Recursion is Wonderful

The old glossary joke that never gets old:

Recursion, n. See recursion

Recursion is a technique where a function calls itself. It should have some stopping condition, otherwise the recursion could happen infinitely. Mathematically, that is OK - imagine the recursive functions used to generate fractals and the like.

But real computer hardware has finite resources, so if you're recursing in a computer program, you really do need the recursive function to know when to give up - either it finds its answer, determines there is no answer, or just stops after some given recursion depth.

Recursion is a brain-melty topic for the uninitiated. And even for seasoned programmers, recursion seems to invite confusion or bugs. I've read corporate software engineering "best practices" guides that explicitly call out recursion as being a naughty no-no on the theory that recursive code is hard to understand, maintain, or troubleshoot.

That all might well-founded, but it also tosses out an elegant and powerful programming idiom. Many problems lend themselves to recursion, but can also be tackled with an iterative approach. But there are some cases where you might not be able to reasonably avoid recursion. And if you're new to software development or computer science, learning about recursion will help you build pattern matching skills for later when you encounter problems for which it might be appropriate or indispensible.

Self-Similarity

I'm thinking about problems that can be broken down into smaller problems that share the same properties as the one you started with. Take the following algorithm for finding a word in a printed dictionary:

1. The word could be anywhere between the first word and last word in the dictionary.

2. Pick a candidate word that is in the middle of the list of words between first and last.

3. If that's the word you're looking for, stop.

4. Otherwise, determine if the target word is before or after your word, and update first or last to be the candidate you just used to narrow your search.

5. If first and last are right next to each other and the candidate is not the target you're looking for, you can give up because your dictionary doesn't have that particular word.

Ponder that for a bit. Once you've flipped to the middle page, you've just chopped out half of the possible values in your search space! And now you have exactly the same problem but in a smaller form. Self-similarity is a hallmark trait of a recursion-friendly problem. You don't need recursion to reduce the search space, but if used properly, recursion makes it tidy.

This is called a binary search. Recursion works really well in this case, and an iterative approach is also possible. The data is sorted, and we have an easy way to keep track of the boundaries of our search space. If your data structure is an indexable list (like a vector or array), you only need to keep track of indices.

Or if your data structure is a binary tree, the tree's existing structure does most of the work for you! Every time you follow a reasonably balanced binary tree link to a child, you just cut the amount of work by half or so.

Graphics Subdivisions

If you're writing computer graphics code that has to push millions of pixels per frame at a rate of 60 times per second, it typical to structure the processing so it needs to do as little work as possible while still achieving an acceptable level of quality. Sometimes the problem can be posed in a way that you can solve a bunch of smaller problems in parallel using graphics hardware. That's one way that self-similarity can help you, though this doesn't necessarily involve recursion. (So the point here is that self-similarity doesn't necessarily mean that self-similarity means recursion is appropriate).

Here's a case where recursion can be used to great effect. Imagine you're going to render a video game scene that involves (oh I don't know) a big scary dragon or something. And some 3D modeler spent all week defining the geometry and textures for that creature involving millions of vertices.

If you're far enough away from the dragon, it is really small on the screen, and rendering the dragon with 100% of its details would be pointless, because screens are only so big, and the user's vision is only so good. Besides, there's loads of other stuff to render. So in this "far from dragon" situation, it can be helpful to have a lower fidelity model that lets you render it nicely with a fraction of the effort.

The original dragon model can be used to generate this lower fidelity data structure by smartly chopping up its surface into pieces so that it has (say) half the geometry data to work with. This is called "decimating" the model. And as long as you have an approach to downsample the 3D model by half, you could feed that model into the same function that yields a model with a quarter of the original geometric data. And so on.

Try to avoid letting the dragon get too close, though, because you're more likely to get eaten or burned to a crisp.

Parsing Programming Languages

When you write computer code, the compiler or interpreter has to process your source code, which has a well-defined grammar. Often these language grammars have recursive definitions. For example, an expression like (foo * 8) / total is built out of several other expressions:

• Division expression: (foo * 8) / total

  • Parenthetic expression: (foo * 8)

    • Multiplication expression: foo * 8

      • Variable expression: foo

      • Integer literal expression: 8

  • Variable expression: total

A grammar to parse that could justifiably use a recursive approach, since any expression can be a composition of one or more smaller expressions, and it has to be able to handle any expression. So why not just recursively re-use the code that can parse expressions? This is called a recursive descent parser.

Don't be afraid of recursion

Problems that lend themselves to recursion are all over the place. Even if you end up taking an iterative appraoch instead, it will be extremely helpful for you to form an intuition of the kinds of situations where recursion could be great, or when it might help you understand a problem well enough to develop an alternative approach.