Recursion and Backtracking Questions

The idea in plain words

The power set of a list is the collection of all its subsets, including the empty one and the whole list. A list of n distinct items has 2^n subsets, because each item is either in a subset or out of it (two choices per item).

A backtracking way to generate them: keep a growing list path. Every path you ever hold, at any moment, is itself a subset, so record it. Then try extending it with each item that comes after the last one used (start index), recurse, and remove the item again. Moving only forward through the list is what keeps the items in their original relative order and avoids producing [2, 1] as well as [1, 2].

The brute-force alternative uses a bitmask: an integer whose binary digits each stand for one item (bit i is 1 if nums[i] is in the subset). Looping the mask from 0 to 2^n - 1 and picking items by bit also works and is just as large in output. For [1, 2, 3] the masks give:

mask 000 -> []
mask 001 -> [1]
mask 010 -> [2]
mask 011 -> [1, 2]
mask 100 -> [3]
mask 101 -> [1, 3]
mask 110 -> [2, 3]
mask 111 -> [1, 2, 3]

The recursive version extends naturally to constraints, because a branch can be abandoned the moment it breaks one.

Code

from itertools import combinations, islice
from typing import Iterator, List


def subsets(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int) -> None:
        result.append(path[:])              # every path is a subset; store a copy
        for i in range(start, len(nums)):
            path.append(nums[i])            # choose
            backtrack(i + 1)                # explore
            path.pop()                      # undo

    backtrack(0)
    return result


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


def subsets_stream(nums: List[int]) -> Iterator[List[int]]:
    path: List[int] = []

    def backtrack(start: int) -> Iterator[List[int]]:
        yield path[:]
        for i in range(start, len(nums)):
            path.append(nums[i])
            yield from backtrack(i + 1)
            path.pop()

    yield from backtrack(0)


print(list(islice(subsets_stream(list(range(30))), 5)))
count = sum(1 for _ in islice(subsets_stream(list(range(20))), 2_000_000))
print("subsets of 20 items:", count)

# count the yield from layers between the generator that yields [0, 1, 2] and the caller
outer = subsets_stream([0, 1, 2, 3])
for s in outer:
    if s == [0, 1, 2]:
        layers, g = 0, outer
        while g.gi_yieldfrom is not None:
            layers, g = layers + 1, g.gi_yieldfrom
        print("yield from layers above [0, 1, 2]:", layers)
        break

# check against the standard library
for n in range(0, 9):
    items = list(range(n))
    expected = [list(c) for r in range(n + 1) for c in combinations(items, r)]
    assert sorted(subsets(items)) == sorted(expected)
    assert len(subsets(items)) == 2 ** n
print("checks passed")

# state leakage demo
shared = []
bad = []
bad.append(shared)
shared.append(1)
print("alias shows later change:", bad)

Output:

[[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]
[[], [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]]
subsets of 20 items: 1048576
yield from layers above [0, 1, 2]: 4
checks passed
alias shows later change: [[1]]

For [1, 2, 3] the output is the 8 subsets (2^3) in depth-first order: [], then everything starting with 1, then everything starting with 2, then [3].

Trace for [1, 2, 3]

This instrumented version of the same recursion prints each record, choose and undo, indented by recursion depth (depth only controls the indentation):

from typing import List


def subsets_traced(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []

    def backtrack(start: int, depth: int) -> None:
        pad = "  " * depth
        result.append(path[:])
        print(f"{pad}record {path}")
        for i in range(start, len(nums)):
            path.append(nums[i])
            print(f"{pad}choose {nums[i]}")
            backtrack(i + 1, depth + 1)
            path.pop()
            print(f"{pad}undo {nums[i]}")

    backtrack(0, 0)
    return result


subsets_traced([1, 2, 3])

Output:

record []
choose 1
  record [1]
  choose 2
    record [1, 2]
    choose 3
      record [1, 2, 3]
    undo 3
  undo 2
  choose 3
    record [1, 3]
  undo 3
undo 1
choose 2
  record [2]
  choose 3
    record [2, 3]
  undo 3
undo 2
choose 3
  record [3]
undo 3

Each record line is one subset. Each undo brings path back to what it was before the matching choose, so the next sibling starts clean.

No shared mutable state

The line result.append(path[:]) stores a copy (path[:] makes a new list). Without it, result would contain 8 references to the one list path, which ends up empty after all the undo steps, so the output would be 8 empty lists. Aliasing means two names pointing at the same list object. The last lines of the program demonstrate it: appending shared into bad stores a reference, not a snapshot, so a later change to shared shows up inside bad. Copies also guarantee that a caller who edits one returned subset does not change another.

Complexity

• Time: the recursion makes exactly 2^n calls (one per subset), and each call copies its path, of average length n/2. So the total is O(n * 2^n). The output itself contains n * 2^(n-1) numbers in total (for n = 3 that is 12), so no algorithm can do better than that order when it must return every subset in full.
• Space: O(n) for the recursion stack and path, plus the output, which is O(n * 2^n) elements. If you count the output as space, the output dominates.

Handling n up to 30: stream, do not materialize

With n = 30 there are 2^30 = 1,073,741,824 subsets, far too many to hold in one list. The subsets_stream generator (a function that yields one value at a time and pauses until the caller asks for the next) produces each subset on demand, so memory stays O(n) no matter how many are consumed. islice(g, k) takes just the first k values from a generator and stops. The program takes the first 5 for 30 items, and counts all 1,048,576 subsets of 20 items without ever storing them. Time is still exponential if you consume everything; streaming fixes memory, not running time. yield from backtrack(i + 1) means "pass along every value the inner generator produces". The subset [0, 1, 2] is produced by the fourth nested backtrack call (the one with start = 3), so it is handed up through four yield from layers (the three backtrack calls above it and the outer subsets_stream) before the caller sees it; the program counts them and prints 4. A subset with d items crosses d + 1 layers, and d is at most n, so every subset costs O(n) to deliver plus the copy.

Edge cases and common mistakes

• Empty list: returns [[]] (one subset, the empty one), not [].
• A single item returns [[], [x]].
• The input is assumed to hold unique integers; with duplicates you would get repeated subsets unless you sort and skip equal neighbours at the same depth.
• Recording path without copying (aliasing), or recording only at the leaves: here every node records, which is what captures subsets of every length.
• Recursion depth is at most n, so there is no recursion-limit concern at n = 30.

Running the code

python3.12 power_set.py

Save the first program above as power_set.py and the traced version as its own file. No packages are needed (the itertools import is from the standard library, used for the check and for islice).

The idea in plain words

A permutation is an ordering of all the items. For n distinct items there are n! of them (n choices for the first slot, n-1 for the next, and so on). The backtracking idea: fill the slots from left to right; at each slot, try every item that has not been used yet, recurse to fill the remaining slots, then take the item back so the next candidate can try the same slot.

The brute-force alternative, generating all n^n sequences and discarding the ones with repeats, wastes almost all of its work. Backtracking never builds a repeat in the first place.

Approach 1: a used array

Keep path (the arrangement so far) and used[i] (whether nums[i] is already in path). A full-length path is one permutation.

Approach 2: swap in place and swap back

Treat the array itself as the state. Slots before index first are fixed. To fill slot first, swap each candidate arr[i] (for i >= first) into that slot, recurse on first + 1, then swap back. This needs no used array and no separate path list.

from itertools import permutations
from typing import List


def permutations_used(nums: List[int]) -> List[List[int]]:
    result: List[List[int]] = []
    path: List[int] = []
    used = [False] * len(nums)

    def backtrack() -> None:
        if len(path) == len(nums):
            result.append(path[:])          # copy: path keeps changing
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True                  # choose
            path.append(nums[i])
            backtrack()                     # explore
            path.pop()                      # undo
            used[i] = False

    backtrack()
    return result


def permutations_swap(nums: List[int]) -> List[List[int]]:
    arr = nums[:]                           # work on a copy of the input
    result: List[List[int]] = []

    def backtrack(first: int) -> None:
        if first == len(arr):
            result.append(arr[:])
            return
        for i in range(first, len(arr)):
            arr[first], arr[i] = arr[i], arr[first]     # choose: put arr[i] at slot first
            backtrack(first + 1)                        # explore
            arr[first], arr[i] = arr[i], arr[first]     # undo: swap back

    backtrack(0)
    return result


print(permutations_used([1, 2, 3]))
print(permutations_swap([1, 2, 3]))

for n in range(0, 7):
    items = list(range(n))
    expected = [list(p) for p in permutations(items)]
    assert permutations_used(items) == expected
    assert sorted(permutations_swap(items)) == sorted(expected)
print("checks passed")
print("empty list:", permutations_used([]), permutations_swap([]))


def leaky(nums):
    result, path, used = [], [], [False] * len(nums)
    def backtrack():
        if len(path) == len(nums):
            result.append(path)             # BUG: no copy
            return
        for i in range(len(nums)):
            if not used[i]:
                used[i] = True; path.append(nums[i])
                backtrack()
                path.pop(); used[i] = False
    backtrack()
    return result


print("without copying:", leaky([1, 2, 3]))


def swap_no_undo(nums):
    arr, result = nums[:], []

    def backtrack(first):
        if first == len(arr):
            result.append(arr[:])
            return
        for i in range(first, len(arr)):
            arr[first], arr[i] = arr[i], arr[first]
            backtrack(first + 1)
            # BUG: no swap back here

    backtrack(0)
    return result


print("swap without swapping back:", swap_no_undo([1, 2, 3]))

Output (the itertools import is only used by the check against the standard library; the solutions do not call it):

[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 2, 1], [3, 1, 2]]
checks passed
empty list: [[]] [[]]
without copying: [[], [], [], [], [], []]
swap without swapping back: [[1, 2, 3], [1, 3, 2], [3, 1, 2], [3, 2, 1], [1, 2, 3], [1, 3, 2]]

Both methods find the same six permutations. For a sorted input the used version yields them in lexicographic order, meaning dictionary order: compare first items, and break ties with the second item, then the third (the check above compares it, in order, with itertools.permutations for range(n) inputs). The swap version produces [3, 2, 1] before [3, 1, 2] because swapping reorders the tail (the swap trace below shows exactly where), so compare results as sets or sorted lists, not by position.

Trace of the used version on [1, 2, 3]

This instrumented version of the used recursion prints each choose and undo, indented by depth (depth only controls the indentation); the swap version's instrumented copy follows it in the same block:

from typing import List


def permutations_used_traced(nums: List[int]) -> None:
    path: List[int] = []
    used = [False] * len(nums)

    def backtrack(depth: int) -> None:
        pad = "  " * depth
        if len(path) == len(nums):
            print(f"{pad}full {path} -> record")
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            print(f"{pad}choose {nums[i]} path={path}")
            backtrack(depth + 1)
            path.pop()
            used[i] = False
            print(f"{pad}undo {nums[i]} path={path}")

    backtrack(0)


def permutations_swap_traced(nums: List[int]) -> None:
    arr = nums[:]

    def backtrack(first: int) -> None:
        pad = "  " * first
        if first == len(arr):
            print(f"{pad}full {arr} -> record")
            return
        for i in range(first, len(arr)):
            arr[first], arr[i] = arr[i], arr[first]
            print(f"{pad}swap slots {first},{i} arr={arr}")
            backtrack(first + 1)
            arr[first], arr[i] = arr[i], arr[first]
            print(f"{pad}swap back {first},{i} arr={arr}")

    backtrack(0)


permutations_used_traced([1, 2, 3])
print("--- swap version ---")
permutations_swap_traced([1, 2, 3])

The first half of its output is the used trace:

choose 1 path=[1]
  choose 2 path=[1, 2]
    choose 3 path=[1, 2, 3]
      full [1, 2, 3] -> record
    undo 3 path=[1, 2]
  undo 2 path=[1]
  choose 3 path=[1, 3]
    choose 2 path=[1, 3, 2]
      full [1, 3, 2] -> record
    undo 2 path=[1, 3]
  undo 3 path=[1]
undo 1 path=[]
choose 2 path=[2]
  choose 1 path=[2, 1]
    choose 3 path=[2, 1, 3]
      full [2, 1, 3] -> record
    undo 3 path=[2, 1]
  undo 1 path=[2]
  choose 3 path=[2, 3]
    choose 1 path=[2, 3, 1]
      full [2, 3, 1] -> record
    undo 1 path=[2, 3]
  undo 3 path=[2]
undo 2 path=[]
choose 3 path=[3]
  choose 1 path=[3, 1]
    choose 2 path=[3, 1, 2]
      full [3, 1, 2] -> record
    undo 2 path=[3, 1]
  undo 1 path=[3]
  choose 2 path=[3, 2]
    choose 1 path=[3, 2, 1]
      full [3, 2, 1] -> record
    undo 1 path=[3, 2]
  undo 2 path=[3]
undo 3 path=[]

Read it as: after choose 1, the slots 2 and 3 are filled by every arrangement of {2, 3}; undo 1 returns path to empty so the first slot can try 2.

Trace of the swap version on [1, 2, 3]

The second half of the same program's output, after the --- swap version --- line. Each line shows the whole array arr; indentation equals first, the number of slots already fixed:

swap slots 0,0 arr=[1, 2, 3]
  swap slots 1,1 arr=[1, 2, 3]
    swap slots 2,2 arr=[1, 2, 3]
      full [1, 2, 3] -> record
    swap back 2,2 arr=[1, 2, 3]
  swap back 1,1 arr=[1, 2, 3]
  swap slots 1,2 arr=[1, 3, 2]
    swap slots 2,2 arr=[1, 3, 2]
      full [1, 3, 2] -> record
    swap back 2,2 arr=[1, 3, 2]
  swap back 1,2 arr=[1, 2, 3]
swap back 0,0 arr=[1, 2, 3]
swap slots 0,1 arr=[2, 1, 3]
  swap slots 1,1 arr=[2, 1, 3]
    swap slots 2,2 arr=[2, 1, 3]
      full [2, 1, 3] -> record
    swap back 2,2 arr=[2, 1, 3]
  swap back 1,1 arr=[2, 1, 3]
  swap slots 1,2 arr=[2, 3, 1]
    swap slots 2,2 arr=[2, 3, 1]
      full [2, 3, 1] -> record
    swap back 2,2 arr=[2, 3, 1]
  swap back 1,2 arr=[2, 1, 3]
swap back 0,1 arr=[1, 2, 3]
swap slots 0,2 arr=[3, 2, 1]
  swap slots 1,1 arr=[3, 2, 1]
    swap slots 2,2 arr=[3, 2, 1]
      full [3, 2, 1] -> record
    swap back 2,2 arr=[3, 2, 1]
  swap back 1,1 arr=[3, 2, 1]
  swap slots 1,2 arr=[3, 1, 2]
    swap slots 2,2 arr=[3, 1, 2]
      full [3, 1, 2] -> record
    swap back 2,2 arr=[3, 1, 2]
  swap back 1,2 arr=[3, 2, 1]
swap back 0,2 arr=[1, 2, 3]

Read it as: at first = 0, swapping slot 0 with slot 2 turns [1, 2, 3] into [3, 2, 1], so the free tail is now [2, 1] and its first arrangement [3, 2, 1] is recorded before the swap at slots 1,2 produces [3, 1, 2]. That is why [3, 2, 1] precedes [3, 1, 2]. Each swap back line restores the array to what it was before the matching swap, so the next candidate starts from a clean state.

How shared-state bugs are avoided

1. Copy on record: path[:] or arr[:] stores a snapshot. The without copying line of the output shows what happens without it: six entries that are all the same (now empty) list.
2. Symmetric undo: every choose has an exact reverse right after the recursive call (path.pop() plus used[i] = False; the second swap). If one half is missing, later branches see leftovers.
3. The input is not mutated: the swap version copies nums first, so the caller's list is unchanged.

Complexity

• Time: there are n! permutations, each copied in O(n) when recorded, so O(n * n!) just for the output. The search tree (every call, partial and full) has about e * n! nodes in total, where e is the constant 2.718... . At depth j (j slots filled) there are n!/(n-j)! nodes: choices for the first slot times choices for the second, and so on. For n = 3 the depths 0, 1, 2, 3 have 1, 3, 6, 6 nodes, which sum to 16, and 16 / 3! = 2.67. That ratio is already near e and climbs toward it: adding n!/(n-j)! for j = 0 to 7 gives 13700 nodes for n = 7, and 13700 / 7! = 2.7183. So the whole tree is only about 2.7 times the number of leaves. The used version scans n slots at each node, so it is also O(n * n!) overall. The swap version does O(1) work per child (no scan), also O(n * n!) because of the copies.
• Space: O(n) auxiliary (recursion depth n, plus path and used), not counting the output, which is n * n! numbers. If the caller does not need every permutation at once, a generator that yields each one keeps memory at O(n).

Edge cases and common mistakes

• Empty list returns [[]] (one permutation, the empty one); a single item returns [[x]].
• With duplicate values both routines emit repeated permutations. For the used version, sort the input and skip nums[i] when it equals nums[i - 1] and used[i - 1] is false. That sorted-neighbour rule does not carry over to the swap version, because swaps move values around and equal values stop being neighbours; there, keep a set of the values already tried in the current slot and skip any repeat.
• Using used = [] as a list of values and testing x in used makes each check O(n); a boolean array is O(1).
• Forgetting to copy (the without copying line) or forgetting to swap back (the swap without swapping back line, which lists [1, 2, 3] and [1, 3, 2] twice and never produces [2, 1, 3] or [2, 3, 1]).

Running the code

python3.12 permutations_backtracking.py

Save the program above as permutations_backtracking.py. No packages are needed (standard library only).

The idea in plain words

Naive recursive Fibonacci recomputes the same subproblems over and over. fib(6) asks for fib(5) and fib(4), but fib(5) also asks for fib(4), so the work for fib(4) is done twice, and the repetition compounds down the tree. Caching (remembering each answer the first time it is computed, also called memoization) removes the repeats, so each value is computed once.

The call tree for n = 6 and the call count

The program prints one line per call, indented by depth in the tree, and counts the calls.

calls = 0


def fib(n, depth=0):
    global calls
    calls += 1
    print("  " * depth + f"fib({n})")
    if n < 2:
        return n
    return fib(n - 1, depth + 1) + fib(n - 2, depth + 1)


print("value:", fib(6))
print("naive calls:", calls)

memo_calls = 0


def fib_cached(n, cache, depth=0):
    global memo_calls
    memo_calls += 1
    if n < 2:
        note = "base case"
    elif n in cache:
        note = "cache hit"
    else:
        note = "computed"
    print("  " * depth + f"fib({n})  {note}")
    if n < 2:
        return n
    if n not in cache:
        cache[n] = fib_cached(n - 1, cache, depth + 1) + fib_cached(n - 2, cache, depth + 1)
    return cache[n]


print("cached value:", fib_cached(6, {}))
print("cached calls:", memo_calls)


# call counts for growing n (naive), counted not timed
def count_calls(n):
    return 1 if n < 2 else 1 + count_calls(n - 1) + count_calls(n - 2)


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


for n in (10, 20, 30):
    print(n, count_calls(n), 2 * fib_loop(n + 1) - 1)
for n in (10, 20, 30):
    print(n, round(fib_loop(n + 1) / fib_loop(n), 4))


def cached_call_count(n):
    seen, count = {}, 0

    def go(m):
        nonlocal count
        count += 1
        if m < 2:
            return m
        if m not in seen:
            seen[m] = go(m - 1) + go(m - 2)
        return seen[m]

    go(n)
    return count


for n in (0, 1, 2, 6, 30):
    print("cached calls for n =", n, ":", cached_call_count(n))

Output:

fib(6)
  fib(5)
    fib(4)
      fib(3)
        fib(2)
          fib(1)
          fib(0)
        fib(1)
      fib(2)
        fib(1)
        fib(0)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
  fib(4)
    fib(3)
      fib(2)
        fib(1)
        fib(0)
      fib(1)
    fib(2)
      fib(1)
      fib(0)
value: 8
naive calls: 25
fib(6)  computed
  fib(5)  computed
    fib(4)  computed
      fib(3)  computed
        fib(2)  computed
          fib(1)  base case
          fib(0)  base case
        fib(1)  base case
      fib(2)  cache hit
    fib(3)  cache hit
  fib(4)  cache hit
cached value: 8
cached calls: 11
10 177 177
20 21891 21891
30 2692537 2692537
10 1.6182
20 1.618
30 1.618
cached calls for n = 0 : 1
cached calls for n = 1 : 1
cached calls for n = 2 : 3
cached calls for n = 6 : 11
cached calls for n = 30 : 59

The tree has 25 calls for n = 6. Counting the lines per argument: fib(6) 1, fib(5) 1, fib(4) 2, fib(3) 3, fib(2) 5, fib(1) 8, fib(0) 5, which sums to 25. Only 7 distinct values (0 through 6) are ever needed, yet fib(2) is computed 5 times and fib(3) 3 times.

The call count follows its own recurrence: calls(n) = 1 + calls(n-1) + calls(n-2) (one call for this node, plus all the calls made under each child), with calls(0) = calls(1) = 1. It solves to 2 * fib(n+1) - 1, and the reason is short. Add 1 to both sides: calls(n) + 1 = (calls(n-1) + 1) + (calls(n-2) + 1). So the sequence calls(n) + 1 obeys exactly the Fibonacci rule (each term is the sum of the previous two). Its first two terms are calls(0) + 1 = 2 and calls(1) + 1 = 2, which are 2 * fib(1) and 2 * fib(2). A sequence with the Fibonacci rule that starts at twice the Fibonacci start stays twice Fibonacci forever, so calls(n) + 1 = 2 * fib(n+1). Check for n = 6: fib(7) = 13, so 2 * 13 - 1 = 25. The first for n in (10, 20, 30) loop in the program prints the counted value next to the formula (10 177 177, 20 21891 21891, 30 2692537 2692537), and they agree (for n = 30, 2,692,537 calls, with fib(31) = 1,346,269).

Asymptotic time and space (naive version)

• Time: the call count grows like fib(n) itself. The ratio of consecutive Fibonacci numbers settles at about 1.618 (the second for n in (10, 20, 30) loop prints fib(n+1) / fib(n) as 1.6182, 1.618 and 1.618 for n = 10, 20 and 30). That number is the golden ratio, written phi, equal to (1 + sqrt(5)) / 2. So the calls grow like phi^n: every extra step of n multiplies the work by about 1.618. Growth like that is exponential (n sits in the exponent). Compare polynomial growth such as n^2 or n^3, where n is the base: doubling n multiplies n^2 work by 4, but adding just 10 to n here multiplies the work by about 123 (1.618^10). The time is O(phi^n). It is usually quoted as O(2^n), which is a looser upper bound: still true, because 1.618^n never exceeds 2^n, but not as tight as it could be. Going from n = 20 to n = 30 multiplied the calls from 21,891 to 2,692,537, about 123 times.
• Space: O(n). Time is spent on the whole tree, but the stack only holds one root-to-current path at a time, and the longest path (always taking n-1) has n frames: for n = 6 that is fib(6), fib(5), fib(4), fib(3), fib(2), fib(1).

What changes with a cache

With the cache in fib_cached, fib(6) made 11 calls instead of 25. The cached tree printed above shows where each call goes. fib(6) down to fib(2) are marked computed: the five real computations (n = 2 through 6), each done once. Every computed node makes two calls. The 11 calls break down as 5 computed, 3 base cases (fib(1) and fib(0) under fib(2), and fib(1) under fib(3)) and 3 cache hit calls: the second call of fib(4) is fib(2), the second call of fib(5) is fib(3), and the second call of fib(6) is fib(4). Each hit returns the stored value at once, without recursing, which is what cuts the tree down. For n >= 1 the cached version makes 2n - 1 calls (n = 6 gives 11, n = 1 gives 1): there are n - 1 computed nodes (n = 2 through n), each makes two calls, and every call except the first is one of those, so the total is 2(n-1) + 1. The last lines of the output count it for n = 0, 1, 2, 6 and 30 (1, 1, 3, 11, 59). The formula does not apply at n = 0, where the single call is a base case and there are no computed nodes, so the count is 1, not -1. Time drops from exponential to O(n). Space stays O(n): the recursion depth is still n, and for n >= 1 the cache holds n - 1 entries.

This is the bridge to dynamic programming: the subproblems overlap, so storing them turns a tree of repeated work into a straight line.

Edge cases and common mistakes

• fib(0) and fib(1) are the base cases (one call each). Forgetting that both are needed, or writing n == 1 only, makes fib(0) recurse into negative numbers.
• A mutable default cache (def fib(n, cache={})) is shared between calls in Python; here the cache is passed in so every top-level call starts clean.
• For n near 1000 or more, the cached recursive version needs more than Python's default limit of 1000 frames and raises RecursionError; a loop avoids it.

Running the code

python3.12 fib_calls.py

Save the program above as fib_calls.py. No packages are needed. The output is deterministic.