TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Деревья вызовов
Что ты узнаешь
- Функция, которая вызывает себя дважды, строит дерево вызовов: каждый кружок это один вызов.
- fib(n) = fib(n - 1) + fib(n - 2) снова и снова считает одни и те же маленькие вызовы: это повторная работа.
- Программа обходит дерево вглубь, левое раньше правого. Путь от вершины до текущего вызова это стек.
- Число вызовов растёт примерно в 1,6 раза с каждым шагом n: fib(40) делает больше 331 миллиона.
Как идёт урок
Крошечная функция считает кроликов. Месяц 15 мгновенно, месяц 40 минуты. Почему?
fib(n) = fib(n - 1) + fib(n - 2): пары кроликов этого месяца это пары прошлого месяца плюс позапрошлого. Сколько вызовов делает fib(15)?
Вырасти дерево вызовов для fib(5).
Каждый кружок это вызов, число это его n. fib(0) и fib(1) отвечают сразу.
fib(5) нужны fib(4) и fib(3). Но fib(4) тоже нужен fib(3). Первый ответ никто не запоминает, поэтому он считается снова, и то же происходит ниже.
Увеличивай n. Как быстро растёт дерево?
Дойди до 15 и сравни со своей ставкой.
Дерево вызовов и повторная работа.
Когда функция вызывает себя больше одного раза, её вызовы образуют дерево вызовов. По кружку на вызов.
fib просит fib(n - 1) и fib(n - 2), и оба просят одни и те же меньшие вызовы. Это повторная работа: одинаковые поддеревья, каждый раз посчитанные с нуля.
Из-за повторной работы дерево и время растут так быстро.
Найди повторы в дереве fib(6).
Нажми на каждую копию нужного вызова. Быстро и без промахов.
В каком порядке программа делает эти вызовы?
Нажимай на вызовы fib(4) по одному, по порядку.
fib(4) сначала вызывает fib(3) и ждёт. fib(3) вызывает fib(2), а тот fib(1), потом fib(0). Только когда вся левая сторона ответила, программа поднимается и делает правый вызов.
Сколько вызовов делает fib(7)?
Один для самой fib(7), плюс все вызовы fib(6), плюс все вызовы fib(5).
calls(7) = 1 + calls(6) + calls(5) = 1 + 25 + 15 = 41. В общем виде calls(n) = 2 x fib(n + 1) - 1.
Нанеси вызовы на график по n. Какая форма?
Тяни каждую синюю точку к её числу вызовов. Правило то же: 1 + два предыдущих.
Каждое число примерно равно сумме двух предыдущих, поэтому их отношение устанавливается около 1,6 (золотое сечение). Умножение на один и тот же множитель каждый шаг это экспоненциальный рост.
Месяц 40. Сколько вызовов делает fib(40)?
Тяни метку по этой большой шкале, потом «Проверить». Засчитывается, если ошибка не больше чем в 3 раза в любую сторону.
calls(40) = 2 x fib(41) - 1 = 331 160 281. 1973 x 1,6 в 25-й степени это около 250 миллионов: правильный порядок.
Предыдущий урок: Доверься задаче поменьше · Следующий урок: Запоминаем ответы: мемоизация · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
