4.12 — Recursion, Divide-and-Conquer & Backtracking

Recursion confuses people because they try to trace it. You cannot hold five levels of a call tree in your head, and trying to is the wrong skill.

The right skill is trusting the smaller call. Write the function assuming it already works for smaller inputs, and check only two things: that the base case is right, and that every recursive call is genuinely closer to it. If both hold, the function is correct, and you never trace anything.

1. What the machine is doing

Chapter 2.2 covered the call stack; here is what it means for recursion specifically. Each call gets a stack frame holding its parameters, its local variables, and the address to return to. The frames stack up as you descend and unwind as you return.

function factorial(n: number): number {
  if (n <= 1) return 1;              // (1)
  return n * factorial(n - 1);       // (2)
}

1. The base case — the input small enough to answer without recursing.
2. The recursive case. Note the multiplication happens after the inner call returns, so this frame must stay alive while the whole subtree below it runs.

Calling factorial(4) builds four frames, then collapses them: 1, then 2×1, then 3×2, then 4×6 = 24.

The two costs. Space is O(\text{depth}), always, because every pending frame is live memory (Chapter 4.1 section 6). And the call stack is small — typically 1 MB, versus gigabytes of heap — so a recursion 100,000 deep crashes with a stack overflow while an iterative loop over 100,000 items does not even notice.

Tail calls, and why they do not help you in most languages. If the recursive call is the last thing the function does, with no pending work, the current frame is no longer needed and could be reused. Compilers that implement tail call optimisation turn such recursion into a loop with O(1) space. Scheme and Lua guarantee it; Haskell and OCaml do it; the JavaScript specification requires it in strict mode and only Safari ever shipped it, so in Node.js and Chrome it does not happen. Python and Java deliberately do not do it, so that stack traces stay readable. The practical consequence: in most languages, deep recursion must be rewritten as a loop with an explicit stack, not restructured into tail form.

2. Writing a recursion you can trust

Three questions, in order, and if you answer them the code writes itself.

What is the smallest input I can answer without thinking? That is the base case. Common ones: an empty array, an empty string, a null node, n = 0 or 1.

Assuming the function already works on smaller inputs, how do I build my answer from theirs? This is the leap of faith, and it is the whole method. For factorial, if factorial(n-1) works, then n * that is the answer.

Does every recursive call actually get closer to the base case? If not, you have infinite recursion. f(n) calling f(n) never terminates; f(n/2) and f(n-1) do.

Take reversing a string:

function reverse(s: string): string {
  if (s.length <= 1) return s;                    // (1)
  return reverse(s.slice(1)) + s[0];              // (2)
}

1. A string of 0 or 1 characters is its own reverse.
2. Reverse everything after the first character — assume that works — then put the first character on the end.

Correct, and also a good example of the analysis trap from Chapter 4.1: slice copies, so this is O(n^2) in total, not O(n). The two-pointer version from Chapter 4.2 is O(n) with no recursion. Recursion is a way to organise thought, not automatically a good implementation.

3. Divide and conquer: the three-step shape

Divide and conquer is a specific recursion shape:

1. Divide the problem into independent subproblems of the same kind.
2. Conquer each by recursing.
3. Combine the answers.

Merge sort divides in half, conquers by recursing, combines by merging. Quicksort divides by partitioning, conquers by recursing, and needs no combine because the partition already placed the pivot. Binary search divides in half and only conquers one side.

The word independent in step 1 is what separates divide and conquer from dynamic programming. If the subproblems overlap — if f(5) and f(6) both need f(4) — plain recursion recomputes the shared work exponentially many times, and you need the memoisation of Chapter 4.22.

Analysing it is Chapter 4.1's Master theorem: write T(n) = a\,T(n/b) + f(n) and compare n^{\log_b a} against f(n).

A worked example that surprises people is Karatsuba multiplication. Multiplying two n-digit numbers the schoolbook way is O(n^2). Split each number into halves, and the product needs four half-size multiplications, giving T(n) = 4T(n/2) + O(n), which the Master theorem says is O(n^2) — no gain. Karatsuba's trick is an algebraic identity that computes the same product with three half-size multiplications instead of four, so T(n) = 3T(n/2) + O(n), and n^{\log_2 3} = n^{1.585}. Multiplying two 10,000-digit numbers goes from a hundred million operations to about four million. The lesson: when a divide-and-conquer algorithm is not faster than the obvious method, the fix is usually to reduce the number of subproblems, not to make the combine step cheaper.

4. Backtracking: DFS over a tree of decisions you never build

Backtracking is how you enumerate every valid arrangement of something: all permutations, all subsets, every way to place eight queens, every valid parenthesis string, every path through a maze.

The mental model: there is a tree whose nodes are partial solutions and whose edges are choices. Walk it depth-first. Whenever a branch cannot possibly work, stop and back up. You never build the tree — it exists only as the shape of the recursion.

Every backtracking function has the same four parts:

function permutations(nums: number[]): number[][] {
  const results: number[][] = [];
  const current: number[] = [];
  const used = new Array(nums.length).fill(false);

  function explore(): void {
    if (current.length === nums.length) {        // (1)  complete
      results.push([...current]);                // (2)  ← copy, not the array itself
      return;
    }
    for (let i = 0; i < nums.length; i++) {      // (3)  every choice at this level
      if (used[i]) continue;                     // (4)  prune

      used[i] = true; current.push(nums[i]);     // (5)  choose
      explore();                                 // (6)  recurse
      current.pop(); used[i] = false;            // (7)  UNDO
    }
  }

  explore();
  return results;
}

1. The goal test — when is a partial solution complete?
2. Copy the result. current is one shared array that keeps mutating; pushing it directly stores a reference that will be empty by the end. Forgetting the spread here produces an array of identical empty arrays, and it is the single most common backtracking bug.
3. The choice set — what can I do next?
4. The pruning rule — which choices are illegal or pointless? This is where all the performance is.
5. Choose, mutating the shared state.
6. Recurse into the subtree that choice creates.
7. Undo — this is the "backtrack". Restore the state exactly as it was so the next iteration starts clean. Mutating and undoing one shared array is what makes backtracking O(1) space per level instead of copying the whole partial solution at every node.

Complexity is the size of the tree, and it is inherently exponential. Permutations of n items: n! leaves, and building each output costs O(n), so O(n \cdot n!). Subsets: 2^n. That is not a flaw — the output is that large, so no algorithm can be faster. When the output is exponential, the only wins available are pruning branches early and stopping once you have enough.

Pruning is the whole skill. N-queens with no pruning tries 8^8 = 16.7 million placements; checking column and diagonal conflicts as you place each queen cuts it to about 2,000. The principle: check validity as early as possible, at the moment of the choice, rather than validating a completed arrangement. Chapter 4.18 works through the standard set.

The subsets variant is worth seeing because its shape is different — the choice is binary rather than a loop:

function subsets(nums: number[]): number[][] {
  const results: number[][] = [], current: number[] = [];
  function explore(i: number): void {
    if (i === nums.length) { results.push([...current]); return; }   // (1)
    current.push(nums[i]); explore(i + 1); current.pop();            // (2)  include
    explore(i + 1);                                                  // (3)  exclude
  }
  explore(0);
  return results;
}

1. Past the end, so the current selection is one complete subset. Every leaf is a result here, unlike permutations where only full-length paths count.
2. Take element i, explore everything downstream, then undo.
3. Skip element i.

Two branches per element, n elements, 2^n leaves. Recognising "include or exclude at each step" as the shape is what makes subsets, combination sum and the knapsack problem in Chapter 4.22 all feel like one problem.

5. Converting recursion to iteration

Two reasons to do this: the recursion is too deep for the stack, or the language has no tail calls and the function is hot.

If it is tail recursive, it is a loop directly:

// recursive
function gcd(a: number, b: number): number {
  return b === 0 ? a : gcd(b, a % b);
}
// iterative — same algorithm, O(1) space
function gcdLoop(a: number, b: number): number {
  while (b !== 0) [a, b] = [b, a % b];
  return a;
}

If it is not, you manage the stack yourself. Chapter 4.13.1's iterative in-order traversal is the standard example: an explicit array replaces the call stack, and the extra state you would have kept in local variables becomes part of what you push.

The general recipe: push a frame holding the parameters plus a marker for "which part of the function am I resuming at", then loop popping frames. It is mechanical and it is ugly, which is why you only do it when you must.

The pragmatic middle ground is worth knowing: many "too deep" recursions can be made shallow instead of iterative. Quicksort recursing into the smaller half and looping on the larger caps the depth at \log n. That is one line of change for a guaranteed bound, and it beats a full rewrite.

What the interviewer will push on

"What is the space complexity of your recursive solution?" O(\text{depth}) from the call stack, and they will ask what the worst-case depth is. For a balanced tree, \log n; for a degenerate one, n. Answering "O(1), I do not allocate anything" is the common wrong answer.

"Would tail call optimisation help here?" Two-part answer. First, is the call actually in tail position — is there any pending work after it? n * factorial(n-1) is not, because the multiply is still owed. Second, does the language do it? Most do not, including Node.js, so the answer is usually "it would in principle, but I would rewrite it as a loop instead".

"Trace your backtracking on a small input." They are checking that you know when the undo happens. Say out loud "choose, recurse, undo" as you walk it, and point at the line that restores the state. The follow-up is what breaks if you forget the undo — the next branch inherits the previous branch's partial state and produces garbage.

"Why do you copy the array when you record a result?" Because current is one shared mutable array. Storing a reference stores a view of something that will keep changing and end up empty. This is asked because it is the bug everybody writes once.

"How would you make this faster? It is exponential." The honest first answer is that the output is exponential so no algorithm can be polynomial. Then name the real levers: prune invalid branches at the moment of choice rather than at the leaf, order choices so the most constrained comes first, and stop early if only one solution is needed.

"When is divide and conquer the wrong tool?" When the subproblems overlap. Then plain recursion recomputes shared work exponentially, and the fix is memoisation — which is exactly Chapter 4.22.

One thing to volunteer: name the leap of faith explicitly. "I am assuming the recursive call works for smaller inputs; my job is to check the base case and that each call shrinks." That is the method, and stating it shows you write recursion by construction rather than by trial and error.

Recall

• Do not trace recursion — trust the smaller call. Verify only the base case and that every call moves toward it.
• Space is always O(\text{depth}) from stack frames, and the call stack is ~1 MB against gigabytes of heap, so deep recursion crashes where a loop would not.
• Tail call optimisation needs the call to be the last thing done and the language to implement it — Node.js and Chrome do not, so rewrite as a loop instead.
• Divide and conquer needs independent subproblems; when they overlap you need memoisation (4.22). Analyse with the Master theorem, and when it gives no gain, reduce the number of subproblems (Karatsuba: 4 → 3).
• Backtracking is DFS over a decision tree that is never built, with four parts: goal test, choice set, prune, and choose / recurse / undo.
• Always copy the partial solution when recording a result — the working array keeps mutating.
• Backtracking is exponential because the output is; the only real lever is pruning at the moment of choice rather than validating at the leaf.

Self-test: Why is n * factorial(n-1) not a tail call? · What exactly goes wrong if you push current instead of [...current]? · Why does Karatsuba beat schoolbook multiplication, in terms of the recurrence? · Give the one-line change that caps quicksort's recursion depth at \log n · What property must subproblems have for divide and conquer, and what do you use when it fails?

Next: 4.13 is the first structure that is defined recursively, so every algorithm on it is too — binary trees and search trees, the four traversals, and why an unbalanced tree quietly becomes a linked list.