41Recursion & backtracking — searching a tree of choices

In Chapter 40 we learned to win by remembering — dynamic programming, where you cache a subproblem's answer so you never solve it twice. Now we drop one level, down to the raw search that the memory was quietly speeding up. Some problems have no clever formula. The only honest move is to try the possibilities — arrange the songs, place the queens, fill the grid. Do that naively and you drown in an ocean of combinations. So here's the plan: recursion to explore those possibilities one choice at a time, backtracking to undo a choice and try the next, and pruning to shut the door on billions of dead ends before you ever walk through them. The whole way through, we keep asking the one question that matters — how do you search a tree with more leaves than there are atoms in the room, and still finish before lunch? By the end, you'll look at any "find a valid or optimal arrangement" and see a tree of choices — and know exactly where to prune it.

01Recursion: shrink the problem until the answer is obvious

Let's start with the one idea the whole chapter stands on. Here's recursion: solve a big problem by solving a smaller version of the same problem, and keep shrinking until the version is so tiny the answer needs no thought at all. That tiny version is the base case — the floor you fall to and stop. Every step above it is the recursive case — do a sliver of the work yourself, then hand the rest to a smaller copy of yourself.

Watch it work on something concrete: the total length of a playlist. The total of [200, 247, 245] is just "the first song, plus the total of everything after it." That second half is the same problem on a shorter list. Shrink it far enough and you reach the empty playlist, whose total is plainly 0. That's the whole recipe — no loop, no cleverness, just a problem that eats itself one item at a time.

def total(songs):
    if not songs:                       # BASE CASE: empty list → answer is 0
        return 0
    return songs[0] + total(songs[1:])  # first + total of the REST (a smaller list)

print(total([200, 247, 245]))           # 692
print(total([]))                        # 0

Lines 2–3 are the floor: an empty playlist sums to 0, no recursion needed. Line 4 is the shrink: peel off songs[0], then ask the same function to total songs[1:] — a list one shorter. Run on CPython 3.12.7, total([200, 247, 245]) returns 692 (200 + 247 + 245) and total([]) returns 0. Notice there is no loop anywhere — the repetition is the function calling itself.

Where does the machine keep its place across all those nested calls? On the call stack — Volume 1, chapter 9. Each call gets a frame: a scrap of memory holding that call's own songs, frozen mid-addition, waiting for its smaller copy to return a number. The frames pile up until the base case, then collapse back down. Each one finishes its + with the value handed up from below. The call stack is recursion's bookkeeping — you don't manage the partial state, the stack does.

Summing a list only ever shrinks one way — chop the head, recurse on the tail, a straight line down. But what if at each step you face several options? Then the single line splits into a branching tree — and trees grow fast. →

02Every choice sprouts a branch — the combinatorial explosion

Recursion becomes powerful — and dangerous — the moment each step offers more than one option. Then it stops drawing a line and starts drawing a tree of choices. The root is "nothing decided yet," each branch is one option, and each leaf at the bottom is one complete solution. To generate every possibility, you walk every branch.

Count the leaves and you feel the danger. Arrange 3 songs in order: the first slot has 3 candidates, then 2 remain for the second, then 1 — that's 3 × 2 × 1 = 6 = 3! orderings (a permutation is one ordering of all the items). Pick a subset instead — each song is independently in or out — and you get 2 × 2 × 2 = 2³ = 8 subsets. We didn't just assert those numbers. We counted the choices at each level and multiplied. That multiplication is the whole story of why brute force dies.

Why so fast? Because it doesn't add — it multiplies. Ten songs: 10! = 3,628,800 orderings, still nothing. Twenty songs: 20! = 2,432,902,008,176,640,000 — 2.4 quintillion. At a billion arrangements per second, that's about 77 years just to list them (both figures computed in Python below). Add one more item and you multiply the wait again. This is the combinatorial explosion, and it is the reason the rest of the chapter exists.

If listing 20! possibilities takes 77 years, brute force is hopeless — yet solvers crack far harder-looking puzzles in milliseconds. Their secret isn't a faster computer. It's refusing to visit most of the tree. →

03Backtracking: walk the tree, undo on the way back

Backtracking is how you actually walk a choice tree without building it all in memory at once. You go depth-first: make one choice, dive deeper as if it were final, and when you've either found a solution or run out of options, step back and undo that choice so the next branch starts from a clean slate. Three beats, over and over: choose → explore → un-choose. That un-choose is the "back" in backtracking. It restores the shared partial state, so the sibling branch isn't polluted by the one you just abandoned.

Here it is generating every subset of the playlist. At each song you branch twice: skip it, or take it. Two options × n songs = 2ⁿ leaves, exactly as we counted.

def subsets(items):
    out, chosen = [], []
    def bt(i):
        if i == len(items):        # reached the bottom: record this subset
            out.append(chosen.copy())
            return
        bt(i + 1)                  # BRANCH 1: skip items[i]
        chosen.append(items[i])    # CHOOSE items[i]
        bt(i + 1)                  # BRANCH 2: explore with it taken
        chosen.pop()               # UN-CHOOSE — restore state for the caller
    bt(0)
    return out

print(subsets(["Levels", "Titanium", "Wake Me Up"]))

Lines 4–6 are the base case: once i walks past the last song, chosen holds one complete subset, so we save a copy (not the live list — it's about to change). Line 8 explores the "skip this song" branch. Lines 9–11 are the choose/explore pair: append the song, then recurse to decide the rest with it included. Line 12 is the crucial un-choose: chosen.pop() removes the song, so that when control returns to the caller, chosen looks exactly as it did before this call touched it. Run on 3.12.7, the call produces all 8 subsets — from [] through ['Levels', 'Titanium', 'Wake Me Up']. Swap the two-way branch for a "place each item that's still unused" loop and the same pattern gives all 6 permutations of [1, 2, 3]: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] (also a real run).

So far we still visit all 2ⁿ leaves — we've organised the search, not shortened it. The real magic is a single extra if: check a partial solution before descending, and cut whole subtrees you can prove are hopeless. →

04Pruning: the whole game

Here is the idea that separates a toy from a solver. As you build a solution one choice at a time, keep asking: can this partial choice possibly complete into a valid answer? The instant the answer is "no," abandon the entire subtree beneath it. Every arrangement that started with this bad prefix is dead, so you never generate a single one of them. That is pruning, and it is the difference between exploring 10⁹ dead ends and 10³ live ones.

The classic showcase is the N-queens puzzle: place N chess queens on an N×N board so none attacks another (no two share a row, column, or diagonal). Put one queen per row — that rules out any row-clash for free — and at each row try each column. Here's the pruning rule: the moment a queen conflicts with one already placed, skip that column entirely and don't recurse into the rows below it. A whole doomed subtree vanishes.

Count the savings on the standard 8×8 board and watch three numbers fall off a cliff. Place 8 queens on any of 64 squares blindly: that's C(64,8) = 4,426,165,368 placements — 4.4 billion (computed in Python). Be a little smarter — one queen per row, all column combinations — and it's 8⁸ = 16,777,216 leaves. Now add the pruning if, and backtracking touches just 2,057 partial placements to find all 92 solutions. That's over 8,000× fewer nodes than even the row-by-row brute force, and two million times fewer than the naïve count. Same puzzle. One conditional. The tree barely grows before pruning mows it down.

Turn the knob yourself. Slide N below and compare the brute-force tree against what backtracking actually visits. The gap is the wasted work you never do.

Pruning tames N-queens because a bad prefix is provably hopeless. But some problems hide their answer so well that no pruning rule cracks the tree open. What then? →

05When the tree won't shrink: NP-hard, and taming the beast

For some problems, nobody has found a pruning rule — or any trick — that reliably avoids the exponential, and there's deep evidence none exists. These are the NP-hard problems. Take the travelling salesman: visit N cities by the shortest possible loop. With 20 cities there are (20−1)!/2 = 60,822,550,204,416,000 distinct tours — 60 quadrillion, computed in Python. Or SAT (is there an assignment of true/false that makes a logic formula true?), which has 2ⁿ assignments. For either one, there is no known algorithm that beats the exponential in the worst case. The tree is genuinely dense with plausible-looking branches.

And yet we solve big instances every day. Not with a magic fast algorithm, but by taming the tree with three moves you can name:

• Branch and bound — carry a running "best answer so far," and before exploring a subtree, compute a bound on the best it could possibly yield. If even the optimistic bound can't beat what you already have, prune it. (Pruning, upgraded from "invalid" to "can't-win.")
• Heuristics / ordering — try the most promising branch first. The order you visit children in doesn't change the answer, but it changes how fast you find a good "best so far," which lets branch-and-bound prune harder. Chess engines order moves this way.
• Constraint propagation — after each choice, cheaply deduce forced consequences that shrink the remaining options (a sudoku solver fills every forced cell before it ever guesses).

This is why real SAT solvers chew through formulas with millions of variables, why sudoku apps solve instantly, and why chess AI before neural networks was backtracking the game tree with alpha-beta pruning — the same "this branch can't beat what I've found, so cut it" logic. The exponential never went away. It got outmanoeuvred.

Branch and bound prunes by "can't win." But there's a fourth weapon, and it's the bridge to the crown jewel of the last chapter: what if the tree keeps re-solving the same subproblem? →

06Backtracking + memory = dynamic programming (the mental move)

Walk a choice tree and you'll often notice the same subproblem showing up on many different branches. The naïve recursive Fibonacci is the purest example (stepped in traces T29/T30): fib(5) calls fib(3) down two separate paths, and each one rebuilds the same subtree from scratch. The tree is exponential not because the answer is hard, but because you keep re-deriving what you already knew.

The fix is one line of thinking: remember the answers you've already computed. Cache each subproblem's result the first time, and on every later encounter, read it instead of recomputing. That collapses the exponential tree into a linear walk. Backtracking that caches overlapping subproblems is dynamic programming — the previous chapter's crown jewel is exactly this chapter's search plus a memo. Look for two conditions: the subproblems overlap (worth caching), and the best full answer is built from best sub-answers (safe to build up).

That reframing is the transferable move — the 1% habit this chapter installs. Faced with any "find a valid or optimal arrangement," don't reach for a formula. Ask three questions in order: (1) Can I frame this as building a solution one choice at a time — a tree of choices? (2) Can I prune — is there a cheap test that proves a partial choice is hopeless, so I skip its subtree? (3) Do subtrees repeat — should I memoise? Choice-tree, then prune, then memo. That sequence turns "impossible, 2.4 quintillion cases" into "feasible, a few thousand."

You already run a rough version of this off-screen. Take debugging: you form a hypothesis, follow it, and the moment the evidence contradicts it you abandon that whole line of theories instead of stubbornly exploring a dead branch. That's pruning. Or planning a route through errands, ruling out a plan the instant it can't fit your lunch meeting — pruning again. Backtracking isn't an exotic algorithm. It's the disciplined, countable version of how a careful mind already searches. Learn to name the tree and the prune, and you can attack problems that have no formula at all.

Backtracking searches when there's no formula. Next we return to a problem that does have fast algorithms — sorting — and meet a stunning result: a hard mathematical ceiling proving you can never sort by comparisons faster than n log n… and the clever trick that sneaks under it anyway. A beautiful impossibility, in the next chapter. →