Recursion Trees and Repeated Work

When one call makes two calls

Fibonacci numbers: each one is the sum of the two before (0, 1, 1, 2, 3, 5, 8, ...). The direct recursive version looks lovely:

calls = 0

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

for n in [10, 20, 25]:
    calls = 0
    print(f"fib({n}) = {fib(n)} using {calls} calls")

Output

fib(10) = 55 using 177 calls
fib(20) = 6765 using 21891 calls
fib(25) = 75025 using 242785 calls

But the number of calls explodes! fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. Drawn out, the calls form a recursion tree full of repeated work. That's about O(2ⁿ).

Remember answers: memoization

Store each answer the first time you work it out, and reuse it after that. This is called memoization:

memo = {}
calls = 0

def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1) + fib(n - 2)
    return memo[n]

print(fib(80), "using", calls, "calls")

Output

23416728348467685 using 159 calls

Think of it like this: If a friend asks “what's 37 × 49?” three times, you work it out once and remember it.

Python can also do this for you with @functools.lru_cache. Memoization is the first step towards dynamic programming (Module 17).

Remember: If a recursive function solves the same smaller problem many times, memoize it.