# Recursion & Backtracking — Part 1: The Pattern

A recursive function solves a problem by solving **smaller instances of the same problem**. Write it in three parts: a **base case** that stops, a **recursive case** that shrinks the input, and a **leap of faith**: assume the recursive call returns the right answer for the smaller input, and only think about how to combine it. **Backtracking** is recursion that builds a solution step by step, explores every valid choice at each step, and **undoes** each choice before trying the next. It's how you generate subsets, permutations, combinations and board placements.

![The include/exclude decision tree that generates all subsets](diagrams/01-decision-tree.svg)

## 1. Writing a Recursive Function

```text
def solve(problem):
    if problem is tiny:            # base case: answer directly
        return direct_answer
    sub = solve(smaller(problem))  # trust it works
    return combine(sub, problem)
```

Questions to answer before coding:

1. **What does the function return** for an input? Say it in one sentence ("the max depth of this subtree").
2. **What is the smallest input** and its answer (empty tree → 0, empty string → true)?
3. **How does the input shrink** each call, so you're sure it reaches the base case?

## 2. The Backtracking Template

```typescript
function subsetsTemplate(nums: number[]): number[][] {
  const res: number[][] = [], path: number[] = [];
  const backtrack = (start: number): void => {
    res.push([...path]);                 // record a copy
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);                // choose
      backtrack(i + 1);                  // explore
      path.pop();                        // un-choose
    }
  };
  backtrack(0);
  return res;
}
```

```python
def subsets_template(nums):
    res, path = [], []

    def backtrack(start):
        res.append(path[:])               # record a copy of the current choice list
        for i in range(start, len(nums)):
            path.append(nums[i])          # 1. choose
            backtrack(i + 1)              # 2. explore
            path.pop()                    # 3. un-choose (restore state)

    backtrack(0)
    return res
```

Every backtracking problem is this template with three decisions:

| Decision | Subsets | Permutations | Combination Sum | N-Queens |
|---|---|---|---|---|
| **What is a choice?** | include `nums[i]` | place an unused number next | add a candidate (reusable) | queen in a column of this row |
| **When is the path complete?** | always record | `len(path) == n` | `remaining == 0` | `row == n` |
| **What prunes a branch?** | none | used set | `remaining < 0` (sort to stop early) | column/diagonal attacked |

## 3. Complexity of Backtracking

Count the **leaves** of the decision tree and the work to copy each solution:

- subsets: 2ⁿ leaves × O(n) copy → **O(n · 2ⁿ)**
- permutations: n! leaves × O(n) → **O(n · n!)**
- combinations of size k: C(n, k) × O(k)

These are exponential by nature: the output itself is that big. Interviewers care that you **prune** early (sort candidates and `break` when they exceed the target) and that you don't copy lists unnecessarily.

## 4. Avoiding Duplicates

When the input has duplicates (`[1, 2, 2]`), **sort first** and skip a value equal to its predecessor **at the same depth**: `if i > start and nums[i] == nums[i - 1]: continue`. That removes duplicate branches without a hash set of results.

## Under the Hood: The Call Stack

Each call pushes a **stack frame** holding its parameters and local variables; returning pops it. Backtracking works because the shared `path` list is modified on the way down and restored on the way up, exactly mirroring the stack. Deep recursion can overflow: Python's default limit is about 1,000 frames (`RecursionError`), JavaScript engines allow roughly 10,000 to 25,000 depending on frame size, and .NET throws an uncatchable `StackOverflowException` around 1 MB of stack. For inputs deeper than a few thousand levels (a linked-list-shaped tree, a long path in a grid), convert to an iterative version with an explicit stack.

## Common Pitfalls

1. **Appending `path` instead of a copy** (`res.append(path)`): every result ends up as the same, finally empty list.
2. **Forgetting to undo** a choice (missing `path.pop()` or not unmarking `used[i]`).
3. **No base case or a base case that's never reached** → infinite recursion.
4. **Duplicate results** from duplicate inputs: sort and skip at the same depth.
5. **Not pruning:** exploring branches that already exceed the target.

## Quick Reference

```text
recursion: base case → recurse on smaller input → combine (trust the call)
backtrack(state): if complete: record copy; for choice in choices: if valid: choose; backtrack; unchoose
dupes: sort; if i > start and a[i] == a[i-1]: continue
subsets O(n·2^n) · permutations O(n·n!) · stack depth = recursion depth
```