Recursion predates computers, but computers’ ability to repeat the same task over and over made recursion a common approach to solving complex problems. Factorials might be a classic example of what recursion can do, but recursion enables many more divide-and-conquer approaches, as well as useful approaches to infinite loops.
You may be nodding your head, thinking “sure, but we don’t need to think about that any more.” Or you may be nodding your head, thinking “if only anyone remembered this stuff any more.”
Until a year or so ago I was in the first camp. I knew the basics of recursion, applying it once in a while to calculations and tree-walking, but it didn’t seem central. Loops and queries of various kinds seemed to make recursion a marginal topic. Usually, seeing recursion was a sign for me to move on, marking a story as “more magic than I needed to know about.”
Erlang forced me to learn recursion—well beyond factorials and trees. Single-assignment variables are a stern master, making me rethink most of the logic I’d used for the last thirty years. There were pleasant surprises, too, like the usefulness of infinite loops in Erlang processes. By the end of writing Introducing Erlang, I had my first genuinely fond feelings for recursion.
Now that I think I have a handle on recursion, I’m paying much more attention to it than I used to, and suspecting I’ve crossed a line. It seems like every language has its own dividing line between amateur and expert, but recursion seems to be a line that crosses programming broadly. Languages meant to be approachable go out of their way to make recursion invisible, while languages meant for experts (or those aspiring to be experts) leave recursion in the open.
(There are other dividing lines: memory management, binary processing, concurrency, error handling, and many more. Even scope can be a line, and not just for global variables. Different environments make different choices about how to handle, or not handle, these challenges.)
It may just be that I’m spending too much time with functional programmers, but I’ve also been in a few conversations lately where “it doesn’t cover recursion” or “they don’t really understand recursion” meant that someone wasn’t considered credible. A few years ago I would have blown that off—since I didn’t really understand recursion deeply myself or care—but now that I’ve safely crossed that chasm I’m left wondering just how wide a gap this key concept creates among programmers.
Or am I the only one noticing?