Recursion (FULL GUIDE)

A function that calls itself looks like it shouldn't work, if answering a question requires answering the same question, nothing's actually moved, and the whole arrangement has the smell of circular reasoning.

But it isn't circular, and getting straight on why is worth doing before anything else in this section. Recursion is like the CS equivalent of mathematical induction. This guide covers both halves of the subject: how to write recursive functions that are correct, and how to recognise the ones that are correct and still ruinously slow.

A function defined in terms of itself

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.

The tail of it, 4 x 3 x 2 x 1, is exactly 4!. That means 5! is just 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 once the problem's gotten small enough to settle outright, and they're the base cases. The third says how to turn a larger problem into a smaller one, and we'll call it the recursive case. Every recursive definition you'll see has these two core parts.

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 things about 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 isn't a quirk of this example but a property of every recursion ever written. No question gets asked twice here, either. Every call in the tree is about a different number.

The same argument as induction

If you've 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's exactly the shape the factorial code has. Set the proof and the function 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 can be the most confusing part for those learning recursion. You're allowed to assume the smaller call is correct, then by our formula (the rule), we can then calculate the value for the next few cases.

What a recursive function has to get right

Two things can go wrong here:

The first is a base case that's missing. 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 common mistake is that the function doesn't always reach the base case. A recursive call is only any use when it asks about a strictly smaller problem, and smaller has to be measured against something that can't keep decreasing forever.

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);
}

Notice the second function alsoBroken(n) , it actually works for even inputs but wont even run for odd ones which is a mistake that can be hard to debug.

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 starts earning 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 isn't an artifact of the drawing. It's real work the program is doing more than once, and the rest of this guide is about it.

Recursion is correct because of induction, and the base case is what the entire argument stands on. That settles whether recursion works. The rest of this guide is about what it costs, because for some very ordinary problems the answer turns out to be far more than it has any business costing.

When recursion does the same work twice

Fibonacci is defined by a rule short enough to hold in your head. Each number is the sum of the two before it, and the sequence starts from 0 and 1. Turning that into code takes about four lines, and those four lines are close to a word for word transcription of the definition. Nothing about it looks expensive.

function fib(n) {
  if (n <= 1) return n;            // base cases
  return fib(n - 1) + fib(n - 2);  // recursive case
}

Written this way it's also close to unusable. Ask it for the fortieth Fibonacci number and a modern laptop will sit there thinking for a noticeable stretch of time. Ask for the sixtieth and you won't have an answer by the end of the week. The definition is correct and the translation into code is faithful, so the fault sits somewhere neither of them can be blamed for.

Look at what Fibonacci actually does

The problem is invisible in the code and impossible to miss in the tree. Below is fib(6) running with nothing clever attached to it, and the thing to watch isn't the shape of the tree so much as the labels written inside the boxes.

By the end, the counter reads 25 calls. Now count the different questions those calls actually asked: fib(6), fib(5), fib(4), fib(3), fib(2), fib(1), fib(0). Seven. Twenty-five calls to answer seven questions, and the dashed coral rings mark every call whose answer was already sitting somewhere to its left by the time it ran. Eighteen of the twenty-five calls are repeats.

fib(3) alone gets computed three separate times, and none of those three is cheap, since each one rebuilds the entire subtree underneath it from scratch. That subtree has its own repeats inside it, and those repeats have repeats of their own, so the waste compounds the whole way down instead of merely adding up. Nothing in the four lines of code hints at any of it.

There's a neat way to see why the total goes exponential without doing any algebra at all. Every call that isn't a base case makes two more, so the number of calls on each level roughly doubles as you go down, and the tree runs about n levels deep before it bottoms out. Doubling n times is what 2 to the power of n means.

How bad it gets

Push the input up to fib(9) and the counter reads 109 calls for ten distinct questions. The pattern behind those numbers is worth naming. Every step of n multiplies the number of calls by about 1.6, which is what exponential growth looks like when you meet it out in the open. It isn't gentle.

Read those two columns against each other for a moment. Forty-one different questions have answers worth knowing, and the program asks 331 million of them. That gap, between how much information the problem actually contains and how much work the program does to extract it, is the entire subject of this section. Forty-one answers, 331 million questions.

The two properties that make this fixable

Not every slow recursion can be rescued the same way, and it pays to be precise about which ones can. Two properties have to hold, and both carry names you'll meet in every textbook that covers the topic, which makes them worth learning properly rather than by feel.

Overlapping subproblems. The recursion has to keep asking the same questions. Fibonacci does this spectacularly, asking seven distinct questions twenty-five times over. If every call in the tree asked about something genuinely new, there'd be nothing at all to save, and no technique in this section would apply. Fibonacci passes this one easily.

Optimal substructure. The answer to a problem has to be built out of answers to smaller versions of the same problem, and those smaller answers must not depend on which larger problem happened to ask for them. fib(4) is 3 no matter who's asking. That last clause is easy to read past.

That second condition sounds like a technicality, and it's nothing of the kind, because it genuinely fails for real problems. Suppose the best route from one city to another depends on which cities you've already passed through, as it does the moment a rule says you can't visit anywhere twice. The subproblem stops having one answer. It has a different answer for every history that could've led into it, and storing results by city buys you nothing at all.

Where plain recursion is already fine

Plenty of recursive algorithms branch without ever repeating themselves, and those need no rescuing at all. Merge sort is the obvious example: it splits a list in half, sorts each half by calling itself, and merges the two sorted results, so its call tree branches in exactly the way Fibonacci's does.

The difference is that the two halves are different lists. Nothing merge sort works out about the left half is ever wanted for the right half, so there's no question asked twice and nothing a cache could catch. That family has its own name, divide and conquer, and it's the case where recursion's already doing the right amount of work. Dynamic programming is what you reach for when the pieces overlap. The distinction isn't academic.

Spotting it before you write the code

Fibonacci is a set piece, and set pieces are easy. The skill worth having is noticing the same shape in a problem nobody's labeled for you, and there's one reliable question that gets you there. Write down what a single call actually depends on, then ask how many different values that description can take. Then count the states.

If the answer is some manageable number, a few thousand or a few million, and the recursion clearly wanders across that space more than once, you're looking at a dynamic programming problem whether or not anyone's said so out loud. If instead a call depends on the entire history of what came before it, you're not, and nothing in this section will save you.

Two names for one fix

The repair comes in two flavors and they compute the same thing. Storing answers as the recursion runs is called memoization, and filling those answers in from the bottom up without recursing at all is called tabulation. Those two, together with the two properties above, are what people mean when they say dynamic programming.

The name itself is famously unhelpful. Richard Bellman coined it in the 1950s, and by his own later account the choice had at least as much to do with sounding respectable to the people funding the work as with describing it. Programming here means scheduling, in the sense of programming a timetable, and has nothing to do with writing code. The label stuck anyway.

The diagnosis is finished. Twenty-five calls for seven answers, and the count more or less dictates the cure: answer each question once and hang on to the answer. The next tutorial does that in three lines of code.