Рекурсия с запоминанием
Рекурсия с запоминанием
Бывает, что при использовании рекурсии мы считаем одно и то же значение по несколько раз.
Для примера рассмотрим числа Фибоначчи и схему работы рекурсии для вычисления значения .
Заметим, что вычислялся два раза, а — целых три раза!
При этом их значения никогда не меняются, и можно было бы не вычислять одни и те же значения снова и снова. Как это улучшить?
Решение этой проблемы — запоминание (memoization).
Идея состоит в том, чтобы создать массив и хранить уже подсчитанные значения.
Тогда при вызове рекурсии выполняются следующие шаги:
