The Politics of Recursion

How close to the metal must programmers be?

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?


Sign up for the O'Reilly Programming Newsletter to get weekly insight from industry insiders.
topic: Programming
  • Charlie

    Back when I taught CS1, I always introduced recursion before looping. If you’re able to consider function calls abstractly instead of trying to emulate the steps in your head, it’s really simpler than looping. And abstract thinking is key to programming.

  • Peter Hunsberger

    Makes sense. Ever since I 1st groked XSLT (I know, don’t get you started), I’ve come to regard functional programming as the dividing line between those who are capable of “CS” vs. those that do programming (no, that’s not an insult). Recursion is a major shift in focus for many who make that leap, though there are other lessons to be learned, immutability being perhaps even more subtle and important.

    • Eric Elliott

      The importance of immutability is another great topic I’d love to bring more attention to. Particularly how it can eliminate the possibility of order-dependency bugs, enhance code reuse, and enable algorithm parallelization…

    • J David Eisenberg

      I never understood LISP, but I had no problem with XSLT. I think that is partially because it doesn’t look like any other programming language, so I was never tempted to think in iterative terms; it was just “oh yeah, these are XSLT’s crazy rules that I have to live with.”

  • Eric Elliott

    You’re not the only one, but in languages like JavaScript, where (at least for now), recursion either slows things down, or leaves you in danger of exploding the stack, recursion is often avoided, particularly by those who lack a deep understanding of it. Once bitten, twice shy.

    That said, there are classes of problems for which recursion is a great solution… this would be a great topic for my blog: Good ways to use recursion in JavaScript.