Recursion, and why it feels like cheating

1. Slide 1

   The reading habit

   Stop tracing. Assume the function already works, and check only two things: that it handles the smallest case, and that every other case gets strictly smaller.

   def total(xs):
       if not xs:
           return 0
       return xs[0] + total(xs[1:])

   Read it that way and there is nothing to verify by simulation. The empty list sums to zero, which is right. A non-empty list is its first element plus the sum of the rest — and the rest is shorter, so it will eventually be empty. Both boxes ticked, the function is correct, and you never once had to imagine four nested calls.

   This is mathematical induction wearing different clothes, and the fact that it was a proof technique for three centuries before it was a programming technique is the reason it feels alien. It is not how anybody thinks about machines. It is how people think about arguments.

2. Slide 2

   What termination actually requires

   A recursive function terminates when there is some quantity that decreases on every call and cannot decrease forever.

   Usually that quantity is obvious: a list gets shorter, a number gets smaller, a tree gets closer to its leaves. When it is not obvious, that is the warning sign. The classic bug is a recursive call that passes the same argument unchanged in some branch — the function is correct on paper, terminates on every input the author tried, and hangs on the one they did not.

   Euclid's algorithm, hanging in the Gallery of Methods, is a good case to sit with. Each step replaces a pair of numbers with a smaller pair, and it is not immediately obvious that the remainder always shrinks — but it does, strictly, and that single fact is the entire termination proof for an algorithm from about 300 BC that is still in your cryptography library.

3. Slide 3

   The stack is not free

   Every pending call occupies memory, and this is the cost that a loop does not have.

   total([1,2,3])
     total([2,3])
       total([3])
         total([])

   Four frames alive at once, each holding its own arguments and its own place to return to. For a three-element list that is nothing. For a list of a million it is a crash, and it will be a crash with a name — stack overflow — that tells you exactly this happened and nothing about which function did it.

   The practical limit is lower than people expect. Python defaults to about a thousand frames and will refuse to go further on purpose; most systems languages get tens of thousands before the operating system stops them. So recursion over a list is a poor idea and recursion over a balanced tree is excellent, because the depth of a balanced tree with a million nodes is twenty.

4. Slide 4

   Tail calls, and the languages that keep the promise

   There is a case where the stack cost disappears entirely, and whether your language exploits it is one of the sharper dividing lines between language families.

   (define (loop n acc)
     (if (= n 0)
         acc
         (loop (- n 1) (+ acc n))))

   The recursive call is the last thing that happens. Nothing waits for its result, so the current frame has no reason to survive it — it can be reused rather than stacked, and the recursion becomes a loop with no change to the source. Scheme requires this and the standard says so; so do most functional languages. C compilers usually do it when optimising. JavaScript specified it and then almost no engine implemented it, which is a small tragedy.

   The difference matters because it decides whether recursion is a general tool or a tool for shallow problems. In Scheme you may write every loop as a recursion. In Python you may not, and the language tells you so by refusing to add the optimisation on the grounds that it would spoil stack traces — which is a real trade-off, honestly made, and not everyone agrees with it.

5. Slide 5

   Some shapes are recursive already

   The strongest argument for recursion is not elegance. It is that some data has the structure built in, and a loop over it is a recursion with the bookkeeping done by hand.

   A tree is defined as a node containing trees. A directory contains directories. An expression contains expressions — the abstract syntax tree in the compiler lecture is recursive all the way down. Writing a function over any of those with an explicit stack is possible and is what the recursive version compiles to, but you have taken a definition that matched the data and replaced it with one that matches the machine.

   The Composite pattern in the Hall of Composition is this observation turned into an object-oriented form: a leaf and a branch presenting the same interface, so that code which walks the structure does not need to know which it is holding. The pattern is recursion, admitted into a language that preferred not to talk about it.

6. Slide 6

   Divide and conquer

   The other place recursion earns its keep is where splitting a problem in half is what makes it fast, and the recursion is the algorithm rather than a way of writing it.

   Quicksort partitions a list and sorts both halves. Binary search discards half the range and searches the rest. Both hang in the Gallery of Methods, both are four or five lines, and in both cases the loop version is longer and harder to convince yourself of.

   What the recursion is expressing is the recurrence relation that gives the complexity. "Solve two problems of half the size" is exactly what produces the logarithm in the running time, and the shape of the code is the shape of the proof. That correspondence is why algorithm textbooks present these recursively even in languages where a loop would run faster.

7. Slide 7

   You do not need a name

   The strangest result in this area, and the one hanging in the Cabinet of Curiosities, is that recursion does not require the ability to refer to yourself at all.

   The Y combinator is a function that takes a non-recursive function and returns a recursive one. It contains no name for itself, no assignment, no loop — nothing but function application. It exists because Alonzo Church's lambda calculus of 1936 had no way to name a function, and recursion had to be built out of what was there.

   It is genuinely difficult to read and the museum does not pretend otherwise. What it is worth taking from it is that self-reference is not a primitive that a language must provide. It is a thing you can construct, from functions, if you are sufficiently determined — which means the discomfort this lecture opened with was pointing at something real. A function calling itself does need explaining. It just turns out to have an explanation.

8. Slide 8

   What to take away

   Recursion is not a clever alternative to loops, and not something to be proud of using.

   It is the right shape when the data or the algorithm already has that shape, and the wrong one when the only thing being recursed over is a sequence.

   Check the two things — the base case, and that something strictly decreases — and stop simulating. Watch the depth rather than the size: a million-element list will kill you and a million-node balanced tree will not. Know whether your language eliminates tail calls, because the answer changes what you are allowed to write.

   And when a recursive function is hard to read, the usual cause is that it is doing two jobs, not that recursion is hard. Split it, and the two halves are generally both obvious.

← All lecturesAtrium