Some recursive algorithms solve the same subproblem over and over: these are overlapping subproblems. Memoization remembers the answer to every subproblem the first time it is computed and then returns the stored result. This often turns exponential time into polynomial time.

The call tree of `fib(5)`: 15 calls with repeats, 6 values with a cache
The call tree of fib(5): 15 calls with repeats, 6 values with a cache

Fibonacci: the exponential blow-up

fib(n) calls fib(n-1) and fib(n-2), and each of them does the same again. For example fib(3) is computed twice in the tree of fib(5). The number of calls grows roughly like 1.618^n.

python
calls = 0

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

for n in (10, 20, 25):
    calls = 0
    fib(n)
    print(n, calls)
text
10 177
20 21891
25 242785

Manual memoization: a dictionary

The simplest way is to keep results in a dict. The function first checks n in memo, returns at once on a hit, otherwise computes and stores. Now every n is computed only once.

python
calls = 0
memo = {}

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