Recursive Problems and Their Limits

The Fibonacci warning

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)


print([fib(n) for n in range(10)])     # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

This is the textbook example of recursion, and it is also the textbook example of how recursion goes wrong.

                    fib(5)
              /                \
          fib(4)                fib(3)
         /      \              /      \
     fib(3)    fib(2)      fib(2)    fib(1)
     /    \    /    \      /    \
 fib(2) fib(1) ...        ...

fib(3) is computed twice, fib(2) three times, and it worsens rapidly. The number of calls roughly doubles for each extra n.

calls = 0


def fib_counted(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib_counted(n - 1) + fib_counted(n - 2)


for n in [10, 20, 30]:
    calls = 0
    fib_counted(n)
    print(n, "->", calls, "calls")

10 -> 177 calls
20 -> 21891 calls
30 -> 2692537 calls

fib(50) would need tens of billions of calls. The algorithm is exponential, and no faster machine rescues it.

Memoisation fixes it

from functools import lru_cache


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


print(fib(50))          # instant
print(fib(100))         # still instant
print(fib.cache_info())

lru_cache stores the result for each argument, so every value of n is computed once. The algorithm drops from exponential to linear because of one decorator line.

from functools import cache     # Python 3.9+, the same as lru_cache(maxsize=None)


@cache
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

Doing it by hand

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n < 2:
        return n
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]


print(fib(100))

Or with a loop, and no stack at all

def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib(1000))        # no recursion limit to worry about

Three versions, three lessons: naive recursion can be exponential, caching can make it linear, and iteration removes the depth limit entirely.

Problems worth solving recursively

Tower of Hanoi

def hanoi(n, source, target, spare):
    if n == 0:
        return
    hanoi(n - 1, source, spare, target)
    print(f"move disc {n}: {source} -> {target}")
    hanoi(n - 1, spare, target, source)


hanoi(3, "A", "C", "B")

The iterative solution exists and is much harder to understand. Here recursion mirrors the definition of the problem.

Permutations

def permutations(items):
    if len(items) <= 1:
        return [items]
    result = []
    for i, item in enumerate(items):
        rest = items[:i] + items[i + 1:]
        for perm in permutations(rest):
            result.append([item] + perm)
    return result


for p in permutations([1, 2, 3]):
    print(p)

Subsets

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


print(subsets([1, 2, 3]))

Merge sort

def merge_sort(items):
    if len(items) <= 1:
        return items

    middle = len(items) // 2
    left = merge_sort(items[:middle])
    right = merge_sort(items[middle:])
    return merge(left, right)


def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result


print(merge_sort([5, 2, 9, 1, 7, 3]))

Divide and conquer is where recursion is not merely acceptable but natural. The depth is only log n, so a million items need about twenty levels.

Directory style traversal

tree = {
    "src": {
        "app.py": 120,
        "utils": {"text.py": 45, "math.py": 60},
    },
    "README.md": 10,
}


def total_size(node):
    if isinstance(node, dict):
        return sum(total_size(child) for child in node.values())
    return node


def show(node, name="root", depth=0):
    pad = "  " * depth
    if isinstance(node, dict):
        print(f"{pad}{name}/  ({total_size(node)} KB)")
        for child_name, child in node.items():
            show(child, child_name, depth + 1)
    else:
        print(f"{pad}{name}  ({node} KB)")


show(tree)
print("total:", total_size(tree))

Backtracking

def solve_queens(n):
    """Place n queens on an n by n board so none attack another."""
    solutions = []

    def safe(placed, row, column):
        for r, c in enumerate(placed):
            if c == column or abs(r - row) == abs(c - column):
                return False
        return True

    def place(placed):
        row = len(placed)
        if row == n:
            solutions.append(list(placed))
            return
        for column in range(n):
            if safe(placed, row, column):
                placed.append(column)
                place(placed)
                placed.pop()          # backtrack

    place([])
    return solutions


print(len(solve_queens(6)))       # 4 solutions on a 6 by 6 board

Try a choice, recurse, and undo the choice if it leads nowhere. Backtracking is recursion at its most useful, and it powers sudoku solvers, maze solvers and constraint puzzles.

Converting recursion to iteration

# Recursive traversal of a nested structure
def walk_recursive(node, result):
    if isinstance(node, list):
        for child in node:
            walk_recursive(child, result)
    else:
        result.append(node)


# The same thing with an explicit stack - no depth limit
def walk_iterative(root):
    result = []
    stack = [root]
    while stack:
        node = stack.pop()
        if isinstance(node, list):
            stack.extend(reversed(node))
        else:
            result.append(node)
    return result


print(walk_iterative([1, [2, [3, [4]]], 5]))     # [1, 2, 3, 4, 5]

Any recursion can be rewritten with an explicit stack. You take on the bookkeeping that Python was doing for you, and in exchange you lose the depth limit.

Deciding whether to recurse

Common mistakes

• Writing naive Fibonacci and assuming it is fine.
• Adding lru_cache to a function whose arguments are unhashable, such as a list.
• Caching a function that has side effects or depends on changing state.
• Recursing over a list with slicing and creating a copy at every level.
• Forgetting to undo a choice in a backtracking search.
• Raising the recursion limit rather than converting to iteration.

Best practices

• Count the calls before trusting a recursive solution on large inputs.
• Reach for functools.cache whenever the same arguments recur.
• Use recursion for divide and conquer, tree walking and backtracking.
• Convert to an explicit stack when depth could be large.
• Always pair a backtracking step with the matching undo.

Practice

1. Count the calls made by naive Fibonacci for n = 25, then add @cache and count again.
2. Write a recursive function producing all binary strings of length n.
3. Implement quicksort recursively and explain its best and worst case depth.
4. Solve a small maze with backtracking, returning any path from start to finish.
5. Convert a recursive nested sum into an iterative version using an explicit stack.

Conclusion

Recursion is a way of describing a problem, not automatically a good way of computing it. When sub-problems repeat, cache them. When depth could be large, use a stack. When the data is genuinely a tree, recursion is the clearest code you can write.