On (Recursion (Recursion (Recursion ...

Hello everyone! I had an Amiga article all planned and ready, but since I couldn't make up my mind on the exact restrictions, I kept putting it off. Enough is enough. Now I found myself with a rather stream-of-conscious take on a common programming technique. To wit, it's about the use of recursion, and my struggle to make intuitive sense of it.

So, without further ado, here we go.

On recursion

The effective exploitation of his powers of abstraction must be regarded as one of the most vital activities of a competent programmer.
--Edsger W. Dijkstra

What's the best way to understand recursion? As the old joke has it, you must first learn recursion. Proponents of this technique claim it is an intuitively obvious, far-simpler way of iteration compared to the more popular imperative ones, and that it's only our mindset (maimed as it is by earlier exposure to imperative programming) that has us thinking otherwise.

Personally, I think that's a crock of shit. We all know recursion isn't simple, otherwise the joke would make no sense.

Holding up recursion as some sort of replacement for iteration is also bullshit. Loops are good. For-loops are okay. While-loops are good. All of them work in place of recursion, but that doesn't make them the same. They handle iteration differently. They have different strengths. They are separate idioms. And so, as in all programming, they require separate metaphors to be properly explained.

Now, it's no wonder that imperative programmers are used to while loops: it's built into our metaphor about how programs are supposed to execute. Recursion, though, requires us to revise our expectations. Loops are like a moving watch, with hands (numbers) that increase in proportion to each other, one sometimes triggering an alarm (a specific method call) or clicks over into a new state. So what makes a useful recursion metaphor?

Well... for me, recursion is all about what you see from where you are.

Traditional loops are flat. We see everything as one big field of similar items, or a big mass of numbers. All of these numbers are operated on by the loop, so we need to understand them and their interactions as a gestalt, as a whole. If we don't understand everything about the loop and the data on which it operates, the loop will at some point go off the rails. Those are a lot of factors for a programmer to juggle.

Recursion is different. In a proper recursive algorithm, your data is a structure, a grid. The shape of the grid doesn't really matter: all that matters is what happens on your immediate position on the grid. All you need to remember is that once you step one level up and down in the recursion, you are in effect moving along the grid. That's intrinsic to the structure, to the algorithm's idiom, so you don't need to keep track of it. All you need is to understand what happens at the specific point you occupy.

To me, where the metaphor of regular loop suggests enumeration, the metaphor of recursion suggests traversal. A regular loop chews through items on a level playing field. Recursion moves from node to node, like a spider flitting across a web. That makes recursion a natural fit for things that have tree-like behavior, but less ideal for things like iterating across flat containers. It also means the node is all you need to care about, which means less cognitive work.

Recursion can replace loops in a pinch, yes. By the same token, a wrench can do the work of a hammer. That doesn't make it the best tool for the job.

Perhaps I'm still poisoned by imperative thinking. It may be that Dijkstra, from whatever coder heaven he now resides, is even now shaking his head and muttering something about the irreparable damage of BASIC. Nevertheless, and this may sound paradoxical, I think recursion is even more useful if placed in constraints. And when it comes to coding, perhaps an abundance of metaphors isn't such a bad thing.

That's it for now. If you still have problems wrapping your head around recursion, I refer you to this article.