Курс 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-підпрограмами →

💪 Або перейдіть одразу до вправ цього розділу.