Мемоизация

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

Сложность: время сводится к числу различных состояний; память: O(числа состояний) под кеш. В Python проще всего применить декоратор functools.lru_cache.

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(50))  # 12586269025 — мгновенно