Recursion, Backtracking, and Divide and Conquer

What must be true when the call returns?

A recursive call is easiest to trust at the moment it gives control back. What fact does the caller receive? Which temporary changes were restored, and which intentional mutation is now the result? Which part of the problem is finished?

Consider a grid search that marks a cell, recurses into its neighbors, and returns immediately when one neighbor succeeds. If that success path skips the unmarking step, the function can return the right boolean while leaving the board wrong for its caller. The recursive idea was fine. The return contract was broken.

This is the useful center of recursive reasoning: every call occupies one well-defined state, makes progress, and either returns a sufficient fact or records an answer. If it temporarily borrows mutable state, it returns that state intact. Base cases, pruning, and complexity all become easier to reason about once that promise is precise.

Give one call a bounded job

Before writing a helper, finish this sentence:

Given this state, the helper returns or records ___, considering exactly ___, and leaves ___ unchanged.

The blanks force several decisions that a generic “recurse on the rest” explanation conceals. The state must contain every fact that changes the future. The base case must answer the same question as the recursive case. Every child must move toward that base case. The caller must know whether children are alternatives to explore or pieces of one result to combine.

Four common contracts illustrate the range:

• height(node) returns the height of the subtree rooted at node.
• search(row) records every legal board that extends the queens already placed in rows before row.
• combinations(start, remaining) records every completion drawn from the candidate suffix beginning at start.
• sort(lo, hi) sorts the half-open range items[lo:hi].

These calls have similar syntax but different shapes. Tree traversal follows substructures fixed by the input. Backtracking creates alternative children from choices. Divide and conquer needs several child results because they are pieces of one parent answer. If many paths ask the same state question, the recursion is exposing a dynamic program and should usually remember its answers.

The base case follows from the sentence, not from habit. A height helper returns a height for an empty tree. A search helper records a solution only when all decisions have been made. A boolean existence helper returns False for an impossible state and True for a complete one. Mixing “return an answer” with “append an answer elsewhere” without deciding which contract governs the helper is a common source of half-correct code.

A constraint problem becomes a decision tree

Place n queens on an n × n board so that no two share a row, column, or diagonal. Filling the board cell by cell creates a large and awkward search. Filling one row per call builds one decision at each depth and makes the row constraint true by construction.

Use the contract:

search(row) appends every legal completion of placement for rows row through n - 1; when it returns, placement and the three occupied-line sets are exactly as they were on entry.

placement[r] = c means the queen in row r occupies column c. The active prefix is therefore a partial permutation of the columns: a used column cannot appear again. Two additional sets represent the diagonals, identified by row - col and row + col.

def solve_n_queens(n):
    solutions = []
    placement = []
    columns = set()
    descending = set()  # row - column
    ascending = set()   # row + column

    def search(row):
        if row == n:
            solutions.append(tuple(placement))
            return

        for column in range(n):
            down = row - column
            up = row + column
            if (
                column in columns
                or down in descending
                or up in ascending
            ):
                continue

            placement.append(column)
            columns.add(column)
            descending.add(down)
            ascending.add(up)

            search(row + 1)

            ascending.remove(up)
            descending.remove(down)
            columns.remove(column)
            placement.pop()

    search(0)
    return solutions

For n = 4, the function returns the column sequences (1, 3, 0, 2) and (2, 0, 3, 1). The first says: put queens at (0, 1), (1, 3), (2, 0), and (3, 2).

The code is correct for reasons that can be stated without tracing every board. On entry to search(row), the prefix contains one nonattacking queen in each earlier row, and the three sets describe exactly those queens. The loop considers every column. It rejects a column only when the new queen would already conflict with the prefix, a conflict that later rows cannot repair. Every legal choice extends the invariant to row + 1. At row == n, the prefix is a complete legal board. Restoration re-establishes the entry invariant before the next column is tried.

That last sentence is the backtracking proof. “Choose, explore, unchoose” is useful shorthand, but the deeper obligation is sibling isolation. Each child may borrow the partial board; none may change the state from which its next sibling begins.

An existence-only version can stop after the first solution, but it must still clean up before returning through each active frame. Store the child’s boolean, restore the state, and then return it. An early return True between the recursive call and the four removal operations recreates the grid-search bug from the opening.

Prune only what the future cannot repair

The occupied-line checks are pruning rules. They are sound because another queen cannot undo a conflict among queens already placed. This monotonic impossibility is what distinguishes pruning from a promising guess.

The same test applies elsewhere:

• A parentheses prefix with more closes than opens can never become valid.
• A partial assignment that violates a fixed constraint cannot be repaired by assigning more variables.
• If all remaining numbers are positive, a sum already above the target cannot return to it.
• After candidates are sorted, a positive candidate larger than the remaining target proves that all later candidates are too large as well.
• Two equal choices at the same decision depth may represent duplicate output; equal values at different depths may still be legitimate choices.

Every condition matters. Negative numbers invalidate the overshoot rule. Unsorted candidates invalidate the early break. Skipping all equal values, rather than equal siblings, can erase valid combinations.

Here is the smaller combination case in executable form. Each input position may be used once, equal-valued sibling branches are collapsed, and positivity makes the early stop sound:

def combination_sum_once(candidates, target):
    candidates = sorted(candidates)
    results = []
    path = []

    def search(start, remaining):
        if remaining == 0:
            results.append(tuple(path))
            return

        for index in range(start, len(candidates)):
            value = candidates[index]
            if index > start and value == candidates[index - 1]:
                continue
            if value > remaining:
                break

            path.append(value)
            search(index + 1, remaining - value)
            path.pop()

    search(0, target)
    return results

Advancing to index + 1 prevents reuse. Passing index instead would describe a different problem in which a candidate may be chosen repeatedly. The distinction lives in the state transition, not in the word “combination.”

Permutations change the transition in another way. At each depth, choose any unused value rather than only a suffix value. For distinct values, a used set or bit mask records that ownership. With duplicates, a count map often expresses the contract more cleanly: choose a value whose count is positive, decrement it for the child, and restore it afterward. N-Queens is a constrained permutation search because each row chooses one unused column and the diagonal sets rule out otherwise valid permutations early.

When children are pieces, return enough to combine them

Backtracking children compete: each branch is a different possible answer. Divide-and-conquer children cooperate: the parent needs their results to build one answer.

A balanced-tree check exposes why the return contract matters. A naive solution asks whether every subtree is balanced, then separately recomputes its height. In a skewed tree, those repeated height walks produce quadratic work. Let one call return both facts by using -1 as a failure sentinel:

def height_or_fail(node):
    if node is None:
        return 0

    left_height = height_or_fail(node.left)
    if left_height == -1:
        return -1

    right_height = height_or_fail(node.right)
    if right_height == -1:
        return -1

    if abs(left_height - right_height) > 1:
        return -1
    return 1 + max(left_height, right_height)


def is_balanced(root):
    return height_or_fail(root) != -1

The sentinel is safe because a real height cannot be negative. Each child returns exactly what the parent needs: whether failure has already occurred and, if not, the height required to test the boundary between the two child results. Every node is processed once.

That boundary is the characteristic danger in divide and conquer. Merge sort must merge values that lie on opposite sides of the split. Maximum subarray must consider an answer crossing the midpoint. Tree diameter must consider a path that rises from one child and descends into another. Closest-pair methods must inspect the strip near the dividing line. Solving each half correctly is insufficient if the combine step forgets what crosses between them.

For merge sort, the contract sort(lo, hi) uses half-open bounds. A range of length zero or one is already sorted. The two child ranges are disjoint and cover the parent range; a linear merge then consumes them completely. The recurrence is two half-size calls plus linear combination, yielding O(n log n) time and, in the usual implementation, O(n) auxiliary space. The recurrence describes the call tree; the contract explains why its work produces a sorted range.

Read cost from the tree, then check the machine

One path through a recursive program rarely describes its cost. Count the whole call tree, the work at each call, and the answers copied at the leaves.

N-Queens has depth n. The unused-column rule bounds the number of recursive prefixes by a sum of partial permutations, which is O(n!); this implementation also scans n columns at each prefix, giving the coarse bound O(n · n!) before diagonal pruning. Constructing every returned board adds output cost. The combination search has up to 2^n subsets before pruning, plus candidate scans and result copying. Balanced-tree traversal is O(n) because no node is recomputed. Merge sort’s recurrence yields O(n log n).

Stack space follows maximum active depth, not total calls. A balanced tree uses O(log n) frames, while a skewed tree uses O(n). A depth-first graph walk, adversarial quicksort partition, deeply nested parser input, or large constraint search can exceed a language’s recursion limit even when its asymptotic time is acceptable.

That practical risk can change the expression of the algorithm:

• Use an explicit stack when depth is large or when suspended control state should be inspectable.
• Add memoization when different paths ask the same state question; plain recursion is recomputing a dynamic program.
• Prefer a loop when the recursion is only a linear chain and the iterative state is clearer.
• Collapse the decision tree to one branch only when a greedy proof shows that the discarded branches cannot improve the answer.
• Keep backtracking when the output itself is combinatorial or constraints make genuinely different branches necessary.

Copying versus restoration is also an algorithmic decision. Passing path + [value] makes ownership local but copies a growing prefix at every edge. Appending and popping avoids those intermediate copies but demands a clean return path. Choose after accounting for both cost and defect surface.

Practice by changing the contract

The most useful drills alter one obligation at a time:

1. Generate all subsets of distinct values. State why advancing an index produces combinations rather than permutations, and include output-copy cost.
2. Generate unique permutations from repeated values. Use a count map and explain why restoring a count isolates siblings.
3. Change the N-Queens function from enumeration to existence. Make every success path restore state before it returns.
4. Search a word in a grid. Explain why visited state is path-local rather than global, then construct a case that fails if a successful branch leaks a marked cell.
5. Compute tree diameter in one traversal. Decide which two facts each child must return so the parent can account for a path through itself.
6. Implement quickselect and choose inputs that expose a bad partition boundary and worst-case recursion depth.
7. Take the positive-only combination solver above and allow negative values. Identify exactly which progress and pruning arguments cease to hold before changing the code.

If a solution fails, trace one call at the point of return. Write down its entry state, promised result, and exit state. This usually reveals a missing fact, an invalid prune, a nonshrinking transition, or borrowed state that was not restored.

Before trusting a recursive solution

You should be able to answer these questions without appealing to a template:

1. What does one call promise in a single sentence?
2. Which values completely identify its state?
3. Which state is already answered, and why is that base result correct?
4. How does every child make progress?
5. Are the children alternatives, pieces to combine, or repeated questions?
6. What may this call mutate, and what exit state does it promise on every return path?
7. What fact proves each prune sound?
8. What crosses a divide-and-conquer boundary?
9. How many calls, transitions, and output copies can the full tree create?
10. What is the maximum active depth on the worst allowed input?

The next two chapters narrow the choice tree in different ways. A greedy algorithm discards branches because a proof makes one local choice safe. Dynamic programming preserves answers because several branches reach the same state. Both decisions become visible only after the recursive state and return contract are honest.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 33: Correctness Before Cleverness
• Chapter 45: Graphs
• Chapter 47: Greedy Algorithms
• Chapter 48: Dynamic Programming