TwiddleLab / Код / Рекурсия: функции, которые вызывают себя
Доверься меньшей задаче
Что ты узнаешь
- Рекурсивное мышление: сделай один маленький кусочек и доверь остаток меньшему вызову.
- Всю цепочку в голове не прослеживаешь. Если меньший вызов верен, твой один шаг делает верным и большой.
- Каждой цепочке всё равно нужен пол: сумма пустого списка 0, а 0! равно 1.
- 5! = 120 это число способов расставить 5 песен по порядку.
Как идёт урок
Сложи список без цикла. Друг помогает.
Друг за раз складывает любой список покороче. Разрежь список так, чтобы тебе досталось одно сложение.
Теперь друг это уменьшенная копия той же машины.
Каждая машина оставляет первое число и передаёт остальное машине поменьше. Заполни каждую ячейку.
sum_list([3, 1, 4]) = 3 + sum_list([1, 4]) = 3 + 1 + sum_list([4]) = 3 + 1 + 4 + sum_list([]) = 3 + 1 + 4 + 0 = 8. Сложения происходят по пути обратно вверх.
Доверься коробке: скоростной раунд.
Фиолетовая коробка уже ответила на меньшую задачу. Не открывай её. Закончи большую.
Рекурсивное мышление.
У рекурсивного мышления три части. Первая: сделай маленький кусочек (первое число, первую букву).
Вторая: доверь той же функции решить меньший остаток. Не прослеживай его в голове.
Третья: базовый случай для самой маленькой задачи, с прямым ответом: сумма пустого списка 0.
Собери fact(n) = n x (n - 1) x ... x 1.
Доверься fact(n - 1). Пол: fact(0) равно 1. Сделай так, чтобы fact(5) давала 120.
fact(n) это n, умноженное на fact(n - 1): твой кусочек это умножение на n, остальное делает меньший вызов. fact(0) = 1, потому что если вернуть там 0, каждое произведение станет 0.
Запусти машину факториала на 5.
Машины открываются по пути вниз. Ответы возвращаются вверх.
rev("hello") должна давать "olleh", а даёт "hello". Исправь.
Доверься rev от остатка, потом реши, куда идёт первая буква.
Баг ставил первую букву обратно вперёд, поэтому каждый уровень отменял переворот. Если довериться rev(s[1:]) и добавить s[0] в конец, слово перевернётся.
Твой факториал считает способы расставить плейлист. Когда он перевалит за 1000?
3 песни можно сыграть в 6 порядках. Двигай число песен; твоя fact(n) считает порядки.
Порядки n песен: n вариантов для первой, n - 1 для второй, до 1. Это произведение n!, та же рекурсия: n! = n x (n - 1)!. 6! = 720 и 7! = 5040.
Все эти машины ждут. Какая ответит первой?
Нажми на машину, потом «Проверить».
Вызовы делаются сверху вниз, но каждая машина ждёт нижнюю. Ответить без ожидания может только sum_list([]), поэтому ответы начинаются с пола и поднимаются обратно.
Предыдущий урок: Базовый случай · Следующий урок: Деревья вызовов · Часть курса: Рекурсия: функции, которые вызывают себя
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
