Информатика · объяснение и практика
Повторяющиеся подзадачи: как запоминание меняет дерево вызовов
На подсчёте путей по ступеням различаем дерево вызовов и набор разных подзадач. Показываем, как кэш сохраняет готовые ответы и почему он не исправляет неверную рекурсию.

В теме Переменные, ветвления, циклы и функции · Учебная карта
Главная мысль
Мемоизация сохраняет результат подзадачи под ключом её входных данных. При повторном обращении с тем же ключом готовое значение берут из памяти вместо повторного вычисления тела. Это полезно, когда рекурсия многократно встречает одинаковые подзадачи. Само правило рекурсии и базовые случаи при этом остаются прежними; правильность ответа не возникает из одного наличия кэша.
Одинаковая подзадача может встретиться в разных ветвях
Пусть до вершины осталось n ступеней и за ход разрешено пройти одну или две. Обозначим число последовательностей ходов через F(n). При нуле ступеней имеется один вариант — ничего больше не делать; при одной ступени тоже один вариант. Для n не меньше двух последний или первый ход разбивает варианты на две группы, поэтому F(n)=F(n−1)+F(n−2). В этой задаче n всегда неотрицательное целое.
Для вычисления F(5) требуется F(4) и F(3). Но F(4) само требует F(3), так что одна и та же задача возникает повторно. Если каждый раз раскрывать рекурсию заново, её потомки тоже пересчитываются. Число узлов дерева вызовов и число разных значений n оказываются различными величинами. Повторное появление состояния не создаёт новый математический ответ, хотя без запоминания программа повторяет работу.
Записываем ответ после его вычисления
Кэш можно представить таблицей «n → F(n)». Перед вычислением проверяют, есть ли ключ. Если есть, возвращают готовый ответ. Иначе вычисляют результат по базовому случаю или рекуррентной формуле, записывают и возвращают. В однопоточном вычислении с пустым неограниченным кэшем каждое впервые достигнутое состояние раскрывается один раз. Повторные обращения остаются, но уже не разворачивают всё поддерево.
В Python такой приём поддерживает functools.cache. Это инструмент запоминания результата функции по аргументам, а не новое правило подсчёта путей. Для ключей требуются хешируемые аргументы. В нашем случае целое n подходит. Если ответ зависит ещё и от набора разрешённых ходов, эту зависимость нельзя скрывать в изменяемой внешней настройке: один ключ n уже не различает две разные задачи.
Пример
Вычислим F(5) при ходах длины 1 или 2, базах F(0)=F(1)=1 и пустом кэше. Какие ответы для состояний от нуля до пяти понадобятся?
Получаются F(0)=1, F(1)=1, F(2)=2, F(3)=3, F(4)=5, F(5)=8. Разных состояний шесть. Готовая запись F(3)=3 используется повторно без нового раскрытия её потомков. Итог восемь считает последовательности ходов, а шесть — разные состояния расчёта; это разные величины.
Экономия времени оплачивается памятью
Для этой рекурсии число сохранённых состояний растёт линейно с n, как и число раскрытий после мемоизации. Глубина вложенных вызовов всё ещё может расти с n, поэтому ограничение стека никуда не исчезает. Значения ответа тоже увеличиваются и требуют всё больше разрядов: утверждение о линейном числе состояний не означает постоянную стоимость арифметики с числами любого размера. Для большого входа полезно рассмотреть и последовательное вычисление циклом.
Кэш не стоит автоматически применять к получению текущего времени, случайному выбору или функции с важными побочными действиями. Повторное использование старого ответа может изменить смысл программы. Также он не превращает бесконечный переход к новым состояниям в конечный: если рекурсия не достигает базы, нечего сохранять как готовый результат. Отдельно проверяют корректность формулы, завершение, количество разных состояний, память и правила актуальности сохранённых значений.
От чтения к действию
А теперь — вы
Частые вопросы
Мемоизация убирает сам рекурсивный вызов при каждом повторе?
Обращение к функции может состояться, но готовый ключ позволяет вернуть результат без повторного вычисления её исходного тела.
Достаточно ли кэшировать n, если разрешённые ходы меняются?
Нет. Ключ должен различать все данные, от которых зависит ответ. Иначе сохранённое значение может относиться к другой задаче.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Как базовый случай останавливает рекурсию
Проверяем базовый случай и движение к нему на рекурсивной сумме, ограничиваем допустимый ввод и различаем доказательство завершения с ограничением глубины стека.
Открыть темуКак версия ключа помогает не выдавать устаревший кэш
На изменённой учебной задаче разбираем версионный ключ кэша, связываем вопрос с решением и отделяем время жизни от актуальности данных.
Открыть тему