Recursion — The Complete Guide

function solve(input, index): Result {
  // 1. Base case — smallest input you can answer directly
  if (index >= input.length) return baseValue;

  // 2. Recursive case — solve for the rest
  const subResult = solve(input, index + 1);

  // 3. Combine — merge current element with sub-result
  return combine(input[index], subResult);
}

// Examples:
// Factorial: base = 1, combine = n * factorial(n-1)
// Sum array: base = 0, combine = arr[i] + sum(arr, i+1)
// Reverse list: base = null, combine = reverse rest, then append head

// When to use: factorial, fibonacci, reverse linked list,
// sum of array, string reversal, palindrome check

function solve(input, left, right): Result {
  // 1. Base case — single element or empty
  if (left >= right) return baseValue;

  // 2. Divide — find the midpoint
  const mid = Math.floor((left + right) / 2);

  // 3. Conquer — solve both halves recursively
  const leftResult = solve(input, left, mid);
  const rightResult = solve(input, mid + 1, right);

  // 4. Combine — merge the two results
  return merge(leftResult, rightResult);
}

// Examples:
// Merge sort: split, sort halves, merge sorted halves
// Maximum subarray (Kadane variant): max of left, right, or crossing
// Count inversions: merge sort + count during merge step

// When to use: merge sort, quicksort, binary search,
// closest pair of points, power(x, n)

function solve(node: TreeNode | null): Result {
  // 1. Base case — null node
  if (node === null) return baseValue;

  // 2. Recurse on children
  const leftResult = solve(node.left);
  const rightResult = solve(node.right);

  // 3. Combine — use current node + children's results
  return combine(node.val, leftResult, rightResult);
}

// Examples:
// Max depth: base = 0, combine = 1 + max(left, right)
// Is balanced: base = true/0, combine = check |leftH - rightH| ≤ 1
// Diameter: base = 0, combine = update global max with leftH + rightH
// Invert tree: base = null, combine = swap left and right

// When to use: max depth, diameter, balanced check, LCA,
// path sum, invert tree, serialize/deserialize

function backtrack(state, choices, result): void {
  // 1. Base case — valid complete solution
  if (isComplete(state)) {
    result.push([...state]); // save a copy
    return;
  }

  for (const choice of choices) {
    // 2. Prune — skip invalid choices early
    if (!isValid(choice, state)) continue;

    // 3. Choose — add to current state
    state.push(choice);

    // 4. Explore — recurse with updated state
    backtrack(state, remainingChoices, result);

    // 5. Unchoose — remove to try next option
    state.pop();
  }
}

// Examples:
// Subsets: choose to include or exclude each element
// Permutations: choose each unused element for the next position
// N-Queens: choose a column for each row, prune conflicts
// Combination Sum: choose a number, recurse with remaining target

// When to use: generate all permutations/combinations/subsets,
// N-Queens, Sudoku solver, word search, palindrome partitioning

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

  function backtrack(index: number, current: number[]) {
    // Base case: processed all elements
    if (index === nums.length) {
      result.push([...current]); // save a copy
      return;
    }

    // Choice 1: EXCLUDE nums[index]
    backtrack(index + 1, current);

    // Choice 2: INCLUDE nums[index]
    current.push(nums[index]);
    backtrack(index + 1, current);
    current.pop(); // unchoose (backtrack)
  }

  backtrack(0, []);
  return result;
}
// Time: O(2^n × n) — 2^n subsets, each takes O(n) to copy
// Space: O(n) recursion depth + O(2^n × n) for output
// Key: each element has exactly 2 choices → 2^n total subsets

function mergeSort(arr: number[]): number[] {
  // Base case: single element is already sorted
  if (arr.length <= 1) return arr;

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

  // Conquer (merge two sorted arrays)
  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }

  return [...result, ...a.slice(i), ...b.slice(j)];
}
// Time: O(n log n) — log n levels, O(n) work per level
// Space: O(n) for the merge step
// Key: splitting gives log(n) depth; merging does O(n) per level

function generateParenthesis(n: number): string[] {
  const result: string[] = [];

  function backtrack(current: string, open: number, close: number) {
    // Base case: used all parentheses
    if (current.length === 2 * n) {
      result.push(current);
      return;
    }

    // Choice 1: add '(' if we haven't used all n
    if (open < n) {
      backtrack(current + "(", open + 1, close);
    }

    // Choice 2: add ')' if it won't create invalid sequence
    if (close < open) {
      backtrack(current + ")", open, close + 1);
    }
  }

  backtrack("", 0, 0);
  return result;
}
// Time: O(4^n / √n) — the n-th Catalan number
// Space: O(n) recursion depth
// Key: the constraint (close < open) ensures we never have
// more closing parens than opening ones at any point.

factorial(5)
├── 5 * factorial(4)
│   ├── 4 * factorial(3)
│   │   ├── 3 * factorial(2)
│   │   │   ├── 2 * factorial(1)
│   │   │   │   └── return 1          ← base case
│   │   │   └── return 2 * 1 = 2      ← unwinding
│   │   └── return 3 * 2 = 6          ← unwinding
│   └── return 4 * 6 = 24             ← unwinding
└── return 5 * 24 = 120               ← unwinding

Answer: 120

Key observations:
- The call stack grows 5 levels deep (one per recursive call)
- Base case (n=1) returns directly — no more calls
- Results "bubble up" as each call returns
- Each level does O(1) work → total O(n) time, O(n) stack space

myPow(2, 10)
├── half = myPow(2, 5)
│   ├── half = myPow(2, 2)
│   │   ├── half = myPow(2, 1)
│   │   │   └── return 2              ← base case (n=1)
│   │   └── return 2 * 2 = 4          ← even: half * half
│   └── return 4 * 4 * 2 = 32         ← odd: half * half * x
└── return 32 * 32 = 1024             ← even: half * half

Answer: 1024

Key observations:
- Only 4 recursive calls for n=10 (vs 10 multiplications in brute force)
- Each call halves n: 10 → 5 → 2 → 1
- Odd n: multiply an extra x. Even n: just square the half.
- Stack depth: O(log n) = O(log 10) ≈ 4 levels

subsets([1, 2, 3])

                          []
                   /              \
              exclude 1          include 1
                []                  [1]
              /      \           /       \
          excl 2    incl 2    excl 2    incl 2
           []        [2]       [1]      [1,2]
          / \       / \      / \      / \
        e3  i3    e3  i3   e3  i3   e3  i3
        []  [3]  [2] [2,3] [1] [1,3] [1,2] [1,2,3]

Leaves (all subsets): [], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]

Answer: [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

Key observations:
- Each level makes a binary choice: include or exclude one element
- 3 elements → 3 levels → 2³ = 8 leaves = 8 subsets
- The tree has depth n (number of elements)
- Backtracking: after exploring "include", we pop the element and explore "exclude"

Is the data structure a tree or graph?
├── YES → Tree/Graph DFS recursion (Template 3)
│         Base case: null node. Recurse on children. Combine results.
└── NO  → Can you define f(n) in terms of f(smaller)?
          ├── YES → Can you split the problem in HALF?
          │         ├── YES → Divide & Conquer (Template 2)
          │         │         Merge sort, power(x,n), closest pair
          │         └── NO  → Linear Recursion (Template 1)
          │                   Factorial, reverse list, fibonacci
          └── NO  → Do you need to generate ALL valid configurations?
                    ├── YES → Backtracking (Template 4)
                    │         Subsets, permutations, N-Queens, sudoku
                    └── NO  → Are there overlapping subproblems?
                              ├── YES → Recursion + Memoization (→ DP)
                              │         Fibonacci, coin change, climbing stairs
                              └── NO  → Recursion probably isn't needed
                                        → Consider iteration, greedy, or hashing