TwiddleLab / Код / Рекурсия: функции, которые вызывают себя

Функция, которая вызывает себя

Урок 1 из 11 · 5 мин · Бесплатно, без аккаунта

Что ты узнаешь

• Рекурсия это функция, которая вызывает себя на уменьшенной версии задачи.
• Каждый рекурсивный вызов кладёт на стек вызовов новую карточку со своим n.
• print до вызова срабатывает по пути вниз; print после вызова срабатывает по пути обратно вверх.
• Строка остановки, например if n == 0, заканчивает цепочку.

Начать урок

Как идёт урок

1. Картинка внутри картинки внутри картинки. Может ли так код?

   Открывай матрёшки. В каждой спрятана та же задача, только меньше.

2. Эта функция вызывает сама себя. Сколько карточек countdown будет в самой глубокой точке?

   countdown(3) вызывает countdown(2), которая вызывает... Каждый вызов получает свою карточку на стеке, как в CS-2.9.

3. Смотри, как стек растёт и уменьшается.

   Пройди по шагам. Заметь, когда печатается каждое число.

   countdown(3) не может закончить, пока не закончит countdown(2), а та ждёт countdown(1), а та ждёт countdown(0). Поэтому все четыре карточки сразу на стеке, а потом снимаются в обратном порядке.

4. Рекурсия.

   Функция, которая вызывает саму себя, рекурсивная. Вызов внутри неё это рекурсивный вызов.

   Каждый вызов получает свежую карточку на стеке вызовов со своим n. Карточка лежит, пока этот вызов не закончится.

   Фокус в том, что каждый вызов работает над меньшей задачей, а одна строка останавливает цепочку: здесь if n == 0.

5. Следующий ход: предскажи стек.

   Перед каждым ходом нажми на то, что будет дальше. Два раунда. Собери серию.

6. Собери свой обратный отсчёт.

   Расставь строки так, чтобы countdown(3) печатала 3, 2, 1, Liftoff.

   Проверка на 0 должна идти до вызова, иначе цепочка никогда не остановится. Если печатать до вызова, числа выходят по пути вниз: 3, 2, 1.

7. Запусти обратный отсчёт с 5. Сколько карточек в самой глубокой точке?

   Поставь метку, потом «Проверить». Если угадаешь, ракета взлетит.

   Каждый вызов ждёт меньшего, поэтому в момент работы countdown(0) на стеке лежат карточки для 5, 4, 3, 2, 1 и 0: 6.

Следующий урок: Базовый случай · Часть курса: Рекурсия: функции, которые вызывают себя

Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.