Дерево вызовов и мемоизация

Пока в рекурсивном шаге один вызов, всё просто: F(10) вызывает F(9), та F(8), и всего получается десять вызовов — цепочка. Но стоит появиться двум вызовам, и картина меняется. Возьмём числа Фибоначчи: F(1) = F(2) = 1, F(n) = F(n−1) + F(n−2). F(5) вызывает F(4) и F(3). F(4) вызывает F(3) и F(2). F(3) вызывает F(2) и F(1). Получается не цепочка, а дерево, и у него на каждом уровне вдвое больше вершин, чем на предыдущем. Посчитаем, сколько вызовов делает наивная программа: F(5) — 9 вызовов, F(10) — 109, F(20) — 13 529, F(30) — 1 664 079, F(40) — 204 668 309. Это и называется экспоненциальным ростом: каждое следующее n почти удваивает работу. Откуда берётся лишняя работа. Присмотритесь к дереву: F(3) в нём встречается дважды, F(2) — трижды, F(1) — дважды. Программа честно считает их заново каждый раз, хотя ответ не меняется. Чем глубже дерево, тем больше доля повторов. Вывод, который и надо запомнить: экспонента берётся не из рекурсии как таковой, а из повторного счёта одних и тех же подзадач. Значит, лечение очевидно — считать каждую подзадачу ровно один раз и запоминать результат.

Полезно один раз посчитать порядки. Для соотношения с двумя вызовами число узлов дерева примерно удваивается с каждым шагом n: для n = 20 это около двух тысяч вызовов, для n = 30 — уже под три миллиона, для n = 40 — сотни миллионов. Ровно поэтому наивная рекурсия, отлично работающая на F(20), намертво зависает на F(40), хотя в коде не изменилось ни строчки.

Способ 1. Мемоизация (сверху вниз). Оставляем рекурсию как есть, но заводим кэш: перед вычислением смотрим, нет ли ответа в памяти; посчитав — кладём туда. ```

`` В Python то же самое делается одной строкой — декоратором ==@lru_cache(None)== из модуля ==functools==, и это самый быстрый способ спасти готовое рекурсивное решение. ==Способ 2. Восходящая динамика (снизу вверх).== Рекурсию убираем совсем и заполняем таблицу от базы к нужному значению обычным циклом. ``

• • ```
• • Что выбрать. Оба способа превращают экспоненту в линейный проход: вместо двухсот с лишним миллионов вызовов для F(40) получается сорок шагов. Восходящая динамика надёжнее, потому что не тратит стек и не упирается в предел глубины; мемоизация быстрее пишется, если соотношение сложное или аргументов несколько.
• • И приятный бонус восходящей динамики: хранить весь массив обычно не нужно. Для соотношения с двумя вызовами достаточно двух переменных:
• • ```
• • a, b = 1, 1
• • for i in range(3, n + 1):
• • a, b = b, a + b
• • print(b)
• • ```

И про размер кэша. @lru_cache(None) означает «помнить всё»; если написать @lru_cache(100), старые значения начнут вытесняться, и при обходе дерева вширь кэш перестанет помогать. В задачах ЕГЭ различных значений немного — десятки или тысячи, — поэтому ограничивать кэш незачем, и None здесь правильный выбор.

Ошибка 1. Пишут наивную рекурсию и ждут ответа. Если в соотношении два обращения к функции и n больше сорока, ответа можно не дождаться. Признак беды: программа работает дольше секунды. Ошибка 2. Кладут значение в кэш после return. Строка после return не выполняется никогда. Кэш заполняют до возврата. Ошибка 3. Считают, что мемоизация меняет ответ. Она меняет только скорость: значения получаются те же самые. Если ответы разошлись, ошибка в соотношении, а не в кэше. Ошибка 4. Не учитывают, что база может быть многоэтажной. Для F(n) = F(n−1) + F(n−3) базой должны быть три значения, иначе цикл выйдет за левый край таблицы. Ошибка 5. Считают число вызовов равным значению функции. Это разные величины: F(5) = 5, а вызовов 9. В заданиях иногда спрашивают именно количество вызовов, и тогда нужна отдельная рекуррента C(n) = 1 + C(n−1) + C(n−2). Ошибка 6. Забывают увеличить предел глубины. Даже с мемоизацией рекурсивное решение для n порядка нескольких тысяч упрётся в стандартный предел Python; либо ставьте sys.setrecursionlimit, либо переходите к циклу.

Отдельно стоит ошибка «посчитал узлы вместо листьев». В вопросе «сколько раз будет вызвана функция» считаются все узлы дерева, включая корень; в вопросе «сколько существует путей» — только листья, то есть достижения цели. Для F(5) числа Фибоначчи это 15 вызовов и 5 как значение функции — величины разные, и подставить одну вместо другой легко. Проверяйте по формулировке: «вызвана» — про узлы, «существует» или «сколькими способами» — про листья.

Считать каждое значение один раз можно двумя способами, и на экзамене годятся оба.

Мемоизация, или счёт сверху вниз. Пишем рекурсию дословно по условию и вешаем @lru_cache(None). Функция сама решает, какие значения ей нужны, и запоминает их при первом вычислении. Достоинство — код повторяет условие буквально, ошибиться почти негде. Недостаток — расход стека и ограничение на глубину.

Восходящая динамика, или счёт снизу вверх. Заводим список или словарь и заполняем его циклом от базы к искомому значению:

F = [0] * (n + 1)

F[1] = 1

for i in range(2, n + 1):

F[i] = F[i - 1] + F[i - 2]

Достоинство — нет рекурсии, а значит нет ограничения на глубину; вдобавок вся таблица остаётся под рукой, и её можно напечатать целиком. Недостаток — надо самому следить за порядком заполнения: все значения, от которых зависит F[i], должны быть посчитаны раньше.

Когда что выбирать. Если аргумент один и меняется на единицу — проще восходящая динамика, таблица заполняется естественным циклом. Если аргументов два или переходы нерегулярны (умножение на 2, деление на 3, переход к произвольному числу) — проще мемоизация, потому что придумывать порядок обхода не придётся.

И одно общее замечание: оба способа дают одинаковую сложность, линейную по числу различных состояний. Разница только в удобстве записи. Если решение работает слишком долго, причина не в выборе способа, а в том, что состояний оказалось слишком много, — и тогда менять надо не форму, а сам алгоритм.

У восходящей динамики есть приятное свойство, о котором стоит знать: часто всю таблицу хранить не нужно.

Посмотрите на соотношение F(n) = F(n−1) + F(n−2). Для вычисления очередного значения нужны ровно два предыдущих, а всё, что было раньше, больше никогда не понадобится. Значит, вместо списка из n элементов хватит двух переменных:

a, b = 1, 1 # F(1) и F(2)

for i in range(3, n + 1):

a, b = b, a + b

print(b)

Память при этом не растёт вовсе, сколько бы ни было n. Для ЕГЭ это редко критично — значения там небольшие, — но приём полезно знать: он ровно тот же, что превращает решение линии 27 из «загрузить весь файл» в «прочитать потоком».

Обратите внимание на строку a, b = b, a + b. Правая часть вычисляется целиком до присваивания, поэтому старое значение a успевает поучаствовать в сумме. Запись в две строки — a = b и потом b = a + b — даёт неверный результат: к моменту второй строки a уже испорчено. Это классическая ошибка, и она же объясняет, почему обмен значений в Python пишут одной строкой: x, y = y, x.

Общее правило: сколько предыдущих значений участвует в соотношении, столько переменных и нужно. Для F(n) = F(n−1) + F(n−3) понадобятся три. А если соотношение обращается к F(n // 2) или к произвольным значениям, «окно» не работает — там нужна полная таблица или мемоизация.

И ещё один частный случай, который экономит и память, и время: если соотношение обращается только к одному предыдущему значению, таблица не нужна вовсе — хватает одной переменной. Именно так считают факториал, сумму ряда, произведение по рекуррентной формуле. Отличить такие соотношения легко: в правой части ровно один вызов F.

Дерево вызовов полезно не только для оценки скорости. Оно же — рабочая модель для целого класса задач, где спрашивают не значение функции, а количество способов что-то сделать. Идея в том, что каждый лист дерева — это один вариант, а ветвление в вершине — это выбор из нескольких возможностей. Пример. Исполнитель умеет прибавлять 1 или прибавлять 2. Сколькими способами он может получить из 0 число n? Обозначим W(n) число способов. Последним шагом была либо «+1» (тогда до него было n−1), либо «+2» (тогда было n−2). Эти случаи не пересекаются, значит, по правилу суммы W(n) = W(n−1) + W(n−2), а базы W(0) = 1 (ничего не делать — это один способ) и W(1) = 1. Получились те же числа Фибоначчи — и это не совпадение: одно и то же дерево описывает и вычисление функции, и перебор вариантов. Что из этого следует практически. Первое: задачи на подсчёт вариантов решаются той же таблицей, что и задание 16. Пишем рекуррентное соотношение, задаём базу, заполняем таблицу снизу вверх. Второе: вершины дерева при таком счёте повторяются так же, как и раньше, поэтому наивный перебор всех вариантов не годится, а динамика годится. Третье, и самое важное для экзамена: когда пути идут подряд и один выбор не зависит от другого, число способов перемножают; когда варианты взаимоисключающие и надо выбрать один из них, число способов складывают. Это правила произведения и суммы, и на них держится всё задание 13. Ловушка: складывать можно только непересекающиеся случаи. Если один и тот же вариант попадает в две группы, он будет посчитан дважды. Поэтому разбор всегда ведут по последнему шагу: он единственный и однозначный.

Полезно помнить, что дерево вызовов и дерево вариантов — это одно и то же дерево. Когда функция считает число программ, каждый её вызов соответствует состоянию исполнителя, а каждая ветвь — команде. Поэтому всё, что верно про рост дерева вызовов, верно и про число вариантов: обе величины растут экспоненциально, и обе приручаются одним и тем же кэшем.