Recursion & the Call Stack

The 10-second versionCopy Anchor Link

Recursion is a function that calls itself on a smaller piece of the same problem, then combines the answers on the way back out. You describe one step — "factorial(n) is n times factorial(n - 1)" — and let the machine handle the rest. The magic ingredient is the call stack: every unfinished call parks a frame that holds its locals and the spot to return to, so when the smallest call finally answers, everything unwinds in exactly the right order. Two rules make it terminate: a base case that answers directly, and a recursive case that always moves closer to it.

Why this existedCopy Anchor Link

Before recursion, there was only go-to and jumping around. If a problem was shaped like a tree — a nested expression, a list of lists — you had to fake your way through it with a hand-maintained pile of "where I was" bookkeeping. The idea that motivated recursion came straight out of mathematical logic.

• 1936 — Alonzo Church formalizes the lambda calculus, a tiny language where functions are values that can be applied to themselves. Self-application becomes a formal thing you can reason about instead of a forbidden trick.
• 1958 — John McCarthy, at MIT, designs Lisp and makes recursion its beating heart. In Lisp you don't loop your way down a list; you say "this is first plus the answer for rest."
• 1960 — Lisp 1.5 ships with recursion and automatic memory management, because a language that creates a new frame per call needs somewhere to put them.

Why did it matter then? Because the machine already had a stack — a region of memory that grows and shrinks Last-In-First-Out. Every call instruction pushes a return address onto it and every return pops it back off. McCarthy's insight was to lean on that, so the programmer could write the mathematical definition and the hardware would keep the bookkeeping. Recursion is the first place the shape of your code starts to mirror the shape of the data.

Inside the inventor's headCopy Anchor Link

Picture McCarthy writing down the definition of a list of numbers: it's either empty, or one number followed by a list of numbers. His whole language is built out of that idea. So when he asks "how do I write length?", the honest answer is the definition itself:

the length of an empty list is 0; the length of (x . rest) is 1 + length(rest).

That's it. No counter, no index, no loop variable. The first attempt at translating that into code is where everyone — McCarthy included — hits the trap:

Watch the trap in code. The naive version looks like the definition, minus the one thing that matters:

// Naive: no base case.const broken = (n) => n * broken(n - 1);   // never returns — stack overflow// Fixed: name the stop condition FIRST, then recurse.const factorial = (n) => (n <= 1 ? 1 : n * factorial(n - 1));

The pivot is the moment you stop thinking "how does it compute the answer?" and start thinking "when do I already know the answer?" Once there's a base case, and every recursive call shrinks the input toward it, the machine does the rest — and that is the aha. The scary part, control flow running backwards and forwards at once, is exactly the part the stack is designed to hide from you.

The final approachCopy Anchor Link

Here is the whole recipe. A recursive function has two arms, and correctness is a promise the recursion makes to itself:

• Base case — the smallest input, answered directly, with no further call.
• Recursive case — build the answer from the answer to a strictly smaller call.

The invariant that makes it correctCopy Anchor Link

The invariant is a contract: if factorial(k) returns k! for every input smaller than n, then factorial(n) returns n!. You prove the base case directly (the contract is trivially true for the smallest input), then show the recursive case preserves it. That's induction, and it's the only reason you're allowed to assume the recursive call is already correct instead of tracing it. And because each call makes the input smaller, the chain is finite — it must eventually land on the base case.

The call stack, frame by frameCopy Anchor Link

As factorial(4) runs, the stack grows downward, one frame per pending call:

Each frame stores nothing magic — just the argument, the local variable r waiting to be filled, and the return address. There is one frame per unfinished call.

A worked trace: factorial(4)Copy Anchor Link

The height of the stack is the depth of the recursion — and depth is the price you pay.

It in codeCopy Anchor Link

const factorial = (n) => (n <= 1 ? 1 : n * factorial(n - 1));const factorialIter = (n) => {  let acc = 1;  for (let i = 2; i <= n; i++) acc *= i;  return acc;};const fib = (n) => (n < 2 ? n : fib(n - 1) + fib(n - 2));

Notice fib is the honest warning: it looks as clean as factorial but recomputes the same subproblems over and over. Its call tree has ~2ⁿ nodes, even though there are only n distinct subproblems. That gap is the entire motivation for memoization and dynamic programming later in the archive.

ComplexityCopy Anchor Link

The lesson: recursion and iteration can compute the same answer at the same time cost, but recursion spends stack depth that iteration doesn't. It's a trade of memory for clarity.

Recursion and iteration are twinsCopy Anchor Link

Every recursion can be rewritten as a loop with an explicit stack, and every loop with a stack can be written as recursion. In C and JavaScript a deep recursion can blow the call stack; Rust will happily optimize a tail call shape into a jump — a call like return factorial(n - 1, n * acc) where nothing happens after the recursive call. When the recursive call is the very last thing you do, no frame needs to stay alive, so the compiler can reuse it. That's the next paragraph.

Where you meet it todayCopy Anchor Link

• Parsing. Every JSON, HTML, or arithmetic expression parser is a recursive descent over a nested grammar — the data is a tree, so the code is a tree.
• Divide & conquer. Merge sort, quick sort, and binary search all say "solve two smaller halves, then combine." That's recursion wearing a hard hat.
• Backtracking. Sudoku, word search, and maze solvers recurse into a choice and unwind when it fails — the call stack is the undo log.
• Tree walks. File systems, scene graphs, and DOM traversal are recursively-shaped data walked by recursively-shaped code.

// A binary tree as nested objects: { value, left, right }const treeSum = (n) =>  n == null ? 0 : n.value + treeSum(n.left) + treeSum(n.right);

A tree has no natural loop — you don't know how wide or deep it is. Recursion is the only way to say "do this to every node" without dragging a manual stack around.

RecapCopy Anchor Link

• Recursion = a base case plus a recursive case that shrinks the input.
• The call stack stores one frame per unfinished call; its height is your recursion depth, and your memory cost.
• The correctness argument is induction: assume the smaller call is right, and prove the step. Same time as iteration, but recursion spends stack.
• Tail calls where nothing happens afterward can be turned into a loop by the compiler — but don't rely on it in C or JS.
• When the data is nested, recursive code is usually the shortest correct description.

Next up: Memory, References & Ownership — where those frames and all your values actually live.