The call stack: how recursion runs and what it costs in memory

When a function calls another function, the computer has to remember where it was — the caller's local variables and the line to come back to. It keeps that in a stack frame, and the frames live on the call stack: each call pushes a frame, each return pops one. Recursion is just a function whose frames happen to belong to itself.

What a call does, step by step

How much memory does recursion use?

Each frame costs a little memory — tens of bytes for a small function. What matters is how many frames are alive at the same time, which is the depth of the recursion, not the total number of calls:

sumTo(n)       n + 1 calls in total, n + 1 alive at once     space O(n)
fib(n)         about 2^n calls in total, only n alive at once  space O(n)
binarySearch   log n calls, log n alive at once            space O(log n)
merge sort     about 2n calls, log n deep                  space O(log n) stack + O(n) for merging

So when you state a recursive algorithm's space, count the maximum depth times the memory per frame, plus anything the function allocates. A loop doing the same job usually needs O(1).

Stack overflow

The call stack is small — a few megabytes. Go too deep and the program crashes: RangeError: Maximum call stack size exceeded in JavaScript, RecursionError in Python (whose default limit is only 1,000 calls), StackOverflowError in Java, and a segmentation fault in C++. Roughly 10,000 frames is a safe ceiling in most languages. That's why recursion over a list of a million values is a bad idea, while recursion over a balanced tree (depth about 20) is fine.

Three ways to write it

The same sum, three ways: plain recursion, a loop, and tail recursion, where the recursive call is the very last thing the function does and the running total is carried along in a parameter.

1function sumTo(n) {2  if (n === 0) return 0;            // base case3  return n + sumTo(n - 1);          // waits for sumTo(n - 1), then adds n4}

1function sumTo(n) {2  let total = 0;3  for (let i = 1; i <= n; i++) total += i;   // no calls, one frame4  return total;5}

1function sumTo(n, total = 0) {2  if (n === 0) return total;3  return sumTo(n - 1, total + n);   // tail call: nothing left to do after it4}

A tail call leaves nothing for the caller to do, so a compiler could reuse the caller's frame and run it in O(1) space. Scheme and some C++ optimisers do; JavaScript engines, Python and Java don't. In those languages, a tail-recursive function is still O(n) deep — rewrite it as a loop when the depth can be large.

Key takeaways