Некоторые рекурсивные алгоритмы многократно решают одни и те же подзадачи — это перекрывающиеся подзадачи. Мемоизация запоминает ответ каждой подзадачи при первом вычислении и затем возвращает готовый результат. Так экспоненциальное время часто сводится к полиномиальному.

Дерево вызовов `fib(5)`: 15 вызовов с повторами, а с кэшем — 6 значений
Дерево вызовов fib(5): 15 вызовов с повторами, а с кэшем — 6 значений

Фибоначчи: экспоненциальный взрыв

fib(n) вызывает fib(n-1) и fib(n-2), а они снова делают то же самое. Например, fib(3) в дереве fib(5) считается дважды. Число вызовов растёт примерно как 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

Ручная мемоизация: словарь

Самый простой способ — хранить результаты в dict. Функция сначала проверяет n in memo, при попадании сразу возвращает значение, иначе считает и записывает. Теперь каждое n вычисляется только один раз.

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]