Recursion and backtracking

Why it matters

Many problems are naturally recursive: trees, nested structures, divide and conquer, and every "generate all valid configurations" task. Writing recursion well means specifying exactly what a call returns and then trusting it for smaller inputs. Backtracking is recursion over a tree of decisions with undo; it is how constraint solvers, parsers and search procedures work. In interviews it tests clarity about state and honest complexity analysis, since the output itself is often exponential.

Core ideas

Recursion as induction. Write the contract first, for example "height(node) returns the number of nodes on the longest downward path from node, and 0 for an empty tree". Handle the base case, then assume the contract holds for smaller inputs. Correctness is an induction on input size; termination needs every call to move toward a base case. MIT 6.006 classifies recursive algorithms by the shape of their call graph: a star for brute force, a chain for decrease and conquer, a tree for divide and conquer, and a DAG with shared subproblems for dynamic programming.

Cost. Draw the recursion tree and add up the work in its nodes. Space is the maximum depth times the frame size, plus anything else allocated. Passing copies (path + [x], string slices) adds O(length) per call; sharing one mutable path and undoing changes avoids that.

Pattern: Backtracking search.

def backtrack(state):
    if is_complete(state):
        record(copy_of(state))
        return
    for choice in choices(state):
        if not feasible(state, choice):
            continue                 # prune
        apply(choice, state)
        backtrack(state)
        undo(choice, state)

Invariant: state is identical on entry and exit; only the recursive call sees the applied choice. The two classic bugs are forgetting to undo and recording a reference to the mutable path instead of a copy. In Go, appending to a shared slice can also overwrite results you already stored.

Decision-tree shapes.

• Subsets: at index i, include or exclude a[i]; 2ⁿ leaves, and copying each subset makes it O(n × 2ⁿ).
• Combinations and combination sums: choose the next element from index start onward so each set appears once in a canonical order; recurse with i when reuse is allowed and i + 1 when it is not.
• Permutations: choose any unused element; n! leaves, O(n × n!) with copying.
• Duplicate values: sort first, then at the same depth skip a value equal to its previous sibling (i > start and a[i] == a[i - 1]).

Pruning. Cut branches that cannot succeed: stop when the remaining target goes negative (with sorted positive candidates you can break out of the loop), track used columns and diagonals in N-Queens, or add a closing parenthesis only while one is still open. Pruning rarely improves the worst-case bound, but it can shrink the explored tree dramatically.

Grids. For path search in a grid (Word Search), mark a cell as visited before recursing and restore it afterwards, so one path never reuses a cell while other paths still can.

When it becomes dynamic programming. If the same subproblem (say, the same remaining index and remaining target) recurs and its answer does not depend on how you reached it, memoize it. If the task is to list every configuration, memoization helps little: the output size is the cost.

Common misconceptions

• "Recursion is risky, so avoid it." It is often the clearest correct solution; know the depth and your language's limit, and convert to an explicit stack when depth can reach tens of thousands.
• "Backtracking is O(2ⁿ)." State the bound from the decision tree and the output, for example O(n × 2ⁿ) for subsets or O(n × n!) for permutations; copying counts.
• "Recording the current path is enough." Record a copy; the shared path keeps changing as the search continues.
• "A global visited set prevents duplicate outputs." Duplicates caused by repeated input values need sorting and sibling skipping; a global visited set can wrongly block valid paths.
• "Pruning improves the worst case." Usually it improves typical behavior only; say so when asked.

How to approach it

Before coding, name the state, the choices at each step, the completion test and the pruning rule. Draw the first two levels of the decision tree for a tiny input and count leaves to get the bound. Test an empty input and an input with duplicates. Interviewers typically probe the complexity of exponential outputs, duplicate handling and whether memoization applies. Practicing the template on varied problems transfers to new ones; memorizing particular question lists does not.