09 — Recursion, backtracking and induction

You are comfortable with recursion. The gap is the second half of what the email asks for: "you should be able to take a given algorithm and prove inductively that it will do what you claim it will do." Almost nobody prepares that, and it converts "I tested it" into an argument.

Prereqs: 01 · Reading: 6 min · Cards: 9

The map

Three related things. Recursion is the tool; backtracking is recursion that undoes its choices, which is how you enumerate; and induction is how you justify either one when asked. The first two you already write. The third is what you say when the interviewer asks "how do you know that's correct?" — and answering with an invariant instead of "I ran the examples" is a visible difference in level.

The connection is structural: a recursive algorithm and an inductive proof have the same shape. Base case, a hypothesis about smaller inputs, and a step showing the combination preserves what you want. If you can write the recursion you can write the proof; you have just never been asked to.

What decides your score here

Answering "how do you know it's correct?" with an invariant. This question, or "convince me this greedy always works", is where the induction material pays off. It is a two-sentence answer that most candidates cannot give at all.

Saying the pruning out loud in backtracking. Backtracking without pruning works and is slow. The pruning is the design decision, and stating it is what gets credited.

Not silently blowing the recursion limit. On a large input, converting to an explicit stack is correct — and saying why you are doing it is what makes it a decision rather than a preference.

Proving by induction

Three steps, always the same. Base case: the algorithm is correct for the smallest input. Hypothesis: assume it is correct for every input smaller than n. Step: show that under the hypothesis it is correct for n.

For merge sort that reads as: a list of zero or one element is already sorted, so the base holds. Assume the algorithm sorts any list shorter than n. For a list of length n we split into two halves, each shorter, so by the hypothesis both come back sorted — and it remains to show that merging two sorted lists yields a sorted one. It does, because at each step merge takes the smaller of the two front elements, and since both inputs are sorted that element is the smallest of everything remaining. So the output is built in non-decreasing order and contains every element.

That is the whole proof, and it fits in thirty seconds spoken.

Loop invariants, which is the iterative version

For a loop you prove an invariant: a property true before, during and after every iteration.

For binary search: if the key is present, it lies in the current window. Initialisation holds because the window starts as the whole array. Maintenance holds because when the midpoint is too small, everything at or below it is too small, so discarding that half cannot discard the key. Termination: the loop ends when the window is empty, and by the invariant the key is absent.

Note that last part. Proving termination is part of the proof, and it has a standard form: find a non-negative quantity that strictly decreases each iteration. Here it is the window width. Most people forget this half, and mentioning it unprompted signals rigour.

For greedy algorithms the standard tool is different: an exchange argument. Show that any optimal solution can be transformed into the greedy one without getting worse — swap the optimal solution's first differing choice for the greedy choice and argue it does not hurt. If that always holds, the greedy solution is optimal too. That is the answer to "convince me this greedy works".

Recursion, briefly

Three parts: a base case that stops, a reduction that makes the problem strictly smaller, and a combination step for the results. If the reduction is not strict you do not terminate, and that is the number one cause of infinite recursion.

Python does not optimise tail calls and caps the stack around a thousand frames. On an input of a hundred thousand, convert to an explicit stack — and say out loud that you are doing it because of the limit, rather than silently.

Backtracking

Choose, explore, un-choose. That is the whole template:

def bt(state, path):
    if complete(state):
        result.append(path[:])            # COPY — path is about to be mutated
        return
    for choice in options(state):
        if not promising(choice):         # PRUNING: the design decision
            continue
        path.append(choice)               # choose
        bt(advance(state, choice), path)  # explore
        path.pop()                        # un-choose

Two bugs live in that snippet and both are silent. Appending path instead of path[:] makes every entry alias the same list, which is empty by the end. Forgetting the pop() lets state leak into the sibling branch, and the results are subtly wrong rather than obviously broken.

Pruning is what turns "it works" into "it works fast". In N-Queens, checking for a conflict before descending cuts the tree by orders of magnitude — and the trick that makes the check constant is encoding the two diagonals as row − col and row + col, so all three conflict tests are set lookups. Always say the pruning out loud; it is the part being assessed.

When the input contains duplicates, dedupe by sorting first and skipping a candidate that equals its predecessor at the same level of the recursion. Same value, same level, means a duplicate branch.

Memoisation

Recursion plus a cache is top-down DP, and in Python @functools.cache does it in one line. The only requirement is that the arguments be hashable, so pass indices or tuples rather than lists. Reaching for it in an interview is legitimate and fast — and connects straight to module 06.

Say it

Cover the answers. Out loud, in English.

Now do this

Three problems, plus one exercise that is not code.

1. Subsets — 15 min. The base template; get the copy right.
2. Combination Sum — 25 min. Say why you pass the same index rather than advancing.
3. N-Queens — 35 min. Encode the diagonals as sets and narrate the pruning.

Then, on paper and out loud: prove binary search correct, stating the invariant, the maintenance argument, and the termination argument. Two minutes, no notes.

Stop when you can give the binary search proof cold, and the backtracking template comes out without thinking about the copy or the pop.