Рекурсия с мемоизацией

Мемоизация в рекурсии

Иногда рекурсивная функция вычисляет одно и то же значение много раз.

Классический пример — последовательность Фибоначчи. Давайте посмотрим, что происходит, когда мы вычисляем $F(5)$ с помощью наивной рекурсивной формулы.

Заметьте, что:

• $F(3)$ вычисляется дважды;
• $F(2)$ вычисляется трижды.

Но эти значения никогда не меняются, поэтому пересчитывать их снова и снова не нужно.

Как мы можем этого избежать?

Идея

Решение — мемоизация.

Мы создаём структуру данных, которая хранит уже вычисленные значения. Затем, когда вызывается рекурсивная функция:

• если мы находимся в базовом случае, сразу возвращаем ответ;
• если значение уже было вычислено, возвращаем сохранённый результат;
• иначе вычисляем его рекурсивно, сохраняем и возвращаем.

Для чисел Фибоначчи это означает:

• если $$, вернуть ;