Recursion Explained — Call Stack, Memoization, and Tail Call Optimization

Recursion is a function calling itself. But understanding recursion deeply — the call stack, activation records, why naive Fibonacci is exponentially slow, how memoization reduces it to linear time, and how tail call optimization collapses deep recursion into a loop — transforms it from a mysterious pattern into a powerful and precise tool for expressing problems that have natural self-similar structure.

1. The Call Stack

When a function is called, the runtime allocates an activation record (stack frame) on the call stack. The frame stores local variables, the return address, and the function's arguments. When the function returns, the frame is popped.

Example: factorial(4) Call stack growth \to factorial(4) \to frame: {n=4, return addr} factorial(3) \to frame: {n=3, return addr} factorial(2) \to frame: {n=2, return addr} factorial(1) \to frame: {n=1, return addr} returns 1 \leftarrow pops frame, n=2 computes 2\times1=2 \leftarrow pops frame, n=3 computes 3\times2=6 \leftarrow pops frame, n=4 computes 4\times6=24 returns 24 Stack depth: O(n) \leftarrow stack overflow for large n! JavaScript call stack limit: typically 10,000-15,000 frames. factorial(15000) \to "Maximum call stack size exceeded"

// Simple linear recursion
function factorial(n) {
  if (n <= 1) return 1;           // base case
  return n * factorial(n - 1);    // recursive step
}

2. Base Cases and Structural Induction

Every recursive function must have a base case — a termination condition that returns without making a recursive call. Without it, recursion runs forever (stack overflow in practice).

Correctness of recursive functions is typically proved by structural induction:

Base case: Prove the function is correct for the smallest input.
Inductive step: Assume the function is correct for all inputs smaller than n. Prove it is correct for n using this assumption.

Recursive vs iterative: Any recursive function can be converted to an iterative one using an explicit stack. The conversion is sometimes trivial (linear recursion → loop), sometimes complex (tree traversal → stack-based iteration). The recursive form is often cleaner and more closely mirrors the mathematical definition — the iterative form avoids stack overflow risk.

3. Tree Recursion: Fibonacci's Trap

fib(n) = fib(n-1) + fib(n-2), fib(0)=0, fib(1)=1 Recurrence tree for fib(5): fib(5) / \ fib(4) fib(3) / \ / \ fib(3) fib(2) fib(2) fib(1) / \ / \ / \ fib(2) fib(1) ... Nodes at depth d: up to 2^d Total nodes: T(n) = T(n-1) + T(n-2) + 1 ≈ φⁿ where φ = (1+√5)/2 ≈ 1.618 Time complexity: O(φⁿ) ≈ O(1.618ⁿ) — EXPONENTIAL fib(50) requires ~1.26 × 10¹⁰ calls (takes minutes) The key problem: fib(3) is computed twice, fib(2) three times, fib(1) five times... Subproblems are recomputed exponentially many times. Answer: fib(40) = 102334155 requires ~1 billion recursive calls. fib(40) ≈ 10⁸ calls in JavaScript ≈ several seconds.

4. Memoization

Memoization (top-down dynamic programming) stores the result of each unique function call in a cache. Before computing, check the cache; if present, return immediately.

// Top-down memoized Fibonacci
function fibMemo(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}
// O(n) time — each unique n computed once
// O(n) space — memo stores n values + call stack depth O(n)

After memoization: fib(5) calls: fib(5) \to fib(4) \to fib(3) \to fib(2) \to fib(1), fib(0) then fib(3) is a cache hit \leftarrow no redundant work Total unique calls: exactly n+1 = O(n) Transformation: O(2ⁿ) \to O(n) time [exponential \to linear] General rule: if a recursive function with k parameters has T unique (parameter) states, each computed in O(work) time, memoized complexity = O(T \times work).

5. Dynamic Programming (Bottom-Up)

Bottom-up DP computes subproblems in order from smallest to largest, storing only what's needed. Avoids recursive overhead and stack depth entirely:

// Bottom-up DP Fibonacci — O(n) time, O(1) space
function fibDP(n) {
  if (n <= 1) return n;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];   // only last two values needed
  }
  return b;
}

Bottom-up DP is the approach behind: Floyd-Warshall shortest paths, Knuth-Morris-Pratt string matching, sequence alignment (Smith-Waterman), optimal BST, coin change, knapsack, and the Viterbi algorithm in HMMs.

6. Tail Call Optimization

A tail call is a recursive call that is the very last operation in a function — the caller has nothing left to do after the recursive call returns. In this case, the caller's stack frame is no longer needed and can be replaced (not stacked) by the callee's frame.

// Not tail-recursive: must multiply AFTER factorial returns
function factorial(n) {
  if (n <= 1) return 1;
  return n * factorial(n - 1);   // ← not tail: "n *" done after return
}

// Tail-recursive: accumulator carries running product
function factTail(n, acc = 1) {
  if (n <= 1) return acc;
  return factTail(n - 1, n * acc);   // ← tail: last thing is the call
}
// With TCO: O(1) stack space — compiles to a loop
// JavaScript ES2015 spec mandates TCO; V8 removed it in 2016 (ShadowRealm workaround)

TCO support in 2026: ECMAScript 2015 mandated proper tail calls, but V8 (Node.js/Chrome) removed TCO support due to debugging concerns. Safari's JavaScriptCore does support it. For production JS, use an explicit loop or trampoline instead.

7. Mutual Recursion and Trampolines

Mutual recursion: function A calls B, which calls A. Example: `isEven(n) = isOdd(n-1); isOdd(n) = isEven(n-1)`. Produces deep stacks for large n even if each function is individually tail-recursive.

A trampoline is a loop that repeatedly calls a function until it returns a plain value instead of a new function:

// Trampoline: converts deep recursion to O(1) stack
function trampoline(fn) {
  return function(...args) {
    let result = fn(...args);
    while (typeof result === 'function') {
      result = result();
    }
    return result;
  };
}

// Each step returns a thunk (zero-arg function) instead of calling directly
const isEven = trampoline(function _isEven(n) {
  if (n === 0) return true;
  return () => _isOdd(n - 1);    // return thunk, not direct call
});

Trampolines decouple recursion depth from call stack depth. The trampoline loop uses O(1) stack while processing arbitrarily deep mutual recursion. This pattern is commonly used in Scheme, Clojure, and when implementing interpreters.

💻 Explore Algorithms →