Chapter 4a — Recursion Problem Patterns

The goal of this chapter: internalize the three recursion shapes. Once you see the shape of a problem, the solution structure writes itself.

The Three Recursion Shapes

Every recursion interview problem fits one of three shapes:

Shape 1: Linear Recursion
One recursive call per level. f(n) = work + f(n-1). Call tree is a chain. Time: O(n). Space: O(n).
Examples: factorial, reverse string, power function.

Shape 2: Tree Recursion (Branching)
Multiple recursive calls per level. f(n) = f(smaller) + f(smaller). Call tree branches. Time: O(branches^depth). Space: O(depth).
Examples: Fibonacci (naive), subsets, permutations, backtracking.

Shape 3: Divide and Conquer
Split in half, recurse on halves, combine. f(n) = 2f(n/2) + O(n). Call tree: balanced binary, log-depth. Time: O(n log n) or O(log n). Space: O(log n).
Examples: merge sort, binary search, merge k sorted lists.

When you see a new problem, identify the shape first. Then the structure follows.

Pattern Map — Before Reading Problems

Problem 1: Fibonacci — Memoization Preview

Problem: Compute the nth Fibonacci number.
fib(0)=0, fib(1)=1, fib(n) = fib(n-1) + fib(n-2)

Four Questions

Q1: What do I have? A number n. The definition of Fibonacci.
Q2: What do I want? The nth Fibonacci number.
Q3: What is the brute force? Direct recursive: fib(n-1) + fib(n-2). Correct but O(2^n).
Q4: Where is the waste? fib(3) is computed over and over. The call tree has exponentially many redundant nodes.

Finding the Waste

For fib(6), draw the call tree partial:

fib(6) calls fib(5) and fib(4)
fib(5) calls fib(4) and fib(3)    ← fib(4) computed twice
fib(4) calls fib(3) and fib(2)    ← fib(3) computed 3 times
...

The number of redundant calls grows exponentially. fib(40) would make over 1 billion calls. But there are only 41 unique subproblems: fib(0) through fib(40).

The fix: Cache. First time you compute fib(k), store the result. Next time, return the cache immediately.

function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];  // cache hit — O(1)
  memo[n] = fib(n - 1, memo) + fib(n - 2, memo);
  return memo[n];
}

Dry Run: fib(5, {})

fib(5)  → memo miss
  fib(4)  → memo miss
    fib(3)  → memo miss
      fib(2)  → memo miss
        fib(1) = 1  (base)
        fib(0) = 0  (base)
      memo[2] = 1. return 1.
      fib(1) = 1  (base)
    memo[3] = 2. return 2.
    fib(2) → MEMO HIT! return 1.  ← This would have been another 3 calls
  memo[4] = 3. return 3.
  fib(3) → MEMO HIT! return 2.   ← This would have been 5 calls
memo[5] = 5. return 5.

Without memoization: fib(5) makes 15 calls.
With memoization: fib(5) makes 9 calls — and for fib(40), the difference is billions vs ~80.

Complexity after memoization:

• Each subproblem fib(0) through fib(n) computed exactly once.
• Total calls: O(n).
• Space: O(n) for memo + O(n) call stack = O(n).

Why this matters: This is dynamic programming. DP = recursion + caching subproblem results. You'll see this exact pattern in Chapter 13 applied to harder problems. The insight is always the same: find overlapping subproblems, cache them.

Problem 2: Power Function (Fast Exponentiation)

Problem: Implement pow(x, n) — raise x to the power n.
LeetCode 50. Asked at Google, Amazon, Microsoft.

Four Questions

Q1: What do I have? A base x (float) and exponent n (integer, can be negative).
Q2: What do I want? x^n.
Q3: What is the brute force? Multiply x by itself n times. O(n) multiplications.
Q4: Where is the waste? To compute x^8, naive does 8 multiplications. But x^8 = (x^4)^2 = ((x^2)^2)^2 — only 3 multiplications. The waste is computing halves redundantly.

The Insight: Divide n by 2

x^n = (x^(n/2))^2          if n is even
x^n = x * (x^((n-1)/2))^2  if n is odd

This is divide and conquer. At each level, the problem halves. That gives O(log n) depth.

Implementation

function pow(x, n) {
  // Handle negative exponents: x^-n = 1 / x^n
  if (n < 0) return 1 / pow(x, -n);

  // Base cases
  if (n === 0) return 1;
  if (n === 1) return x;

  // Divide: compute half
  const half = pow(x, Math.floor(n / 2));

  // Combine: square the half
  if (n % 2 === 0) {
    return half * half;         // x^n = (x^(n/2))^2
  } else {
    return half * half * x;     // x^n = x * (x^(n/2))^2
  }
}

Dry Run: pow(2, 10)

pow(2, 10)  n is even
  pow(2, 5)  n is odd
    pow(2, 2)  n is even
      pow(2, 1) = 2  (base case)
    half=2. n=2 even. return 2*2 = 4.    → 2^2 = 4 ✓
    half=4. n=5 odd.  return 4*4*2 = 32. → 2^5 = 32 ✓
  half=32. n=10 even. return 32*32 = 1024. → 2^10 = 1024 ✓

Total: 4 recursive calls vs 10 for naive. For pow(2, 1000000): ~20 calls vs 1,000,000.

Complexity: O(log n) time, O(log n) space (call stack depth).

Shape: Divide and Conquer — problem size halves each level.

Interview signal: Any time you see "do X, n times" and the action can be split (squaring, matrix multiplication, modular arithmetic), think O(log n) via this pattern.

Problem 3: Flatten Nested Array

Problem: Given a nested array of arbitrary depth, return a flat array.
flatten([1, [2, [3, 4]], 5]) → [1, 2, 3, 4, 5]

This is a warm-up. But it teaches you to recognize tree structure in non-obvious problems.

Four Questions

Q1: What do I have? An array where each element is either a number or another array (possibly nested).
Q2: What do I want? All numbers in the same order, in a single flat array.
Q3: What is the brute force? Walk every element. If it's a number, include it. If it's an array, flatten it recursively and include its elements.
Q4: Where is the waste? None — every element must be visited exactly once. This is O(n) where n is the total number of leaf values.

Implementation

function flatten(arr) {
  const result = [];

  for (const item of arr) {
    if (Array.isArray(item)) {
      // item is an array → flatten it, spread results into result
      result.push(...flatten(item));  // recursive leap of faith
    } else {
      // item is a number → include it directly
      result.push(item);
    }
  }

  return result;
}

Dry Run: flatten([1, [2, [3, 4]], 5])

flatten([1, [2, [3, 4]], 5])
  item=1: not array → push 1. result=[1].
  item=[2, [3, 4]]: array →
    flatten([2, [3, 4]])
      item=2: not array → push 2. result=[2].
      item=[3, 4]: array →
        flatten([3, 4])
          item=3: not array → push 3. result=[3].
          item=4: not array → push 4. result=[3, 4].
          return [3, 4].
      push ...[3, 4] → result=[2, 3, 4].
      return [2, 3, 4].
  push ...[2, 3, 4] → result=[1, 2, 3, 4].
  item=5: not array → push 5. result=[1, 2, 3, 4, 5].
  return [1, 2, 3, 4, 5].

Why this matters: DOM trees, JSON objects, file directories — they're all this structure. The recursive leap of faith — flatten(item) returns the correct flat array for the sub-array — is the key.

Problem 4: Generate All Subsets (Power Set)

Problem: Given an array of distinct integers, return all possible subsets.
subsets([1, 2, 3]) → [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]]
LeetCode 78. Foundation for all backtracking problems.

Four Questions

Q1: What do I have? An array of n distinct integers.
Q2: What do I want? All 2^n subsets (including empty set and full set).
Q3: What is the brute force? For each element, decide: include or exclude. These are binary decisions made for each element.
Q4: Where is the waste? None — we need all 2^n subsets, so we must generate all of them. O(2^n * n) is unavoidable (2^n subsets, each of up to n elements to copy).

The Include/Exclude Pattern

For each element at index i, there are exactly two choices:

1. Include arr[i] in the current subset being built.
2. Exclude arr[i] from the current subset being built.

After making that choice, recurse for arr[i+1].

This is a binary tree of decisions. Each leaf is one complete subset.

                      []          ← start, index=0
                /           \
           include 1       exclude 1
              [1]              []          ← index=1
            /    \           /    \
       include 2  excl 2  incl 2  excl 2
          [1,2]    [1]    [2]     []       ← index=2
         /   \    /  \   /  \    /  \
       +3   -3  +3  -3  +3  -3  +3  -3
      [1,2,3][1,2][1,3][1] [2,3][2] [3]  []

8 leaves for 3 elements = 2^3. ✓

Implementation

function subsets(nums) {
  const result = [];

  function backtrack(index, current) {
    // Every path through the tree is a valid subset
    // When we've considered all elements, we have a complete subset
    if (index === nums.length) {
      result.push([...current]);  // copy current state
      return;
    }

    // Choice 1: include nums[index]
    current.push(nums[index]);
    backtrack(index + 1, current);

    // Choice 2: exclude nums[index] (undo the include)
    current.pop();
    backtrack(index + 1, current);
  }

  backtrack(0, []);
  return result;
}

Dry Run: subsets([1, 2])

backtrack(0, [])
  Include 1: current=[1]
    backtrack(1, [1])
      Include 2: current=[1, 2]
        backtrack(2, [1,2])  → index===length → result.push([1,2])
      Pop 2: current=[1]
      Exclude 2:
        backtrack(2, [1])    → index===length → result.push([1])
  Pop 1: current=[]
  Exclude 1:
    backtrack(1, [])
      Include 2: current=[2]
        backtrack(2, [2])    → index===length → result.push([2])
      Pop 2: current=[]
      Exclude 2:
        backtrack(2, [])     → index===length → result.push([])

result = [[1,2], [1], [2], []]

(Order differs from problem statement — both orderings are valid.)

Key observations:

1. [...current] — we spread-copy the array. If you push current directly, all entries in result point to the same array object and will be mutated. Always copy.
2. current.pop() is the undo step. This is "backtracking" — you explore a path, then undo your choice to explore the other path. Chapter 11 (Backtracking) is entirely this pattern.
3. The current array is shared state — one array, modified in place as we traverse the decision tree.

Complexity: 2^n subsets × O(n) to copy each = O(n × 2^n) time, O(n) space for call stack (depth = n).

Problem 5: Merge Sort — Full Implementation (From Scratch)

Problem: Implement merge sort.
mergeSort([5, 2, 4, 1, 3]) → [1, 2, 3, 4, 5]

You saw merge sort in Chapter 4. Now implement it from scratch without looking at notes.

The Contract

mergeSort(arr) returns a new sorted array. It does NOT sort in place.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;

  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) {
      result.push(left[l++]);
    } else {
      result.push(right[r++]);
    }
  }

  // Append remaining elements
  while (l < left.length) result.push(left[l++]);
  while (r < right.length) result.push(right[r++]);

  return result;
}

Dry Run: mergeSort([3, 1, 4, 1, 5])

mergeSort([3, 1, 4, 1, 5])
  left  = mergeSort([3, 1])
    left  = mergeSort([3]) → [3]
    right = mergeSort([1]) → [1]
    merge([3],[1]):
      l=3, r=1: 1<3 → push 1, r=1 (exhausted)
      remaining left: push 3.
      → [1, 3]
  right = mergeSort([4, 1, 5])
    left  = mergeSort([4]) → [4]
    right = mergeSort([1, 5])
      left  = mergeSort([1]) → [1]
      right = mergeSort([5]) → [5]
      merge([1],[5]):
        l=1,r=5: 1<5 → push 1, l exhausted
        remaining right: push 5.
        → [1, 5]
    merge([4],[1,5]):
      l=4, r=1: 1<4 → push 1, r=1.
      l=4, r=5: 4<5 → push 4, l exhausted.
      remaining right: push 5.
      → [1, 4, 5]
  merge([1,3],[1,4,5]):
    l=1, r=1: 1<=1 → push left[0]=1, l=1.
    l=3, r=1: 1<3 → push right[0]=1, r=1.
    l=3, r=4: 3<4 → push 3, l exhausted.
    remaining right: push 4, 5.
    → [1, 1, 3, 4, 5]

Result: [1, 1, 3, 4, 5] ✓

Note the stability: When left[l] <= right[r], we prefer the left. This means equal elements from the left half always appear before equal elements from the right half — merge sort is stable. The two 1s: the one from position 0 (left half) appears before the one from position 3 (right half). Stability matters when sorting objects by one key where original order should be preserved for ties.

Problem 6: Binary Search — Recursive Version

Problem: Given a sorted array and a target, return the index. Return -1 if not found.
binarySearch([1, 3, 5, 7, 9, 11], 7) → 3

Four Questions

Q1: What do I have? A sorted array and a target.
Q2: What do I want? The index of target, or -1.
Q3: What is the brute force? Linear scan. O(n).
Q4: Where is the waste? We check the midpoint and know which half the target is in. The other half can be discarded entirely. This is O(log n) division.

Implementation

function binarySearch(arr, target, low = 0, high = arr.length - 1) {
  // Base case: search space is empty
  if (low > high) return -1;

  const mid = Math.floor((low + high) / 2);

  if (arr[mid] === target) return mid;     // found

  if (arr[mid] < target) {
    return binarySearch(arr, target, mid + 1, high);  // search right half
  } else {
    return binarySearch(arr, target, low, mid - 1);   // search left half
  }
}

Dry Run: binarySearch([1, 3, 5, 7, 9, 11], 7)

binarySearch([1,3,5,7,9,11], 7, low=0, high=5)
  mid = 2. arr[2] = 5. 5 < 7 → search right half.
  binarySearch([1,3,5,7,9,11], 7, low=3, high=5)
    mid = 4. arr[4] = 9. 9 > 7 → search left half.
    binarySearch([1,3,5,7,9,11], 7, low=3, high=3)
      mid = 3. arr[3] = 7. 7 === 7 → return 3. ✓

Complexity: O(log n) time, O(log n) space (log n stack frames for log n recursive calls).

Note: The iterative version of binary search is O(log n) time, O(1) space — no stack frames needed. Chapter 9 covers this in depth. For now, the recursive version is easier to reason about.

Problem 7: Climbing Stairs

Problem: You can climb 1 or 2 stairs at a time. How many distinct ways can you reach the n-th stair?
climbStairs(3) → 3 (ways: [1,1,1], [1,2], [2,1])
LeetCode 70. One of the most commonly asked interview problems.

Four Questions

Q1: What do I have? n stairs. Each step you can take 1 or 2 stairs.
Q2: What do I want? Number of distinct ways to reach stair n.
Q3: What is the brute force? From stair 0, try taking 1 step (land on 1) or 2 steps (land on 2). From each position, do the same. Count paths that reach exactly n.
Q4: Where is the waste? The number of ways to reach stair k is computed multiple times across different paths. It only depends on k, not on how we got here.

The Recursive Structure

To reach stair n, your last step was either:

• A 1-step from stair n-1 (so: how many ways to reach n-1?)
• A 2-step from stair n-2 (so: how many ways to reach n-2?)

Therefore: ways(n) = ways(n-1) + ways(n-2).

This is Fibonacci. Base cases: ways(1) = 1 (only [1]), ways(2) = 2 ([1,1] or [2]).

function climbStairs(n, memo = {}) {
  if (n <= 0) return 0;
  if (n === 1) return 1;
  if (n === 2) return 2;
  if (memo[n]) return memo[n];
  memo[n] = climbStairs(n - 1, memo) + climbStairs(n - 2, memo);
  return memo[n];
}

Dry Run: climbStairs(5)

climbStairs(5)
  = climbStairs(4) + climbStairs(3)
  climbStairs(4)
    = climbStairs(3) + climbStairs(2)
    climbStairs(3)
      = climbStairs(2) + climbStairs(1)
      = 2 + 1 = 3. memo[3]=3.
    memo[3] HIT for second climbStairs(3) call.
    climbStairs(2) = 2.
    climbStairs(4) = 3 + 2 = 5. memo[4]=5.
  climbStairs(3) = memo[3] = 3. (HIT)
  climbStairs(5) = 5 + 3 = 8.

climbStairs(n) for n=1..8 = [1, 2, 3, 5, 8, 13, 21, 34] — the Fibonacci sequence shifted by two.

Why this matters: This is the first pure DP problem most candidates see. The insight — "to reach here, where could I have come from?" — is the DP recurrence design pattern. You'll use it constantly in Chapter 13.

Problem 8: Sort Colors (Dutch National Flag — Divide Strategy)

Problem: Given an array with values 0, 1, 2 (representing red, white, blue), sort them in place so all 0s come first, then 1s, then 2s.
sortColors([2, 0, 2, 1, 1, 0]) → [0, 0, 1, 1, 2, 2]
LeetCode 75. Classic partition problem.

Four Questions

Q1: What do I have? An array of {0, 1, 2} values.
Q2: What do I want? Sort in place: 0s, then 1s, then 2s.
Q3: What is the brute force? Run merge sort or quicksort. O(n log n). Or count 0s, 1s, 2s and fill. O(n) two-pass.
Q4: Where is the waste? A two-pass counting solution scans twice. We can do it in one pass using three pointers.

This is a partitioning problem — directly from quicksort's partition idea. Three regions: [0, low) = 0s, [low, mid) = 1s, [high+1, end] = 2s, [mid, high] = unknown.

function sortColors(nums) {
  let low = 0;     // boundary of 0-region
  let mid = 0;     // current element
  let high = nums.length - 1;  // boundary of 2-region

  while (mid <= high) {
    if (nums[mid] === 0) {
      // Swap with low boundary, advance both
      [nums[low], nums[mid]] = [nums[mid], nums[low]];
      low++;
      mid++;
    } else if (nums[mid] === 1) {
      // 1 belongs in middle, just advance
      mid++;
    } else {
      // 2: swap with high boundary, don't advance mid (need to re-examine)
      [nums[mid], nums[high]] = [nums[high], nums[mid]];
      high--;
    }
  }
}

Dry Run: sortColors([2, 0, 2, 1, 1, 0])

Initial: [2, 0, 2, 1, 1, 0], low=0, mid=0, high=5

mid=0: nums[0]=2 → swap nums[0],nums[5]: [0,0,2,1,1,2]. high=4.
  State: [0, 0, 2, 1, 1, 2], low=0, mid=0, high=4

mid=0: nums[0]=0 → swap nums[0],nums[0]: [0,0,2,1,1,2]. low=1, mid=1.
  State: [0, 0, 2, 1, 1, 2], low=1, mid=1, high=4

mid=1: nums[1]=0 → swap nums[1],nums[1]: [0,0,2,1,1,2]. low=2, mid=2.
  State: [0, 0, 2, 1, 1, 2], low=2, mid=2, high=4

mid=2: nums[2]=2 → swap nums[2],nums[4]: [0,0,1,1,2,2]. high=3.
  State: [0, 0, 1, 1, 2, 2], low=2, mid=2, high=3

mid=2: nums[2]=1 → mid=3.
  State: [0, 0, 1, 1, 2, 2], low=2, mid=3, high=3

mid=3: nums[3]=1 → mid=4.
  State: [0, 0, 1, 1, 2, 2], low=2, mid=4, high=3

mid=4 > high=3. Loop ends.

Result: [0, 0, 1, 1, 2, 2] ✓

Why mid doesn't advance when we swap with high: The element that came from nums[high] is unknown — it could be 0, 1, or 2. We need to examine it next. But when we swap with nums[low], we know nums[low] was a 1 (everything below mid is either a 0 or a 1, and everything below low is a 0), so it's safe to advance mid.

Complexity: O(n) time, O(1) space. One pass.

Connection: This is quicksort's partition generalized to three values instead of two. Dutch National Flag is the name; Dijkstra invented it.

Pattern Recognition Cheat Sheet

You see a recursion problem. Ask:

1. Does f(n) depend on f(n-1)?
   → Linear recursion. Write base case, write the dependency.

2. Does f(n) depend on f(n-1) AND f(n-2)?
   → Fibonacci shape. Memoize immediately.

3. Are we making a binary CHOICE at each step?
   → Include/exclude pattern (subsets, backtracking).
   → Two recursive calls: one with choice made, one without.
   → Always undo the choice before the second call (backtrack).

4. Are we dividing the input in half?
   → Divide and conquer.
   → T(n) = 2T(n/2) + O(n merge) → O(n log n)
   → T(n) = T(n/2) + O(1) → O(log n)

5. Are we picking a pivot and partitioning?
   → Quicksort / quickselect pattern.
   → O(n) partition, O(log n) average depth.

5 Practice Problems

1. Trace and Predict

function f(n) {
  if (n <= 0) return 0;
  if (n % 2 === 0) return f(n / 2);
  return 1 + f(n - 1);
}

Trace f(12). What does this function compute? What is its time complexity? What would happen on f(0)? Can this infinitely recurse for any positive even integer? Why or why not?

2. Find the Waste

function countPaths(m, n) {
  if (m === 0 || n === 0) return 1;
  return countPaths(m - 1, n) + countPaths(m, n - 1);
}

countPaths(3, 3) counts paths in a grid from top-left to bottom-right. Draw the call tree for countPaths(3, 3). Identify repeated subproblems. Add memoization. What is the complexity before and after?

3. Failure Analysis

A developer writes:

function subsets(nums) {
  if (nums.length === 0) return [[]];
  const rest = subsets(nums.slice(1));
  return [...rest, ...rest.map(s => [nums[0], ...s])];
}

Does this produce correct subsets? Trace subsets([1, 2]). Is it correct? Now identify the time complexity — specifically, how many times is rest.map(...) called for the full recursion, and what does that cost?

4. Design Under Constraints

Design a recursive function treeHeight(root) where root = { val, left, right } or null. Return the height (max depth from root to any leaf). Then identify: what is the time complexity? What is the space complexity? What is the worst-case input (a path to a leaf that maximizes space)?

(We haven't covered trees yet — but you have enough to figure this out. If a node is null, height is 0. Otherwise, height is 1 + max(height(left), height(right)). Try it.)

5. Reach Beyond

Implement permutations([1, 2, 3]) → all arrangements: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]. There are n! permutations of n elements.

Hint: At each recursive step, pick one element to go first. Recurse on the remaining elements. Use the include/exclude pattern but pick one element per slot instead of making a binary decision per element.

What is the time complexity? The space complexity? (For 10 elements: 10! = 3,628,800 permutations.)

Connect Forward

Chapter 5 — Two Pointers uses iterative movement of two indices across an array. No recursion. But Chapter 8 (Linked Lists) will use recursion again — reverse a linked list recursively is a canonical problem. Chapter 10 (Trees) is 90% recursion. Chapter 11 (Backtracking) is subsets from this chapter, generalized to arbitrary constraints.

The subsets pattern — "at each element, include or exclude" — is the backbone of backtracking. Combination Sum, N-Queens, Sudoku Solver — they all use this pattern with one addition: a constraint that prunes branches early.