Recursion and the call stack, step by step

Recursion can feel like a trick the first time you see it: how can a function use itself before it is finished? The answer is that each call is a separate piece of work with its own variables, and the computer keeps track of the unfinished ones on a stack. Once you can picture that stack, recursion stops being mysterious.

Two ingredients: a base case and a smaller step

The factorial of a positive integer is the product of all the integers from 1 up to it: $4! = 4 \times 3 \times 2 \times 1 = 24$. It has a natural recursive definition:

Every correct recursive definition has the same two parts.

• A base case that is answered directly, without recursion. Here it is $n \le 1$.
• A recursive case that reduces the problem to a smaller instance and builds the answer from it. Here $n!$ is built from $(n-1)!$.

“Smaller” matters. Each call must move towards a base case, or the recursion never stops. In code, factorial is three lines:

function fact(n) {
  if (n <= 1) return 1;
  return n * fact(n - 1);
}

The call stack, step by step

When fact(4) runs, it cannot finish 4 * fact(3) until fact(3) has returned. So the computer pauses fact(4), remembers where it was, and starts fact(3) as a brand new call with its own n = 3. The bookkeeping record for each unfinished call is a stack frame: it holds the call’s parameters, its local variables and the place to resume. Frames live on the call stack, last in, first out.

Step through it below. The tree shows every call made so far; the panel on the right shows the frames on the stack right now, with the running call on top.

For fact(4) the stack grows to four frames, fact(4), fact(3), fact(2), fact(1), then unwinds as the answers 1, 2, 6 and 24 come back. The multiplications happen on the way back up, after each inner call returns.

When recursion branches: Fibonacci

The Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, …, each the sum of the previous two:

The direct translation makes two recursive calls, so the calls form a tree rather than a chain. Choose “Fibonacci (naive)” in the stepper and run $n = 5$. The same sub-problems are solved again and again: fib(2) is computed three times and fib(1) five times.

It gets worse quickly. The number of calls made by naive fib(n) is $2F(n+1) - 1$, which grows like $\varphi^n$ where $\varphi \approx 1.618$ is the golden ratio:

The stack never gets deeper than $n$ frames, though. Depth and total work are different things: depth is the longest path from the root of the call tree to a leaf; total work is the number of nodes in the tree.

Memoisation: remember answers you have computed

The fix is to store each result the first time it is computed and look it up afterwards. That is memoisation. Select “Fibonacci (memoised)”: every value from fib(0) to fib(n) is computed once, the second branch of each call becomes an instant lookup, and the call count drops from exponential to $2n - 1$.

You can also turn the recursion inside out and fill a table from the bottom up: start from $F(0)$ and $F(1)$ and loop upwards. This is dynamic programming. Memoisation is the same idea organised top-down, so it only computes the sub-problems the answer actually needs.

How to write a recursive function

1. Find the smaller problem. Ask: if someone handed me the answer for a slightly smaller input, could I finish the job? For a list, “smaller” is usually the list without its first element; for a range, half of it; for a tree, a subtree.
2. Handle the smallest inputs directly. Zero, one, the empty list, a leaf. Check that every chain of recursive calls reaches one of them.
3. Trust the recursive call. While writing the recursive case, assume the call on the smaller input returns the right answer. This is exactly the inductive hypothesis in a proof by induction, and induction is how you prove a recursive function correct.

Recursion versus loops

Any recursive function can be rewritten with a loop and an explicit stack, and any loop can be written recursively. The choice is about clarity and resources.

• Natural fit. Recursion matches recursively shaped data: trees, nested lists, expressions, the file system, divide-and-conquer algorithms such as merge sort and quicksort.
• Stack depth. Each pending call uses stack memory, and the stack is limited. Recursing a million levels deep in JavaScript or Python fails with a “maximum call stack size exceeded” or “recursion depth” error. Algorithms whose depth grows linearly with the input, such as a naive recursive list traversal or depth-first search on a long path, may need an explicit stack.
• Tail calls. A call is in tail position when its result is returned directly, with nothing left to do afterwards. A language that eliminates tail calls can reuse the frame, so tail recursion runs in constant stack space. Scheme guarantees this. ECMAScript 2015 specifies it too, but most JavaScript engines do not implement it, so don’t rely on it in browser code.

Recursion and running time

The cost of a recursive algorithm is described by a recurrence. Factorial does constant work plus one call on $n-1$: $T(n) = T(n-1) + O(1)$, which is $O(n)$. Naive Fibonacci does $T(n) = T(n-1) + T(n-2) + O(1)$, which is exponential. Merge sort does $T(n) = 2T(n/2) + O(n)$, which is $O(n \log n)$. Drawing the call tree and adding up the work level by level is the most reliable way to solve these; see Big-O notation for the vocabulary.

References

1. H. Abelson and G. J. Sussman, Structure and Interpretation of Computer Programs, 2nd ed., MIT Press, 1996. Section 1.2 contrasts recursive and iterative processes.
2. R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Chapter 1 is about recurrences.
3. “Recursion (computer science)”, Wikipedia.