Recursion and Backtracking

A function that calls itself

Recursion solves a problem by calling the same function on a smaller version of that problem. Every recursive solution needs:

1. a base case that can be answered directly,
2. progress toward that base case, and
3. a rule that combines the smaller answer into the current answer.

For factorial, factorial(n) = n × factorial(n - 1) and factorial(0) = 1. The calls wait on the call stack until the base case returns:

factorial(4)
4 × factorial(3)
4 × 3 × factorial(2)
4 × 3 × 2 × factorial(1)
4 × 3 × 2 × 1 × factorial(0)
4 × 3 × 2 × 1 × 1 = 24

Recursion is especially natural for trees, divide-and-conquer algorithms and nested structures. A loop is usually clearer for a simple linear walk.

From recursion to backtracking

Backtracking is recursive search over choices. At each step:

1. choose one allowed option,
2. explore what follows from it,
3. undo the choice before trying the next option.

The undo step is what keeps one branch from contaminating another. A partial answer can also be pruned as soon as it cannot lead to a valid complete answer.

Cost and safety

The running time follows the number of states explored. Generating every subset of n items takes O(2ⁿ) because there are 2ⁿ results; no implementation can output them all faster than that. Pruning makes many practical searches far smaller, but it does not automatically change the worst case.

The call stack uses memory too. A recursion depth of d requires O(d) stack frames. Very deep recursion can overflow the language's stack, so iterative traversal with an explicit stack is safer for a chain with thousands of nodes.

Generate combinations

This program generates all size-two study pairs in input order. start prevents duplicates, and removing the most recent subject performs the unchoose step.

def combinations(items, size):
    result, choice = [], []

    def search(start):
        if len(choice) == size:
            result.append(choice.copy())
            return
        needed = size - len(choice)
        for i in range(start, len(items) - needed + 1):
            choice.append(items[i])
            search(i + 1)
            choice.pop()

    search(0)
    return result


subjects = ["Maths", "Science", "English", "History"]
pairs = combinations(subjects, 2)
print("count:", len(pairs))
for pair in pairs:
    print(" + ".join(pair))

count: 6
Maths + Science
Maths + English
Maths + History
Science + English
Science + History
English + History

A reusable checklist

When designing a backtracking solution, write down the state, the choices available from that state, the completion condition, and the reason a branch can be pruned. Then make every mutation have an obvious matching undo. This pattern covers permutations, grid paths, word searches, constraint puzzles and many scheduling problems.