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

💪 Или преминете направо към упражненията в този раздел.