TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Запоминай ответы: мемоизация
Что ты узнаешь
- Мемоизация: веди блокнот ответов. Прежде чем что-то считать, загляни в него; после запиши ответ.
- В Python блокнот это словарь: ключ n, значение fib(n).
- С ним fib(n) делает 2n - 1 вызовов вместо миллионов: каждое значение считается один раз.
- Та же идея считает пути по сетке: каждая клетка считается один раз из соседей.
Как идёт урок
Приложение задаёт один и тот же трудный вопрос 1000 раз. Решать его 1000 раз?
fib(15) сделала 1973 вызова. Теперь у неё есть блокнот: когда fib(k) известна, она записана. Угадай, сколько вызовов теперь.
Побудь блокнотом для fib(6).
Каждый новый вызов: нажми на кружок, чтобы посчитать его, или на его страницу в блокноте, если ответ уже там.
Без блокнота fib(6) считает fib(4) дважды, fib(3) трижды, а fib(2) пять раз. С ним, когда любую из них спрашивают второй раз, ответ читается за один шаг.
fib(15) с блокнотом и без.
Та же функция, тот же ответ. Посчитай вызовы.
Мемоизация.
Мемоизация значит запоминать ответы. Веди блокнот; это словарь, memo = {}.
Прежде чем считать fib(n), проверь: if n in memo, return memo[n]. Посчитав, запиши: memo[n] = ответ.
Каждый ответ вычисляется один раз. Дерево вызовов сжимается из пышного дерева в одну цепочку.
Дай fib блокнот.
Сначала проверь блокнот, потом базовый случай, потом посчитай и запиши. Сделай так, чтобы fib(30) печатала 832040.
Поиск в блокноте должен идти до всякой работы, иначе он ничего не экономит. Запись memo[n] перед возвратом заполняет блокнот для следующих вызовов.
Что в блокноте после fib(6)?
Заполни каждую страницу. Каждое значение это сумма двух предыдущих страниц.
fib(2) = 1 + 0 = 1, fib(3) = 1 + 1 = 2, fib(4) = 2 + 1 = 3, fib(5) = 3 + 2 = 5, fib(6) = 5 + 3 = 8. До строки memo[n] = ... доходят только n от 2 и больше.
Сколько путей от старта до дальнего угла, если двигаться только вправо или вниз?
paths(клетка) = paths(клетка сверху) + paths(клетка слева). Заполни сетку, каждую клетку один раз.
Направь свою fib с блокнотом на месяц 30 и месяц 70.
Без блокнота fib(70) считалась бы годами. Нажми «Запуск».
Сколько вызовов делает fib(20) с блокнотом?
fib(6) сделала 11 вызовов, fib(15) 29, fib(30) 59.
С блокнотом fib(n) вызывает fib(n - 1), fib(n - 2) ... до fib(1): n вызовов. По пути второй вызов каждого уровня это поиск или базовый случай: ещё n - 1. Итого 2n - 1.
Оба дерева считают fib(6). Какое пользовалось блокнотом?
Нажми на дерево, потом «Проверить».
Пышное дерево пересчитывает fib(4), fib(3) и fib(2). Тонкое считает каждую один раз; повторные запросы это пунктирные поиски, под которыми ничего нет.
Предыдущий урок: Деревья вызовов · Следующий урок: Ханойские башни · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
