41Recursion & backtracking — searching a tree of choices

In Chapter 40 we learned to win by remembering — dynamic programming, the trick of caching a subproblem's answer so we never solve it twice. Here we drop one level, down to the raw search that all that memory was quietly speeding up. Some problems simply have no clever formula. The only honest move left is to try the possibilities: arrange the songs, place the queens, fill the grid. Try them naively, though, and you drown in an ocean of combinations. So here's the plan for this chapter. We use recursion to explore the possibilities one choice at a time, and backtracking to undo a choice and try the next. Then we use pruning to slam the door on billions of dead ends before we ever walk through them. The whole way through, we keep asking the one question that actually 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" problem and see a tree of choices. Better, you'll 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. Recursion means solving a big problem by solving a smaller version of the same problem. You keep shrinking it until the version is so tiny the answer needs no thought at all. That tiny, no-thought 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. And that second half is the same problem on a shorter list — the exact shape we just named. Shrink far enough and you hit the empty playlist, whose total is obviously 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

Line 2–3 is the floor: an empty playlist sums to 0, and no recursion is needed to say so. Line 4 is the shrink step. It peels off songs[0], then asks the very same function to total songs[1:], a list one item shorter. Ran on CPython 3.12.7, total([200, 247, 245]) returns 692 (that's 200 + 247 + 245) and total([]) returns 0. Notice there is no loop anywhere in the function. The repetition comes entirely from the function calling itself.

Where does the machine keep its place across all those nested calls? On the call stack, the machinery we opened up back in 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 stack up until the base case, then collapse back down. As they collapse, each frame finishes its + with the value handed up from below. The call stack is recursion's bookkeeping — you don't manage the partial state, because the stack does it for you.

One honest caveat before we lean on this, because the stack is real memory with a real limit. Forget the base case, or fail to shrink toward it, and the frames pile up without end. CPython guards against that with a recursion limit, set to 1000 frames by default — ask sys.getrecursionlimit() and it will tell you. Blow past it and Python kills the call with a RecursionError rather than let the stack eat your memory. That limit also means our elegant total() would die somewhere around the thousand-song mark, where a plain loop would shrug and carry on. So treat recursion here as a way of thinking first. When the depth stays small, as it does in every tree this chapter searches, it is also excellent code.

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. With one option per step, the calls trace out a simple line. With several, they draw a tree of choices. The root is "nothing decided yet," each branch is one option taken, and each leaf at the bottom is one complete solution. To generate every single possibility, you have no option but to walk every branch.

Picture it with the three-song playlist before we count anything. The first choice is which song opens the set, and it sprouts 3 branches from the root. Down each of those branches two songs remain, so each one sprouts 2 more. One song is left after that, a single forced branch, and then you are standing at a leaf holding one finished ordering. Trace any root-to-leaf path with your finger and you read off one complete playlist. The tree isn't a metaphor here — it is literally the shape of the calls the recursion makes, one frame per node.

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 for the last. That's 3 × 2 × 1 = 6 = 3! orderings, and a permutation is exactly that: one ordering of all the items. Now pick a subset instead, where each song is independently in or out. You get 2 × 2 × 2 = 2³ = 8 subsets, and notice we didn't assert those numbers from a formula on high. We counted the choices at each level and multiplied — and that multiplication is the whole story of why brute force dies.

Here's the cruel part: growth by choices doesn't add, it multiplies. Ten songs give 10! = 3,628,800 orderings, which a laptop still shrugs at, but twenty songs give 20! = 2,432,902,008,176,640,000, which is 2.4 quintillion. At a billion arrangements per second, merely listing them takes about 77 years (both figures computed in Python below). Add one more item and you multiply the whole 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 traverse a choice tree without ever building the whole thing in memory. You go depth-first: make one choice, then dive deeper as if that choice were final. 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. The rhythm is three beats, repeated at every node: choose → explore → un-choose. That un-choose is the "back" in backtracking, and it matters more than it looks. It restores the shared partial state, so the sibling branch you try next isn't polluted by the one you just abandoned.

Why undo at all, instead of giving every branch its own private copy of the list? Because copying is real work the machine must do at every node of the tree. Hand a fresh copy to each of the 2ⁿ branches of a subset search and the copying alone dwarfs the searching. Backtracking's bargain is sharper: keep one shared list, push a choice onto it on the way down, pop it off on the way back up. The list is a live thing that always describes the current root-to-node path, nothing more. That is why the un-choose step is not optional politeness — skip it once and every branch explored afterwards inherits a lie.

you type
$ python skeleton.py

def subsets(items):
    out, path = [], []

    def walk(i):
        if i == len(items):
            out.append(path.copy())      # SNAPSHOT -- path keeps mutating
            return
        walk(i + 1)                      # branch 1: skip items[i]
        path.append(items[i])            # CHOOSE
        walk(i + 1)                      # EXPLORE
        path.pop()                       # UN-CHOOSE  <-- the law

    walk(0)
    return out

print(subsets(["a", "b", "c"]))

# ---------- now delete ONE line: path.pop() ----------
print(subsets_broken(["a", "b", "c"]))

# ---------- and now put pop() back, but append path instead of path.copy() ----------
print(subsets_noSnapshot(["a", "b", "c"]))

print(len(subsets(list(range(12)))), 2 ** 12)

you see
[[], ['c'], ['b'], ['b', 'c'], ['a'], ['a', 'c'], ['a', 'b'], ['a', 'b', 'c']]
[[], ['c'], ['c', 'b'], ['c', 'b', 'c'], ['c', 'b', 'c', 'a'], ['c', 'b', 'c', 'a', 'c'], ['c', 'b', 'c', 'a', 'c', 'b'], ['c', 'b', 'c', 'a', 'c', 'b', 'c']]
[[], [], [], [], [], [], [], []]
4096 4096

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"]))

Line 4–6 is the base case. Once i walks past the last song, chosen holds one complete subset, so we save a copy rather than the live list, which is 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 when control returns to the caller, chosen looks exactly as it did before this call meddled with it. Ran on 3.12.7, the call produces all 8 subsets, from [] up through ['Levels', 'Titanium', 'Wake Me Up']. And the pattern generalises with one small edit. Swap the two-way branch for a "place each item that's still unused" loop, and the identical skeleton spits out 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).

Now connect this back to the call stack from section 01, because something quietly wonderful is happening. The tree for 3 songs has 8 leaves, yet the stack never holds more than 4 frames at once. Those are the calls for i = 0, 1, 2, 3 down a single path. Depth-first search keeps only one root-to-leaf path alive in memory, never the whole tree. So the memory cost grows with n, while the work explored grows with 2ⁿ. Watch the frames in the walkthrough above: they never pile past the tree's depth, however many leaves the run visits. That asymmetry is the whole reason backtracking can face an exponential tree at all.

from itertools import product

KEYS = {"2": "abc", "3": "def", "4": "ghi", "5": "jkl",
        "6": "mno", "7": "pqrs", "8": "tuv", "9": "wxyz"}


def letter_combinations(digits):
    if not digits:
        return []                            # no digits -> no strings at all
    out, path = [], []

    def walk(i):
        if i == len(digits):                 # every decision made
            out.append("".join(path))        # SNAPSHOT
            return
        for ch in KEYS[digits[i]]:           # the branches at this step
            path.append(ch)                  # CHOOSE
            walk(i + 1)                      # EXPLORE
            path.pop()                       # UN-CHOOSE

    walk(0)
    return out


print(letter_combinations("23"))
print(letter_combinations(""))
print(letter_combinations("7"))
print(len(letter_combinations("2345")), 3 * 3 * 3 * 3)
print(len(letter_combinations("7999")), 4 * 4 * 4 * 4)

ref = ["".join(t) for t in product(*(KEYS[d] for d in "2345"))]
print(letter_combinations("2345") == ref)
print(letter_combinations("234")[:5], letter_combinations("234")[-1])


# ---------- the actual run, python 3.12.7 ----------
#
# ['ad', 'ae', 'af', 'bd', 'be', 'bf', 'cd', 'ce', 'cf']
# []
# ['p', 'q', 'r', 's']
# 81 81
# 256 256
# True
# ['adg', 'adh', 'adi', 'aeg', 'aeh'] cfi
#
#
# ---------- reading it ----------
#
# 1. The empty-string guard is not pedantry. Without it, walk(0) hits the
#    floor immediately -- i == 0 == len("") -- and records "".join([]) = "".
#    You would return [""], "one way to spell nothing", when the honest
#    answer is [], "no ways at all". One is a list containing an answer;
#    the other is a list containing no answers. Anything counting your
#    results downstream sees 1 where the truth is 0.
#
# 2. "7" has four letters and "9" has four. Hard-coding three letters per
#    digit is the classic bug: it passes every test built from 2-6 and
#    fails silently on a phone number containing a 7 or a 9.
#
# 3. The length check is free and total. len(answer) must equal the product
#    of the branch counts -- 3*3*3*3 = 81, 4*4*4*4 = 256 -- because the tree
#    is a full product with nothing pruned. If your count is short, a pop
#    is misplaced; if it is long, a snapshot is aliased.
#
# 4. The itertools comparison passes in ORDER, not just as a set. That is
#    the real payoff: walking the tree depth-first, taking each branch left
#    to right, produces exactly the lexicographic cross-product. Look at
#    "234": adg, adh, adi, then aeg -- the LAST digit spins fastest,
#    because it is the deepest loop in the recursion. Your recursion is an
#    odometer, and the deepest frame is the ones column.
#
# 5. No prune appears anywhere, because no partial string is ever invalid.
#    That is worth naming: this is backtracking with the prune removed, and
#    what remains -- choose, explore, un-choose -- is pure enumeration.
#    Add one rule (say, no two identical letters in a row) and you would
#    add exactly one 'continue' at the top of the loop, and the tree would
#    shrink without another line changing.

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 one question: 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 already 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 that none attacks another. Queens attack along rows, columns, and diagonals, so no two may share any of the three. The trick is to place one queen per row, which rules out row-clashes for free, and at each row to try each column in turn. Then the pruning rule is simple. The moment a candidate square conflicts with a queen already placed, skip that column entirely and don't recurse into the rows below. A whole doomed subtree vanishes on a single comparison.

Feel the size of what one skipped column throws away. Put two queens down, one in each of the first two rows, and six rows of choices still hang below, 8 columns each. That single node has 8⁶ = 262,144 leaves underneath it — re-multiply it yourself, six eights. One cheap conflict test at row 2 deletes all of them, unexamined. And the earlier a conflict is caught, the bigger the subtree that dies, which is why pruning near the root is worth vastly more than pruning near the leaves.

Count the savings on the standard 8×8 board, and watch three numbers fall off a cliff. Place 8 queens blindly on any of the 64 squares: that's C(64,8) = 4,426,165,368 possible placements, about 4.4 billion (computed in Python). Be a little smarter, with one queen per row and every column combination, and the tree has 8⁸ = 16,777,216 leaves. Now add the pruning if. Backtracking touches just 2,057 partial placements on its way to all 92 solutions. That is 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 extra conditional. The tree barely grows before the pruning mows it down.

Turn the knob yourself, because these numbers land differently when you watch them move. Below, slide N and compare the full brute-force tree against what backtracking actually visits. The widening gap between the two curves 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 at all, that reliably avoids the exponential. There is deep evidence that 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, about 60 quadrillion, computed in Python. Or take SAT, which asks whether some assignment of true/false makes a logic formula true — it has 2ⁿ assignments to consider. For both, there is no known algorithm that beats the exponential in the worst case. The tree is genuinely dense with plausible-looking branches, and no cheap test tells the dead ones apart.

It's worth pausing on what makes that last sentence so strange. Everything earlier in this volume, sorting and hashing and shortest paths, grew like n² or better. Doubling the input merely multiplied the work by a small constant. Exponential cost is a different animal: at n = 30, n² is 900 steps while 2ⁿ is 1,073,741,824, over a billion. Whether every problem whose answers are fast to check also has a fast way to solve is the famous P versus NP question. It is still open, and the Clay Mathematics Institute has a million-dollar prize waiting for a proof either way. Nearly every expert bets the answer is no — that for these trees, the exponential is simply the truth.

And yet we solve big instances of these problems every single day, and not because someone found a magic fast algorithm. The win comes from taming the tree, using 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).

These three moves are why real SAT solvers chew through formulas with millions of variables, and why sudoku apps solve any puzzle before your finger leaves the screen. They're why chess AI before neural networks was backtracking through the game tree with alpha-beta pruning — the same "this branch can't beat what I've already found, cut it" logic. The exponential never went away. It got outmanoeuvred.

One of those moves deserves a concrete picture before the next paragraph leans on it: branch and bound. Suppose the best complete tour you've found so far measures 100 km. Now you're partway down a branch and the half-built tour already measures 105 km. Every remaining leg can only add distance, because road lengths are never negative. So nothing below this node can possibly finish under 105, let alone beat 100 — the whole subtree is cut without a glance. The "bound" is that honest best-case estimate for a subtree, and the cut fires whenever the bound already loses to the best tour you hold.

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 for long enough and you'll notice something: the same subproblem showing up on many different branches. The naïve recursive Fibonacci is the purest example, and you can step it yourself in traces T29/T30. fib(5) reaches fib(3) down two separate paths, and each path rebuilds that same subtree from scratch. The tree is exponential not because the answer is hard. It's exponential because you keep re-deriving what you already knew.

You can count the waste with nothing but a pencil. Call the number of calls that fib(n) triggers c(n), so c(0) and c(1) are 1 call each. Then c(2) = 3, c(3) = 5, c(4) = 9, and c(5) = 15. Each value is its two children plus one for the call itself, and you can check every step. Fifteen calls to produce six distinct answers, fib(0) through fib(5), means most of the tree is duplicate work. Push n to 30 and the duplication is no longer a curiosity, it's nearly 2.7 million calls. And the distinct answers you actually need at n = 30 is still just 31.

The fix is one line of thinking: remember the answers you've already computed. Cache each subproblem's result the first time; 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. The two conditions to look for: 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 in your head. Faced with any "find a valid or optimal arrangement," don't reach for a formula, because one probably doesn't exist. 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, meaning is there a cheap test that proves a partial choice hopeless, letting me skip its whole subtree? (3) Do the subtrees repeat, so that a memo would pay for itself? Choice-tree, then prune, then memo — that sequence turns "impossible, 2.4 quintillion cases" into "feasible, a few thousand."

Here's the part I love: you already run a crude version of this search off-screen. When you debug, you form a hypothesis and follow it, and the moment the evidence contradicts it you abandon that whole line of theories rather than stubbornly exploring a dead branch. That's pruning. Planning a route through your errands, you rule out any plan the instant it can't fit your lunch meeting — pruning again. Backtracking isn't some exotic algorithm. It's the disciplined, countable version of how a careful mind already searches. Learn to name the tree and name 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. →