PART 4 · DSA AND COMPLEXITY · CHAPTER 25

Recursion and backtracking

FreeLesson 50 of 78

Recursion solves a problem by solving a smaller copy of it. Backtracking is recursion that tries a choice, explores it, then undoes it and tries the next.

Every recursive function needs two things: a base case that stops (an empty list, a leaf node), and a step that makes the problem smaller. Forget the base case and you get a RecursionError; forget to shrink and you get the same thing.

RECURSION ON NESTED DATAPYTHON 3.12

def depth(obj):                 # how deeply nested is it?
    if isinstance(obj, dict) and obj:
        return 1 + max(depth(v) for v in obj.values())
    if isinstance(obj, list) and obj:
        return 1 + max(depth(v) for v in obj)
    return 0                           # base case: a plain value

payload = {"order": {"id": 114,
                     "items": [{"sku": 4, "tags": ["new"]}]}}
print(depth(payload), depth(42), depth({}))

Output

5 0 0

Time O(n) for n values in the payload; space O(d) for nesting depth d, from the call stack. Flattening JSON (P7) is the same walk.

BACKTRACKING: EVERY SUBSET, EVERY ORDERPYTHON 3.12

def subsets(items):
    out, path = [], []
    def go(i):
        if i == len(items):
            out.append(path.copy())     # one complete choice
            return
        go(i + 1)                       # choice 1: skip items[i]
        path.append(items[i])           # choice 2: take items[i]
        go(i + 1)
        path.pop()                      # undo before returning
    go(0)
    return out

def permutations(items):
    if len(items) <= 1:
        return [items[:]]
    return [[x] + rest for i, x in enumerate(items)
            for rest in permutations(items[:i] + items[i + 1:])]

print(subsets(["city", "status", "month"]))
print(len(permutations(list("abcd"))), permutations([1, 2, 3])[:3])

Output

[[], ['month'], ['status'], ['status', 'month'], ['city'], ['city', 'month'], ['city', 'status'], ['city', 'status', 'month']]
24 [[1, 2, 3], [1, 3, 2], [2, 1, 3]]

Recursion is a good fit	Prefer a loop or explicit stack
Data is naturally nested: JSON, trees, folders	Depth could exceed about 1,000 (Python's default limit)
Divide and conquer: merge sort, binary search	A simple running total or scan
Exploring choices: subsets, permutations, paths	Production code on untrusted, deeply nested input

BACKTRACKING WITH PRUNINGPYTHON 3.12

def valid_brackets(n):
    out = []
    def go(s, opened, closed):
        if len(s) == 2 * n:
            out.append(s); return
        if opened < n:
            go(s + "(", opened + 1, closed)
        if closed < opened:          # prune: never close early
            go(s + ")", opened, closed + 1)
    go("", 0, 0)
    return out

print(valid_brackets(3))

Output

['((()))', '(()())', '(())()', '()(())', '()()()']

Pruning cuts branches that can never lead to a valid answer, so the search explores far fewer than the 2^(2n) raw strings. Good backtracking is mostly good pruning.

Practice before you move on

Write a recursive function that counts every key, at every depth, of one record in customers.json.
List every pair of products in products.csv whose prices add up to at most 1,500.