Python Recursive Problem Solving

Describe the problem as a current decision plus a smaller remaining problem, and identify the base case where nothing is left to decide:

def subsets(items):
    if not items:
        return [[]]
    rest = subsets(items[1:])
    return rest + [[items[0]] + s for s in rest]

print(subsets(["laser", "lathe"]))   # [[], ['lathe'], ['laser'], ['laser', 'lathe']]

Every recursive call must make real progress towards the base case: one fewer position to fill, one item fewer to decide. If a call can be made with the same arguments it received, the recursion never ends. Writing the table above before the code is often the hardest and most useful step.

Backtracking builds a solution step by step in shared, mutable state. At each step it makes a choice, recurses, then undoes the choice before trying the next option:

def plan(tools, budget, chosen, results):
    if not tools:
        results.append(list(chosen))         # record a copy
        return
    name, cost = tools[0]
    if cost <= budget:
        chosen.append(name)                  # choose
        plan(tools[1:], budget - cost, chosen, results)
        chosen.pop()                         # un-choose (backtrack)
    plan(tools[1:], budget, chosen, results) # skip this tool

The pop() is essential. Without it, items chosen in one branch remain in chosen when the next branch runs, and results become mixed up. Two more details matter: record a copy of the state (list(chosen)), since the list keeps changing afterwards, and prune branches early: the cost <= budget check stops exploring choices that can't lead to a valid answer, which can save enormous amounts of work.

Backtracking solves puzzles such as Sudoku and the N-queens problem, generates permutations and combinations, and finds schedules that satisfy constraints.

Some recursions solve the same subproblem many times. Counting the ways to build a 30 cm shelf from 1 cm and 2 cm pieces calls ways(28) from both ways(29) and ways(30), and the repetition multiplies all the way down. Memoization stores each answer the first time it's computed:

from functools import lru_cache

@lru_cache(maxsize=None)
def ways(length):
    if length <= 1:
        return 1
    return ways(length - 1) + ways(length - 2)

print(ways(30))   # 1346269, computed with 31 distinct calls

functools.cache (Python 3.9+) is shorthand for lru_cache(maxsize=None). The arguments must be hashable, so pass tuples rather than lists, and the function must be pure: its result must depend only on its arguments. Caching a function that reads changing global state, a file or the clock returns stale answers. Unbounded caches also keep every result in memory; set maxsize when inputs vary widely.

Memoization helps only when subproblems repeat. Backtracking searches that build different partial solutions each time, such as listing all subsets, have nothing to reuse.

Branching recursion grows exponentially. If each step has b choices and there are d steps, there are bᵈ complete outcomes:

Each call can be trivially simple and the whole search still impossible to finish. Recursion is a way of expressing an algorithm; it doesn't make one efficient.

Before writing a search, estimate the number of outcomes. If it's too large, look for ways to cut it: prune choices that violate constraints as early as possible, memoize repeated subproblems (turning many exponential searches into polynomial dynamic programming), or switch to a different algorithm, such as a greedy rule or a library solver. Generating outcomes lazily with yield instead of building one big list keeps memory under control even when you need to scan many results.

Task: enumerate badge choices, add a constraint and explain when memoization can reduce repeated subproblems. Generate three-symbol badges from A, B and C with no two identical symbols next to each other:

def badges(prefix, remaining):
    if remaining == 0:
        yield prefix
        return
    for symbol in "ABC":
        if prefix and prefix[-1] == symbol:
            continue                         # prune: constraint violated
        yield from badges(prefix + symbol, remaining - 1)

designs = list(badges("", 3))
print(len(designs), designs[:4])     # 12 ['ABA', 'ABC', 'ACA', 'ACB']

Pruning cuts the outcomes from 27 to 12. Memoization wouldn't help here, because each call builds a different prefix, but it would help to merely count designs, where count(last_symbol, remaining) is called repeatedly with the same arguments. For the worked check, mutable backtracking must restore the state changed for the current choice before exploring the next option.

The documentation covers functools.lru_cache and cache and itertools for ready-made combinatorics. Continue with introduction to machine learning or revisit recursion. Practise with the Python exercises and Python quiz.