Recursion, backtracking and divide and conquer

Design a recursion by its base case and its shrinking step, generate subsets and permutations, and prune a search that would otherwise explode.

Recursion as a contract

Every correct recursion answers three questions: what is the smallest input I can answer directly, how do I reduce a general input toward that, and does the reduction always make progress? Skip the third and you get a stack overflow instead of an answer.

from typing import Sequence

# the base case handles the smallest input; the step makes progress
def total(xs: Sequence[int]) -> int:
    if not xs:                       # base: the empty sequence sums to 0
        return 0
    return xs[0] + total(xs[1:])     # step: strictly smaller input

# the same idea without slicing, which copies the whole rest of the list
def total_index(xs: Sequence[int], i: int = 0) -> int:
    if i == len(xs):
        return 0
    return xs[i] + total_index(xs, i + 1)

# convert to a loop when the recursion is a simple tail call
def total_iter(xs: Sequence[int]) -> int:
    acc = 0
    for x in xs:
        acc += x
    return acc

# the recursion tree for total([1,2,3]) is a straight line: depth n, work n
# for a branching recursion the count is what matters, not the depth
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # 2^n calls without memoisation

• Python's default recursion limit is about 1000 frames. Set sys.setrecursionlimit only with a matching thread stack size, and prefer an explicit stack for anything deeper.
• Slicing a list inside a recursive call makes a copy at every level, turning a linear recursion into quadratic work and memory.
• A recursion depth of n with a large n is a stack overflow waiting to happen. Rewrite it as a loop with an explicit accumulator, or as an explicit stack of work items.
• Every recursion can be written with an explicit stack, and sometimes it must be. The recursive form is preferable only when it is clearer.

Backtracking: choose, explore, unchoose

def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    current: list[int] = []

    def backtrack(start: int) -> None:
        result.append(current.copy())          # every node is a valid subset
        for i in range(start, len(nums)):
            current.append(nums[i])            # choose
            backtrack(i + 1)                   # explore with the choice made
            current.pop()                      # unchoose: the crucial step

    backtrack(0)
    return result


def permutations(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    used = [False] * len(nums)
    current: list[int] = []

    def backtrack() -> None:
        if len(current) == len(nums):          # a complete arrangement
            result.append(current.copy())
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            current.append(nums[i])
            backtrack()
            current.pop()                      # undo in the reverse order
            used[i] = False

    backtrack()
    return result


def combinations(nums: list[int], k: int) -> list[list[int]]:
    result: list[list[int]] = []
    current: list[int] = []

    def backtrack(start: int) -> None:
        if len(current) == k:
            result.append(current.copy())
            return
        # i must leave room for the remaining k - len(current) picks
        need = k - len(current)
        for i in range(start, len(nums) - need + 1):
            current.append(nums[i])
            backtrack(i + 1)
            current.pop()

    backtrack(0)
    return result


if __name__ == "__main__":
    print(len(subsets([1, 2, 3])))        # 8
    print(len(permutations([1, 2, 3])))   # 6
    print(len(combinations([1, 2, 3, 4], 2)))   # 6

Copying current at every leaf is where the cost lives. For n elements the output of subsets is 2 to the power n lists of average length n/2, so the output size alone is exponential. Backtracking reduces the search cost, not the answer size.

Pruning and divide and conquer

def solve_n_queens(n: int) -> int:
    """Count placements using three sets for O(1) conflict checks."""
    cols: set[int] = set()
    diag: set[int] = set()          # row - col is constant on a downward diagonal
    anti: set[int] = set()          # row + col is constant on an upward diagonal
    count = 0

    def place(row: int) -> None:
        nonlocal count
        if row == n:
            count += 1
            return
        for col in range(n):
            if col in cols or (row - col) in diag or (row + col) in anti:
                continue            # prune: an immediate conflict, no need to recurse
            cols.add(col); diag.add(row - col); anti.add(row + col)
            place(row + 1)
            cols.discard(col); diag.discard(row - col); anti.discard(row + col)

    place(0)
    return count


def merge_sort(xs: list[int]) -> list[int]:
    """Divide and conquer: split, solve both halves, combine in linear time."""
    if len(xs) <= 1:
        return xs
    mid = len(xs) // 2
    left = merge_sort(xs[:mid])
    right = merge_sort(xs[mid:])

    merged: list[int] = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= keeps the sort stable
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged


def quick_select(xs: list[int], k: int) -> int:
    """The k-th smallest, average O(n), by partitioning only one side."""
    pivot = xs[len(xs) // 2]
    lo = [x for x in xs if x < pivot]
    eq = [x for x in xs if x == pivot]
    hi = [x for x in xs if x > pivot]
    if k < len(lo):
        return quick_select(lo, k)
    if k < len(lo) + len(eq):
        return pivot
    return quick_select(hi, k - len(lo) - len(eq))

FAQ

Related

Complexity and Big-O in practice Dynamic programming: memoisation to tabulation

Last refreshed 2026-09-18.