Recursion and the Call Stack

Recursion has a reputation for feeling like a magic trick — a function that calls itself, and somehow the right answer falls out the other end. It stops feeling like magic the moment you trace what's actually happening on the call stack, which this course covered mechanically (if briefly) back in the JavaScript foundations material. This lesson does it properly, because trees and graphs — most of the rest of this course — lean on recursion constantly.

Every recursive function has two parts

function sum(n) {
  if (n <= 0) return 0;      // base case — stops the recursion
  return n + sum(n - 1);     // recursive case — calls itself with a smaller problem
}

The base case is the condition under which the function answers directly, without calling itself again. The recursive case calls the function again with an input that's genuinely closer to the base case. Both are required: skip the base case and the function never stops calling itself; skip making real progress toward it (say, accidentally calling sum(n) again instead of sum(n - 1)) and it never stops either, just with the same argument forever.

Tracing the stack by hand

Call sum(3). Here's what actually happens, step by step:

1. sum(3) starts. It needs sum(2)'s return value before it can compute 3 + sum(2) — so it calls sum(2) and pauses, exactly like any function call pauses its caller.
2. sum(2) starts, needs sum(1), pauses, calls it.
3. sum(1) starts, needs sum(0), pauses, calls it.
4. sum(0) starts. n <= 0 is true — base case. Returns 0 immediately, no further call.

At this exact moment — right before anything has returned — all four calls are alive on the stack simultaneously:

Now it unwinds, bottom-up:

5. sum(0) returns 0. sum(1) resumes, computes 1 + 0 = 1, returns 1.
6. sum(2) resumes, computes 2 + 1 = 3, returns 3.
7. sum(3) resumes, computes 3 + 3 = 6, returns 6.

The additions don't happen in the order the calls were made — they happen in the reverse order, as the stack unwinds. This is the single most important thing to internalize about recursion: a function can't compute its own result until the call it made returns, which means the "real work" of a recursive function happens on the way back up, not the way down.

Why this matters beyond tracing an example

This mental model is what lets you actually design a recursive function instead of guessing at one: ask "what's the smallest version of this problem I can answer directly" (the base case), then ask "how do I turn a bigger version of this problem into a smaller one, plus a little extra work" (the recursive case), then trust that the smaller version handles itself. That trust — not tracing every single frame every time — is what makes recursion tractable for problems too deep or irregular to trace by hand, which is exactly the situation trees and graphs put you in, a few lessons from now.

It's also the mental model behind reading a stack trace, which is literally this same picture, printed: the function that crashed, then the one that called it, then the one that called that — read top to bottom, it's the call stack at the moment of the error, frozen.

Run it and read the indentation: calls nest deeper going down (each one pausing the one above it), then "resumes" messages print in reverse order coming back up — the trace makes the pause-and-resume mechanism visible instead of asserted.

What to remember

• Every recursive function needs a base case (a condition that returns directly) and a recursive case that provably moves closer to it.
• Calling a function pauses the caller, exactly as in any function call — recursion is just a function whose caller happens to be itself, one level up.
• At the deepest point of a recursive chain, every unreturned call is alive on the stack simultaneously — that's real, measurable memory, as covered in the space-complexity lesson.
• A recursive function's actual computation resolves from the base case outward as the stack unwinds, not from the first call inward — trace it bottom-up when in doubt.