Мемоизация в рекурсии
Иногда рекурсивная функция вычисляет одно и то же значение много раз.
Классический пример — последовательность Фибоначчи. Давайте посмотрим, что происходит, когда мы вычисляем с помощью наивной рекурсивной формулы.

Заметьте, что:
- вычисляется дважды;
- вычисляется трижды.
Но эти значения никогда не меняются, поэтому пересчитывать их снова и снова не нужно.
Как мы можем этого избежать?
Идея
Решение — мемоизация.
Мы создаём структуру данных, которая хранит уже вычисленные значения. Затем, когда вызывается рекурсивная функция:
- если мы находимся в базовом случае, сразу возвращаем ответ;
- если значение уже было вычислено, возвращаем сохранённый результат;
- иначе вычисляем его рекурсивно, сохраняем и возвращаем.
Для чисел Фибоначчи это означает:
- если , вернуть ;
