Курс языка программирования Raku / Функциональное, конкурентное, реактивное и веб-программирование / Функциональное программирование / Рекурсия

Базовый случай

Всякой рекурсивной подпрограмме нужен базовый случай: условие, при котором она возвращает ответ, не вызывая себя снова. Без него подпрограмма вызывала бы себя бесконечно.

В факториале базовым случаем было «$n равно 1 или меньше». Вот другой пример — обратный отсчёт до нуля:

sub countdown($n) {
    return if $n < 1;   # базовый случай: останавливаемся
    say $n;
    countdown($n - 1);  # рекурсивный шаг
}

countdown(3);

Программа печатает:

3
2
1

Первая строка — базовый случай: когда $n опускается ниже 1, подпрограмма немедленно возвращается и цепочка вызовов заканчивается. Рекурсивный шаг всегда движется к базовому случаю, вызывая countdown с меньшим числом.

Если забыть про базовый случай или если шаги до него никогда не доберутся, рекурсия не остановится и программа в конце концов упадёт. У правильной рекурсивной подпрограммы всегда есть две вещи: базовый случай, завершающий рекурсию, и шаг, приближающий к нему каждый вызов.

Навигация по курсу

← Тест — Рекурсия   |   Тест — Базовый случай →

💪 Или перейдите сразу к упражнениям этого раздела.