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

Рекурсия с multi-подпрограммами

До сих пор базовый случай был строкой внутри подпрограммы — тернарным оператором или ранним return, проверяющим аргумент. Raku предлагает более выразительный способ записать то же самое. Поскольку у подпрограммы может быть несколько кандидатов multi, базовому случаю и рекурсивному шагу можно отдать отдельные подпрограммы и позволить множественной диспетчеризации выбирать нужную при каждом вызове.

Вспомните факториал. С multi два его случая становятся двумя подпрограммами:

multi fact(0)  { 1 }
multi fact($n) { $n * fact($n - 1) }

say fact(5); # 120

Первый кандидат срабатывает, только когда аргумент в точности равен 0, — этот литерал в сигнатуре и есть базовый случай. Все остальные вызовы уходят ко второму кандидату, который умножает и рекурсивно вызывает себя. Когда fact($n - 1) наконец дойдёт до 0, диспетчеризация переключится на первого кандидата и цепочка вызовов развернётся обратно. Базовый случай больше не ветка, спрятанная в теле; это подпрограмма, существующая ради единственного значения.

Почему 0, а не 1? Потому что каждый шаг вычитает единицу, и любое начальное число рано или поздно попадает точно на 0, а 0! по определению равен 1, — значит, именно на 0 спуск по-настоящему заканчивается. Кандидат с литералом срабатывает для одного точного значения, поэтому база вида multi fact(1) вычислила бы fact(1) верно, но fact(0) провалился бы к multi fact($n) и уходил бы в рекурсию за ноль бесконечно. Остановка на 0 сохраняет подпрограмму правильной для любого неотрицательного целого числа, включая fact(0).

Особенно хорошо это читается, когда базовых случаев больше одного. Числам Фибоначчи нужны два:

multi fib(0) { 0 }
multi fib(1) { 1 }
multi fib($n) { fib($n - 1) + fib($n - 2) }

say fib(10); # 55

Каждый базовый случай — собственный однострочный кандидат, а рекурсивный кандидат обрабатывает всё остальное; никаких вложенных условий.

Литерал вроде 0 срабатывает только для этого точного значения. Когда базовый случай покрывает диапазон — «$n равно 1 или меньше», — используйте вместо литерала ограничение where:

multi fact($n where * <= 1) { 1 }
multi fact($n)              { $n * fact($n - 1) }

say fact(6); # 720

Кандидат с ограничением более специфичен, поэтому Raku пробует его первым; кандидат с простым $n ловит всё остальное.

Прежняя дисциплина остаётся в силе: каждый рекурсивный путь обязан дойти до кандидата с базовым случаем. Факториал с литералом 0, например, безопасен только для неотрицательных целых чисел — fact(-1) перешагнул бы через 0 и уходил бы в рекурсию бесконечно, потому что ни один кандидат так и не подошёл бы. Разнесение случаев по multi-подпрограммам не отменяет необходимости в базовом случае; оно лишь даёт этому базовому случаю имя и собственное место.

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

← Тест — Базовый случай   |   Тест — Рекурсия с multi-подпрограммами →

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