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

Рекурсивная подпрограмма

Рекурсивная подпрограмма — это та, которая вызывает саму себя. Классический пример — факториал: факториал n равен n, умноженному на факториал n - 1.

sub fact($n) {
    $n <= 1 ?? 1 !! $n * fact($n - 1);
}

say fact(5); # 120

Прочитайте тело как два случая, соединённых тернарным оператором ?? !!:

• когда $n равно 1 или меньше, ответ — просто 1;
• иначе ответ — это $n, умноженное на fact($n - 1), то есть на ту же подпрограмму, вызванную с меньшим числом.

Каждый вызов отслаивает один множитель и запрашивает меньший факториал, пока число не дойдёт до 1, после чего вызовы разворачиваются обратно: fact(5) — это 5 * fact(4), что есть 5 * 4 * fact(3) и так далее вниз до 1.

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

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

← Рекурсия   |   Тест — Рекурсия →

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