Recursion and Backtracking

1Recursion needs a base case

A recursive function solves a problem by calling itself on a strictly smaller input. That only terminates if some inputs hit a base case that returns without another call. A missing or wrong base case is the usual cause of infinite recursion and stack overflow — write the base case before the recursive branch.

Figure. Each call waits on a smaller one. The chain ends at fact(1) — that base case is what stops the stack from growing forever.

How a recursive call works

1. ShrinkIdentify a smaller instance of the same problem (n−1, a shorter suffix, a child subtree).
2. BaseWhen the input is small enough that the answer is immediate (n ≤ 1, empty list, null node), return it — no further call.
3. CombineUse the recursive result to finish the current frame (multiply by n, append a node, merge sorted halves).

Factorial

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

2Call stack costs O(d) space

Every live recursive call occupies a stack frame. If the deepest chain of calls has depth d, recursion uses O(d) stack space on top of any heap structures you allocate. Deep trees, long linked lists and large n in a linear recursion can overflow the language's call-stack limit even when the algorithm is asymptotically fine in time — peak space tracks the longest chain, not how many calls already returned.

Figure. Four frames live at once for fact(4). Space tracks depth, not how many factorials you will eventually finish.

What the stack holds

1. PushEntering a call stores locals, arguments and the return address — one frame.
2. DepthWhile that call waits on a child, both frames stay live. Peak space tracks the longest chain, not the number of completed calls.
3. PopReturning frees the frame. After the top-level return, stack cost is gone; heap allocations may remain.

3Backtracking abandons dead partials

Backtracking builds a candidate solution one choice at a time and abandons a partial as soon as it cannot lead to a valid complete answer. That is search with undo: explore a branch, and if a constraint fails — or the branch finishes — revert the last choice and try the next option. Generate-all-subsets, permutations, combinations, N-Queens and Sudoku share this shape.

Figure. Backtracking drops a partial as soon as a constraint fails, then undoes that choice and tries the next option.

What backtracking does

1. ExtendAppend one legal choice to the current partial (a number into a subset, a queen into a row, a digit into a cell).
2. TestIf the partial already violates a constraint, do not recurse — that whole subtree is dead.
3. UndoAfter exploring (or rejecting) a choice, remove it so the next sibling option sees a clean partial.

4Choose, explore, unchoose

The core backtracking loop is three lines of intent: make a choice, recurse to explore every completion of that choice, then undo the choice so the next option can try. Interviews phrase this as choose / explore / unchoose. Getting the undo wrong — forgetting to pop, clear a bit, or free a column — is how solutions silently corrupt later branches.

Figure. Backtracking is choose → explore → unchoose: undo the mutation before trying the sibling branch.

One iteration of the loop

1. ChooseMutate the shared state: push into path, mark a column used, place a digit.
2. ExploreRecurse to the next index / row / cell. Record a solution when the base case says the partial is complete.
3. UnchooseExactly reverse the mutation before trying the next candidate at this level.

Template

def backtrack(path, options):
    if is_solution(path):
        record(path)
        return
    for choice in options:
        if not valid(path, choice):
            continue
        path.append(choice)          # choose
        backtrack(path, next_options)
        path.pop()                   # unchoose

5Subsets: include or exclude each element

The power set of n elements has 2^n members. Backtracking generates them with a binary decision at each index: include nums[i] in the current subset, recurse, then exclude it and recurse. When the index reaches n, record a copy of the path. Time is \Theta(2^n) to list every subset (more if you count the cost of copying each path).

Figure. Include/exclude tree for nums = [1, 2]: four leaves, one per subset. The ledger's n = 3 tree is the same shape one level deeper — eight leaves.

Include / exclude

1. Index iDecide the fate of nums[i] — in or out — before moving to i+1.
2. Include branchAppend nums[i], recurse on i+1, then pop (unchoose).
3. Exclude branchRecurse on i+1 with the path unchanged. At i == n, append path[:] to the answer.

All subsets

def subsets(nums):
    ans, path = [], []
    def bt(i):
        if i == len(nums):
            ans.append(path[:])
            return
        path.append(nums[i])
        bt(i + 1)            # include
        path.pop()
        bt(i + 1)            # exclude
    bt(0)
    return ans

6Permutations cost n!

A permutation is an ordering of all n elements. There are n! of them. Backtracking builds one by choosing any unused element for the next position, recursing, then unchoosing. Writing each permutation of length n costs O(n) work to copy, so listing them all is O(n \cdot n!) — that factorial blow-up overtakes the subset tree once n grows.

Same include/exclude tree shape as Subsets: include or exclude each element, except every level picks the next unused element — n choices, then n-1, …, for n! leaves.

Fill the next slot

1. Unused poolAt depth k, any of the remaining n−k elements may occupy path[k].
2. Choose onePlace it, mark used (or swap into position), recurse to k+1.
3. BaseWhen k == n, record path. Unchoose before the next candidate at this depth.

All permutations

def permute(nums):
    ans, path, used = [], [], [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            ans.append(path[:])
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)
            bt()
            path.pop()
            used[i] = False
    bt()
    return ans

7Pruning: N-Queens

Pruning cuts a branch the moment a constraint fails, before recursing. In N-Queens you place one queen per row and skip any column whose column or either diagonal is already occupied. Without pruning the search is worst-case O(n!) row–column assignments; with set-based conflict checks, whole invalid subtrees disappear — for n = 4 only two boards survive.

Figure. One of the two n = 4 solutions: queens in columns [1, 3, 0, 2] (0-based). No shared column or diagonal — every other column choice at some row was pruned.

Place a queen

1. Row rTry each column c in 0…n−1.
2. PruneReject c if c, (r−c), or (r+c) is already in the occupied sets — do not recurse.
3. Descend / undoMark the three sets, recurse to r+1; on return, unmark. When r == n, count a solution.

Count N-Queens

def total_n_queens(n):
    cols, d1, d2 = set(), set(), set()
    def bt(r):
        if r == n:
            return 1
        count = 0
        for c in range(n):
            if c in cols or (r - c) in d1 or (r + c) in d2:
                continue
            cols.add(c); d1.add(r - c); d2.add(r + c)
            count += bt(r + 1)
            cols.remove(c); d1.remove(r - c); d2.remove(r + c)
        return count
    return bt(0)

Coding lab. Four queens, two boards runs in the app, with checks on your output.

8Combinations, and when depth is the danger

Combinations of k out of n ignore order: backtracking still chooses or skips, but stops once the path length is k (or once remaining elements cannot fill the quota). There are \binom{n}{k} results. Separately, any deep recursion — even a correct one — can blow the call stack; convert that walk to an explicit stack or a loop when depth may exceed the runtime limit.

Read the comparison table: combinations stop at path length k for \binom{n}{k} results; any deep recursion that may exceed the call stack should move to an explicit stack or loop.

Two takeaways

1. CombinationsStart index s; either take nums[i] and advance with k−1 left, or skip to i+1 with k unchanged. Record when k hits 0.
2. CountLeaves equal \binom{n}{k}, not 2^n and not n! — order does not matter and size is fixed.
3. Depth escapeIf the call chain can be long (linked-list recursion, skewed tree), keep the same logic on a heap-allocated stack or rewrite as iteration.