Recursion, and Why It Works

A function that calls itself looks like it should not work. If answering a question requires answering the same question, nothing has actually moved, and the whole arrangement has the smell of circular reasoning.

It is not circular, and getting straight on why is worth doing before anything else in this section. Recursion is mathematical induction wearing different clothes. Once you can see the two as one argument, writing a recursive function stops being a matter of tracing calls in your head and becomes a matter of checking three short claims, none of which asks you to picture the whole tree at once.

A function defined in terms of itself

Factorial earns its place as the standard first example. The factorial of a whole number n, written n!, is what you get by multiplying every whole number from 1 up to n. So 5! is 5 x 4 x 3 x 2 x 1, which comes to 120.

Stare at that product for a second and something falls out of it. The tail of it, 4 x 3 x 2 x 1, is exactly 4!. That means 5! is simply 5 x 4!. Nothing about the number five made that work either. Every factorial has the next smaller factorial sitting inside it, and that gives you a definition of factorial written in terms of factorial.

fact(0) = 1
fact(1) = 1
fact(n) = n x fact(n - 1)

Two of those lines are answers and the third is a rule. The first two say what to do when the problem has got small enough to settle outright, and they are the base cases. The third says how to turn a larger problem into a smaller one, and it is the recursive case. Every recursive definition you meet from here on has that same two-part shape.

function factorial(n) {
  if (n <= 1) return 1;          // base case: answered outright
  return n * factorial(n - 1);   // recursive case: shrink, then combine
}

Below is that function running, drawn as a tree of calls. Each box is one call, it turns green the moment it has a value to hand back, and stepping through frame by frame shows the chain traveling all the way down to the base case before a single answer starts coming back up.

Two features of that shape are worth noticing now, because both come back later. The chain goes all the way down before it comes back up, which means the call you made first is the last one to finish, and that ordering is not a quirk of this example but a property of every recursion ever written. No question gets asked twice here. Every call in the tree is about a different number.

The part that feels like cheating

Here is the objection that bothers most people the first time they see this. The definition of factorial uses factorial. You have not been told what factorial is. You have been told what it equals in terms of itself, which sounds a lot like being told that a word means what the word means.

The objection is a fair one and there is a real answer to it. The answer is not that the definition must be fine because the code happens to run. It is that the definition rests on a case which does not use factorial at all, and every other case can be traced back to that one in a finite number of steps, which is the whole difference between a definition that grounds out and one that spins.

The same argument as induction

If you have met mathematical induction before, this next part will feel familiar. Induction proves a claim about every whole number without checking them one at a time, which would take forever. It manages that in two moves.

First you prove the claim for the smallest case outright, usually with arithmetic simple enough to do on paper. Then you prove something conditional: if the claim holds for n minus 1, it holds for n. Those two together are enough to cover everything. The first case is settled directly, the second follows from the first, the third from the second, and the chain reaches every number you could name.

That is exactly the shape the factorial code has. Set the proof and the function out side by side and the correspondence runs line for line, with every move in the argument answered by a line of code doing the same job.

The middle row is the one doing the work, and it is the one people distrust. You are allowed to assume the smaller call is correct. Not hope, assume. That assumption is not a leap of faith, because it is precisely what the induction step is entitled to help itself to, and the base case is what pays for it.

In practice this changes how you write recursive code, and the change is a big one. You never have to hold a call tree in your head. You write the base case, you write the combining step, and then you check one thing: would that step be right if the smaller answer were right? Three small checks. Each one fits inside a single line of thought.

The widget above has a panel that spells those three out for whichever call is running. Step through it again with that panel open and the assumption gets named for the call actually on screen, rather than left sitting there as an abstract n.

What a recursive function has to get right

Two things can go wrong here, and awkwardly, both show up as the same symptom.

The first is a base case that is missing, or one that never gets reached. With nothing to stop the chain the calls keep coming until the program runs out of room to remember where it was, which in most languages means a stack overflow whose error message almost never points at the line that actually caused it.

The second is an argument that fails to shrink. A recursive call is only any use when it asks about a strictly smaller problem, and smaller has to be measured against something that cannot keep decreasing forever. Counting down toward zero qualifies. Passing the same value straight through does not.

function broken(n) {
  return n * broken(n);          // the argument never shrinks
}

function alsoBroken(n) {
  if (n === 0) return 1;         // a base case that odd inputs sail past
  return n * alsoBroken(n - 2);
}

The second one is nastier than the first, because it works. Feed it an even number and it terminates and hands back something that looks perfectly reasonable, so the function sails through whatever test you happened to write for it. Feed it 5 and it counts 5, 3, 1, then minus 1, minus 3, and never so much as touches zero. Half the inputs are fine. Bugs like that are the ones that reach production.

Reading a call tree

Factorial makes one call per level, so its tree is a straight chain. Most recursions worth writing branch instead, and the moment one call makes two calls of its own the tree stops being a line and starts being a shape, which is where a picture begins to earn its keep.

Switch the widget above over to Fibonacci and step through that instead. Each call now makes two, the tree fans out, and before long the same numbers start turning up in different corners of it. That repetition is not an artifact of the drawing. It is real work the program is doing more than once, and it is the whole subject of the next tutorial.

Recursion is correct because of induction, and the base case is what the entire argument stands on. Carry that piece forward, because what comes next is not about whether recursion works. It is about what recursion costs, and for some very ordinary problems the answer turns out to be far more than it has any business costing.