Recursion: how a function calls itself

What is actually happening

A call that is too big to answer outright hands a smaller version of the same question to a fresh copy of itself, and then waits. That copy does the same. Sooner or later a copy gets a question small enough to answer with no help at all. That is the base case, and it hands its answer straight back. Every waiting call then wakes in turn, finishes its own bit of work, and passes its answer up.

So nothing is worked out on the way down. The descent only breaks the problem into smaller pieces. The answer is built on the way back up.

Why it stops

Every recursive function has two branches, and it needs both. The recursive case is the one that calls itself, always on a smaller input than it was given. The base case is the one that answers directly, with no call at all.

The input shrinking is what guarantees you reach the base case. Remove the base case and nothing ever stops the descent; stop shrinking the input and you never arrive at it. Either mistake produces the same symptom, which is why they are worth separating in your head.

How each call remembers its own n

When a call is interrupted it needs somewhere to keep the values it was working with, so they are still there when it resumes. That somewhere is a stack frame: a small block holding this call's n, and the point in the code to carry on from.

Frames are kept on the call stack, which is a stack in the ordinary sense: added to and removed from one end only. Look at the frames beside the animation while it runs. Four calls in flight means four frames, each holding a different n at the same moment. They are not sharing one variable and taking turns. Each call got its own.

That is the whole answer to “how does it remember?”. It does not have to remember. Nothing ever overwrote it.

Where the answer goes

When a call finishes it hands back a return value, and that value goes to exactly one place: the call that was waiting for it, which resumes on the very line where it paused. Nothing is broadcast and nothing jumps back to the start.

Watch the highlighted line as you step. With factorial, line 3 makes the call and line 4 does the multiplication. Line 4 cannot run until line 3 has produced a value, and that is the whole reason the work happens on the way back up.

Now switch to countdown and the order flips. It prints before it calls itself, so all of its work happens on the way down and the return journey does nothing at all. Same shape, opposite timing.

What a frame costs

Every frame is real memory. For a function like factorial that is typically tens of bytes: the saved return address, the saved frame pointer, and the locals. Call depth is therefore a memory cost that grows in step with n.

The space those frames come from is not unlimited either. It was set aside before the program started and it does not grow, so depth is not only a cost but a ceiling. What that ceiling is, and what happens when a program reaches it, is the whole of the next lesson.

Why fib is a different animal

countdown and factorial make one call each, so their call trees are a straight line: n calls, depth n. fib makes two, so its tree branches, and the number of calls stops growing with n and starts growing like 1.618ⁿ, the golden ratio.

Set the animation to fib with n = 5 and count: fifteen calls to produce the answer 5, with fib(1) worked out five separate times from scratch. Nothing is remembered between branches.

The depth is still only n, though, because the tree is walked one path at a time. Wide in total work, narrow at any one moment, which is exactly what the frames show while the tree fans out behind them.

Fixing that repeated work, by keeping answers instead of recomputing them, is a later lesson in this course. It is the same tree with most of it deleted.

Recursion against a loop

Anything recursion can do, a loop can do. The two are equivalent in power, so the real trade is which one makes the code match the problem.

For factorial, a loop is honestly better: same answer, no frames, no depth limit. For walking a tree, recursion wins clearly, because a tree is defined in terms of smaller trees and the code can say exactly that. Write the loop version of a tree walk and you will find yourself building a stack by hand. The same stack, only now it is one you have to maintain yourself.

Tail calls, and why they do not save you here

When a recursive call is the last thing a function does, there is nothing left to come back for, so the frame could be reused instead of stacked. Some languages guarantee this: Scheme requires it, and C compilers often do it with optimisation turned on.

JavaScript engines, in practice, do not, so the stack you see in the animation is the stack you get. It is also worth noticing that factorial as written here is not tail recursive anyway: the multiplication on line 4 happens after the call returns, so the frame still has work to do and cannot be discarded.

Then write some

Work these out on paper before running them. The point is to predict, and the useful moment is the one where your prediction is wrong.

sum(4) should give 10. Fill in the two branches.

function sum(n) {
  if (???) return ???
  return ??? + sum(??? )
}

function sum(n) {
  if (n === 0) return 0        // base case: nothing left to add
  return n + sum(n - 1)        // recursive case: n, plus the rest
}

digits(4051) should give 4. What is the base case, and what makes the input smaller?

function digits(n) {
  if (n < 10) return 1
  return 1 + digits(Math.floor(n / 10))
}

reverse('abcd') should give 'dcba'. Make the input smaller by one character each time.

function reverse(s) {
  if (s.length <= 1) return s
  return reverse(s.slice(1)) + s[0]
}

This runs forever. Why?

function countdown(n) {
  if (n === 0) return
  console.log(n)
  countdown(n)
}

countdown(n - 1)   // the input has to shrink

What does this print for n = 3, and why is it not 3 2 1?

function f(n) {
  if (n === 0) return
  f(n - 1)
  console.log(n)
}

1 2 3

flatten([1, [2, [3, 4]], 5]) should give [1, 2, 3, 4, 5]. The nesting can be any depth.

function flatten(list) {
  const out = []
  for (const item of list) {
    if (Array.isArray(item)) out.push(...flatten(item))
    else out.push(item)
  }
  return out
}

What gets asked, and what the asker is checking. Answer out loud before opening each one. The gap between knowing something and being able to say it out loud is the thing interviews actually measure.