Recursion & Backtracking

Recursion is solving a problem by assuming you can already solve a smaller version of it, then combining that answer with a little work of your own. You do not trace the whole thing in your head — you trust the smaller call, describe how one step shrinks the problem, and define where it stops.

Every recursive function needs exactly two things: a base case (a problem small enough to answer directly, with no further recursion) and a recursive case (reduce the problem and call yourself on the smaller piece). Miss the base case and you recurse forever; get the reduction wrong and you never reach it.

The call stack

Every active call gets a stack frame holding its local variables and its place in the code. A call that recurses d levels deep before returning stacks up d frames — that is where recursion's O(d) space comes from, even when it returns a single number. Overflow that stack (too deep, or a missing base case) and you get the dreaded Maximum call stack size exceeded.

function factorial(n) {
  if (n <= 1) return 1        // base case: stop here
  return n * factorial(n - 1) // recursive case: shrink by 1
}
// factorial(4) = 4 * factorial(3)
//              = 4 * 3 * factorial(2)
//              = 4 * 3 * 2 * factorial(1)  <- base case, unwind

Backtracking: choose → explore → un-choose

Backtracking is recursion for building all valid arrangements. At each step you choose an option, explore the consequences by recursing, then un-choose — undo the choice so the next branch starts clean. That undo is what makes one shared state (a partial path) safe to reuse across every branch of the tree.

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

  function backtrack(start) {
    result.push([...path])            // record this subset (a copy!)
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i])              // choose
      backtrack(i + 1)               // explore the rest
      path.pop()                      // un-choose (backtrack)
    }
  }

  backtrack(0)
  return result
}

Subsets, permutations, combinations

The three classic backtracking families differ only in how they iterate. Subsets pass i + 1 so each element is used at most once and order does not matter. Combinations are subsets of a fixed size k — same shape, plus a base case when path.length === k. Permutations care about order, so they loop over all elements each time and mark which are already used instead of advancing a start index.

• Subsets — every combination of "in or out"; 2ⁿ results.
• Combinations — choose k of n, order-independent.
• Permutations — all orderings; n! results, track a used[] set.

Pruning: stop bad branches early

Backtracking explores a tree, and that tree can be enormous. Pruning means cutting a branch the moment it cannot lead to a valid answer — skip a duplicate, bail when a running sum already exceeds the target, return early when a constraint breaks. A good prune turns an intractable search into a fast one without changing the answer.

When recursion overlaps: the road to DP

Sometimes the recursion tree solves the same subproblem over and over. Naive fib(n) recomputes fib(n − 2) in both of its branches, and those overlaps multiply into an O(2ⁿ) blowup. This signal — overlapping subproblems — is exactly when you cache results (memoisation) or fill a table bottom-up. That optimisation is dynamic programming, and it is the natural next step from recursion.