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

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.

// 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:

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

3. Tree Recursion: Fibonacci's Trap

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)

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)

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.