Где применяется
1. Задача
Ты написал простую рекурсию. Она даёт правильный ответ. Потом запускаешь её на входе чуть побольше, и она думает десять секунд. Ошибки в ней нет. Рекурсия просто снова и снова решает одну и ту же маленькую задачу.
Возьми числа Фибоначчи: fib(n) = fib(n-1) + fib(n-2). Чтобы получить fib(30), вызовы разворачиваются в огромное дерево: всего 2 692 537 вызовов. Один только fib(5) в нём считается 121 393 раза. Каждая ветка заново делает работу, которую уже сделала другая ветка. Прибавь к n всего 2, и вызовов станет примерно в 2,6 раза больше.
Время уходит на повторы. Если отвечать на каждый отдельный вопрос один раз и запоминать ответ, всё будет работать быстро.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитfib(5)| n=2 | n=3 | n=4 | n=5 | |
|---|---|---|---|---|
| memo |
Считаем fib(5). Обычная рекурсия много раз просит одно и то же fib(n). memo запоминает каждый ответ, как только он найден.
Столбики: сколько раз fib(i) действительно вычислялось, i от 0 до 17. Вызов, на который ответила память, ничего не вычисляет, и его столбик не растёт.
Одна операция: один вызов, ответ из памяти тоже считается за один. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(2ⁿ)O(n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- рекурсивные вызовы повторяют одни и те же аргументы (пересекающиеся подзадачи)
- обычная рекурсия работает верно, но слишком медленно / экспоненциальный взрыв
- мало различных состояний, хотя дерево рекурсии огромное
- закешировать результат (i, ...) перед возвратом
- формулировка вроде Фибоначчи / подъём по лестнице / путь по сетке с намёком на кеш
Похоже, но не то
- Рекурсия (Recursion)
Обычная рекурсия каждый раз пересчитывает повторный аргумент. Кеш это вся разница.
- Динамическое программирование (1-D) (Dynamic programming (1-D))
Динамика снизу заполняет таблицу в заданном порядке. Здесь она заполняется по требованию, сверху.
- Хеш-множество / словарь (Hash set / map)
Кеш обычно хранят в словаре. Эта страница про то, когда его вообще заводить.
- Бэктрекинг (Backtracking)
Бэктрекинг обходит пути, которые все разные, поэтому ничего не повторяется. Кеш там хранит ключи, которых больше не спросят.
Стоимость это число различных аргументов на работу одного вызова. Кеш в 1e6 ключей нормален.
На LeetCode
Задачи на подсчёт, где простая рекурсия много раз задаёт один и тот же вопрос, например сколько способов подняться по лестнице или пройти по сетке. Сохраняй каждый ответ в мемо с первого раза и используй повторно.
ways(n) = ways(n минус 1) + ways(n минус 2), то есть Фибоначчи с другими начальными значениями.
fib из урока, только складываются три предыдущих числа вместо двух, в том же мемо.
gridPaths из урока под другим именем, мемо по клетке.
У каждого дома выбирай лучшее из двух, пропустить его или ограбить и перескочить на два вперёд, мемо по индексу.