Recursion and Backtracking

Recursion is the programming mirror of induction: solve the smallest case, and express every other case in terms of a smaller one. Backtracking is recursion for search — explore a choice, and if it dies, undo it and try the next. Together they generate a large family of interview questions with one shared skeleton.

Designing a recursion

Three questions, answered before typing: What's the base case? What's the recursive step (how does the problem shrink)? What state travels down the calls? Get those right and the code writes itself:

def total_size(folder):
    return folder.size + sum(total_size(f) for f in folder.subfolders)

The failure modes are equally standard: a missing or wrong base case (infinite recursion), the state not actually shrinking, and — the performance one — overlapping subproblems, which is the cue to add memoization and land in the dynamic-programming lesson. Python-specific: recursion depth caps around 1,000, and there's no tail-call optimization — deep linear recursions should become loops (the invariant/monovariant discipline from the proofs lesson tells you the loop terminates).

Backtracking: choose, explore, unchoose

For problems asking to enumerate or search configurations — subsets, permutations, board placements — the template:

def backtrack(path, options):
    if is_complete(path):
        results.append(path.copy())
        return
    for choice in options:
        if not valid(choice, path):   # prune early
            continue
        path.append(choice)           # choose
        backtrack(path, next_options) # explore
        path.pop()                    # unchoose

The three canonical instantiations, each a stock interview question: subsets ($2^n$: each element in or out), permutations ($n!$: pick each unused element next), and N-Queens (place a queen per row; prune on column/diagonal conflicts). State the output size before coding — an interviewer hearing "there are $2^{20}$ subsets, about a million, so enumeration is fine; at $n = 50$ it isn't" knows you've connected this to the complexity ladder.

Pruning: the difference between toy and tool

Raw backtracking is brute force; pruning — rejecting partial solutions the moment they're doomed — is what makes it viable. N-Queens without pruning at $n=8$ explores $8^8 \approx 17$M placements; with row/column/diagonal pruning, a few thousand. The quant-relevant framing: pruning is bounding (the inequalities lesson applied to search), and its industrial-strength version — bound the best possible completion, abandon branches that can't beat the incumbent — is branch-and-bound, the engine inside integer-programming solvers used for portfolio construction with lot-size and cardinality constraints. Sudoku, expression-target puzzles ("make 24 from these four numbers"), and constraint games at interviews are all this template plus problem-specific pruning.

Recursion in the wild

Parsing nested structures (JSON, expressions — matched to the stack lesson: recursion is a stack), tree traversals, divide-and-conquer (mergesort, quickselect), and the game-theory lesson's minimax — evaluating a game tree is recursion with alternating min/max, and alpha-beta pruning is, once more, "abandon dominated branches."

The interview version

"Print all valid combinations of n pairs of parentheses." — Backtrack with two counters (opens used, closes used); prune when closes would exceed opens; output size is the Catalan number from the combinatorics lesson — naming that earns the bonus point. "Why is your solution exponential, and is that okay?" — Because the output is exponential; enumeration can't beat its own output size. Knowing when exponential is inherent versus when memoization collapses it — that judgment is the actual exam.