Recursion & the Call Stack
⏱️ ~5-minute bite · solve the sandbox to master
5-Year-Old Metaphor
— The physical, real-world picture. No jargon.🍽️ A stack of plates — each call adds a plate, each return removes one.
The physical picture
Imagine a cafeteria dishwasher stacking clean plates. Every time your function calls itself, the cafeteria worker adds a new plate on top of the stack. That plate holds the current function's local variables and where to return when done.
The base case is the minimum plate stack you allow before the worker starts removing plates. Hit the base case, stop adding plates, start removing them.
Stack overflow = the worker added so many plates they hit the ceiling and dropped them all — the runtime ran out of memory for new stack frames.
Two phases of every recursive function
1. The descent (adding plates)
- Each call adds a frame to the stack
- Work is deferred — nothing resolved yet
- Stops when the base case fires
2. The ascent (removing plates)
- Each return removes a frame
- Deferred results resolve and combine
- Final answer propagates up to caller
Anatomy of a valid recursive function
| 1 | function countdown(n: number): void { |
| 2 | if (n <= 0) { console.log("Done!"); return; } // ← base case |
| 3 | console.log(n); |
| 4 | countdown(n - 1); // ← smaller input (n-1 < n, progress guaranteed) |
| 5 | } |
Interactive Sandbox
— Move something, see it react instantly.Code
| 1 | function factorial(n: number): number { |
| 2 | if (n <= 1) return 1; // base case |
| 3 | return n * factorial(n - 1); // recursive call |
| 4 | } |
Call Stack
Challenge
Explore all 5 recursion patterns by stepping through each to the end. (1/5 explored)
Why Should I Care?
— The exact interview question + the bug it kills.Interview question — base case
"What makes a valid base case? What happens if you get it wrong?"
A valid base case must: (1) be reachable by the recursive calls, (2) not recurse further, and (3) return a meaningful value.
| 1 | // Bug: base case returns wrong value |
| 2 | function factorial(n: number): number { |
| 3 | if (n <= 1) return 0; // ← WRONG — should return 1 |
| 4 | return n * factorial(n - 1); |
| 5 | } |
| 6 | factorial(4); // → 4 * 3 * 2 * 0 = 0 (wrong answer) |
| 7 | |
| 8 | // Bug: base case unreachable |
| 9 | function factorial(n: number): number { |
| 10 | if (n === 0) return 1; // unreachable for n=4,3,2,1 — |
| 11 | return n * factorial(n - 1); // always hits n=0 eventually, ok here |
| 12 | } |
| 13 | // BUT: factorial(-1) → infinite recursion (n never reaches 0) |
Interview question — exponential complexity
"Why does naive fib(n) have O(2^n) calls?"
Each call to fib(n) spawns two calls: fib(n-1) and fib(n-2). The call tree is binary — it roughly doubles at each level. Depth is n, so nodes ≈ 2^n. fib(40) ≈ 1 billion calls.
| 1 | // Fix with memoization — O(n) time, O(n) space |
| 2 | const memo = new Map<number, number>(); |
| 3 | function fib(n: number): number { |
| 4 | if (n <= 1) return n; |
| 5 | if (memo.has(n)) return memo.get(n)!; // cache hit |
| 6 | const result = fib(n - 1) + fib(n - 2); |
| 7 | memo.set(n, result); |
| 8 | return result; |
| 9 | } |
Tail recursion optimization
A recursive call is "tail position" if it's the very last operation — no work is done after it returns. Tail-call optimization (TCO) reuses the current stack frame instead of pushing a new one, making tail recursion O(1) space.
| 1 | // NOT tail-recursive: n * factorial(n-1) does work AFTER the call |
| 2 | function factorial(n: number): number { |
| 3 | if (n <= 1) return 1; |
| 4 | return n * factorial(n - 1); // ← multiply happens after return |
| 5 | } |
| 6 | |
| 7 | // Tail-recursive: accumulator carries the result |
| 8 | function factorial(n: number, acc = 1): number { |
| 9 | if (n <= 1) return acc; |
| 10 | return factorial(n - 1, n * acc); // ← last operation is the call |
| 11 | } |
⚠️ V8 (Node.js / Chrome) does not implement TCO despite ES6 specifying it. Use an iterative loop or trampolining in production.
Production bugs recursion causes
- Missing base case → stack overflow — function recurses until the browser kills it (~10k–15k frames). Manifest as "Maximum call stack size exceeded".
- Wrong base case value — returns a wrong result silently, propagates through every deferred multiplication.
- Deep JSON/XML parsing — recursive parsers stack-overflow on deeply nested documents. Fix: iterative approach with explicit stack.
The Deep Dive
— Spec refs, engine internals, the minutiae.Call Stack Frame Structure
Each frame on the call stack stores: the return address (where to jump back), arguments, local variables, and the saved frame pointer. In V8, each frame is allocated on the native C++ stack, not the JS heap.
Stack Overflow Limits
Browsers cap the call stack at roughly 10,000–15,000 frames (V8: ~15k, SpiderMonkey: ~30k, Safari: ~10k). The exact limit varies by platform and available memory. Deep JSON trees, deeply nested React components, and unguarded recursive parsers are the most common triggers.
| 1 | // Measure your environment's limit |
| 2 | function depth(n = 0): number { |
| 3 | try { return depth(n + 1); } |
| 4 | catch (e) { return n; } |
| 5 | } |
| 6 | console.log(depth()); // ~10k-15k in V8 |
Trampolining — Deep Recursion Without Overflow
Trampolining converts deep recursion into a loop by returning functions instead of calling them. The "trampoline" loop repeatedly calls the returned function until it gets a plain value.
| 1 | type Thunk<T> = T | (() => Thunk<T>); |
| 2 | |
| 3 | function trampoline<T>(f: () => Thunk<T>): T { |
| 4 | let result: Thunk<T> = f; |
| 5 | while (typeof result === "function") result = result(); |
| 6 | return result as T; |
| 7 | } |
| 8 | |
| 9 | // Tail-recursive factorial, thunk-wrapped |
| 10 | function factTail(n: number, acc = 1): Thunk<number> { |
| 11 | if (n <= 1) return acc; |
| 12 | return () => factTail(n - 1, n * acc); // return thunk, not call |
| 13 | } |
| 14 | |
| 15 | trampoline(() => factTail(100_000)); // no stack overflow |
Memoization vs Dynamic Programming
Memoization (top-down)
- Recursive structure preserved
- Cache wraps the function
- Only computes needed subproblems
- Stack overhead still present
DP table (bottom-up)
- Iterative — no stack frames
- Fill table smallest→largest
- Computes all subproblems
- Often space-optimizable to O(1)
| 1 | // DP bottom-up fib — O(n) time, O(1) space |
| 2 | function fib(n: number): number { |
| 3 | if (n <= 1) return n; |
| 4 | let [a, b] = [0, 1]; |
| 5 | for (let i = 2; i <= n; i++) [a, b] = [b, a + b]; |
| 6 | return b; |
| 7 | } |
Why V8 Skipped TCO
ES2015 (ES6) specified proper tail calls (PTC) as mandatory. Safari/JSC implemented it. V8 implemented it behind a flag in 2016, then removed it in 2017. The V8 team's reasoning: PTC breaks stack traces (frames are discarded, so errors show no meaningful call stack), introduces significant complexity for optimizer tiers, and real-world usage was near zero. SyntacticTailCalls (STC — an explicit return continue syntax) was proposed as an alternative but never advanced.
Interview Questions
— Real questions from real interviews — with answers.A base case that stops recursion and a recursive case that makes progress toward the base case.
Each frame occupies stack memory — deep recursion exhausts it; fix with iteration, trampolining, or increasing input constraints.
When subproblems overlap — the same inputs are computed more than once — memoization caches and reuses them.
Replace the call stack with an explicit stack data structure; push right child before left so left is processed first.
Backtracking is recursion that undoes choices — prune when a partial solution can never lead to a valid complete solution.
Memory Game
— Quick quiz — lock the concept in long-term memory.What is in-order traversal and what is it particularly useful for?