TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Базовый случай
Что ты узнаешь
- Базовый случай это строка, которая отвечает, не вызывая снова. Это пол.
- Рекурсивный случай вызывает функцию на меньшей задаче, на шаг ближе к полу.
- Без пола или с шагами, которые его перепрыгивают, стек переполняется: переполнение стека, в Python это RecursionError.
- Базовый случай плюс рекурсивный случай устроены так же, как первое домино плюс толчок.
Как идёт урок
Эта функция вызывает себя вечно. Где она остановится?
Строки, которая её остановит, нет. Поставь, сколько карточек накопится, прежде чем что-то сломается.
Запусти и смотри на стек.
Она печатает 3, 2, 1, 0, -1 и продолжает.
Ни один вызов не заканчивается, поэтому ни одна карточка не снимается. Python держит предел стека, чтобы сбежавшая функция падала с понятной ошибкой, а не съедала всю память.
Теперь есть проверка на 0, но она ничего не делает. Исправь.
Сделай так, чтобы countdown(3) печатала 3, 2, 1 и останавливалась.
return сразу заканчивает текущий вызов. С ним countdown(0) не доходит до рекурсивного вызова, и цепочка останавливается на полу.
Базовый и рекурсивный случай.
Базовый случай отвечает сразу, не вызывая снова. Это пол: здесь if n == 0, return.
Рекурсивный случай вызывает функцию на меньшей задаче: countdown(n - 1).
Каждый рекурсивный вызов должен двигаться ближе к базовому случаю. Если он туда не доходит, стек переполняется: переполнение стека.
Пол или падение?
Для каждой функции нажми «Приземлится», если она доходит до пола, или «Переполнится», если нет. Потом смотри.
stairs(5) спускается на 2 ступеньки за раз и падает. Исправь пол.
Поменяй один символ, чтобы она печатала 5, 3, 1, Down.
n идёт 5, 3, 1, -1, -3 и так далее: ровно 0 оно не бывает. С n <= 0 вызов stairs(-1) ловится полом, и цепочка останавливается.
Собери power(b, e): b, умноженное само на себя e раз.
Её пол: всё в степени 0 равно 1. Сделай так, чтобы power(2, 3) давала 8.
power(2, 3) = 2 x power(2, 2) = 2 x 2 x power(2, 1) = 2 x 2 x 2 x power(2, 0), а power(2, 0) это пол: 1. Если вернуть там 0, всё умножится в 0.
В математике это называется индукцией. Подпиши домино.
У базового и рекурсивного случая есть близнецы в ряду падающих домино.
В рекурсии базовый случай это место, где цепочка точно закончится, а рекурсивный случай связывает каждый вызов с меньшим. В индукции первое домино это место, где всё начинается, а правило связывает каждый случай со следующим. Обеим нужны обе части.
Пусть твоя функция степени построит стек ровно из 6 карточек.
Двигай e. Каждый раз твой код запускает power(2, e). Потом «Проверить».
Каждый вызов уменьшает e на 1, пока e не станет 0. Начиная с e = 5, это вызовы для 5, 4, 3, 2, 1 и 0: шесть карточек, и останавливается только последний.
Предыдущий урок: Функция вызывает сама себя · Следующий урок: Доверься задаче поменьше · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
