3 Рекурсия изнутри
Дерево вызовов растёт по шагам. Счётчики «с памятью» и «без» бегут наперегонки.
Дерево вызовов
Кружок — вызов is_winning(n), на ребре — ход. Цвет появляется, когда вызов вернул ответ.
Подробнее
Функция пробует ходы по порядку и останавливается на первом ходе в П, поэтому раскрываются не все ветви. При n = 0 ни один ход не подходит (условие m <= n ложно), функция возвращает False — позиция П.
Без памяти одни и те же позиции считаются снова и снова — это видно в таблице «Сколько раз считали позицию k». С памятью каждая позиция считается один раз, остальные вызовы берут ответ из словаря memo. Поэтому вызовов не больше 1 + n·s, где s — число разрешённых ходов.
Наперегонки
Одна и та же функция, два запуска на сервере: без памяти и с памятью.
Вызовы при n = 5, 10, …, 40
Шкала логарифмическая: каждая линия сетки — в 10 раз больше предыдущей.
Подробнее
Без памяти сервер по-настоящему запускает рекурсию и присылает счёт по ходу работы. Если вызовов слишком много, число находится без запуска: вызовы(k) = 1 + сумма вызовов(k − m) по тем ходам m, которые функция успевает попробовать, — до первого хода в П включительно.
Без памяти вызовы растут экспоненциально: на логарифмической шкале столбцы удлиняются почти равными шагами. С памятью — не больше 1 + n·s, где s — число разрешённых ходов.
| n | без памяти | с памятью |
|---|