---

Рекурсивные функции без кэширования могут выполнять одни и те же вычисления многократно и приводить к экспоненциальной сложности. Без использования специальных инструментов программа может буквально застрять.

---

Пример¶

Уже при таких цифрах разница в скорости выполнении будет на порядок и больше.

Плохо:

def calculate_fibonacci(num):
    if num <= 1:
        return num
    return calculate_fibonacci(num - 1) + calculate_fibonacci(num - 2)


print(calculate_fibonacci(100))

Хорошо:

import functools


@functools.lru_cache(maxsize=None)
def calculate_fibonacci(num):
    if num <= 1:
        return num
    return calculate_fibonacci(num - 1) + calculate_fibonacci(num - 2)


print(calculate_fibonacci(100))