Funkcionální JavaScript - Rekurze s ocasem

Rekurze patří mezi základní techniky funkcionálního programování, protože umožňuje velmi hutně a stručně vyjádřit, čeho chceme dosáhnout, a to bez použití cyklů. Mezi programátory má ale velmi špatnou pověst, protože je velmi jednoduché "vyrobit" stack overflow. Není to však vždy pravda. V moderních jazycích (jako je v JavaScript) může mít rekurze ocas a pak je stejně efektivní jako cyklus. Ne, "ocas" není žádná zkratka z angličtiny ani hipsterská šifra, je to prostě normální český vocas, oháňka, ohon, chvost.

Rekurze je deklarativní

Rekurzivně napsané algoritmy jsou velmi deklarativní a připomínají matematické vzorce. Například, faktoriál pro n spočítáme pomocí vzorce:

0! = 1
n! = n * (n-1)!

Což můžeme přímo přepsat pomocí rekurzivní funkce:

JavaScript bohužel nemá pattern matching, a tak je nutné nějak přidat podmínku pro ukončení rekurze a zápis není tak hezky deklarativní jako v jazycích, které pattern matching mají. Nicméně i tak je zápis daleko blíže matematickému vyjádření než for/while cyklus.

Pomocí rekurze můžeme jednoduše zapsat celou řadu užitečných funkcí pro operace s kolekcemi. Trik je rozdělit kolekci pomocí destructuringu na první prvek x (head) a zbytek xs (tail) a definovat co se má stát s jedním prvkem a rekurzivně to samé aplikovat na zbytek kolekce:

Všimněte si, jak moc užitečný je destructuring a spread operátor, kterým můžeme spojovat pole a prvky bez pomocných funkcí (např. [...reverse(xs), x]). Pokud destructuring a spread neznáte, mrkněte třeba na dokumentaci Babelu, bude se vám to určitě hodit.

Dokonce se tak dá napsat i quicksort, což je super, protože tím se vždycky vytahovali Haskellisti, že to umí napsat na pět řádků, tak teď jim to můžeme natřít, že to umíme taky a ještě to poběží ve všech devajsech na světě, heč.

A teď ten slíbený ocas

Problém všech výše uvedených příkladů je, že rekurze s každou iterací konzumuje stack. Pro malé kolekce to bude bez problémů fungovat, ale když pak v produkčním prostředí přijdou tisíce řádků, může dojít ke stack overflow.

Jenže. Co kdybychom funkci factorial přepsali tak, aby návratová hodnota rekurzivního volání byla zároveň návratovou hodnotou funkce samotné?

Výsledekem volání factorial(69) je teď volání factorial(68, 69 * accumulator). Jinými slovy, výsledek factorial(68, 69 * accumulator) se už nijak dál nezpracovává, jen se vrátí. A tomu se říká tail position, neboli poloha ocasu (a proto my puberťáci radši používáme angličtinu).

Pokud je rekurzivní volání v tail position, vlastně už není nutné držet stack pro každou iteraci, protože se s ním po návratu z rekurze stejně nic nedělá. A proto mají některé chytré jazyky kompilátory a interprety, které dokáží automaticky rozeznat tail position a fakticky převést rekurzi na cyklus. Jmenuje se to tail call optimization, neboli optimalizace ocasu (hahaha hehehe). A ES2015 je chytrý jazyk (jak jinak)! A Babel umí převést rekurzi na cyklus už dnes:

Původní verze funkce factorial není tail recursion proto, že se výsledek volání factorial(n - 1) ještě před vrácením násobí n.

Hmm takže aby byla rekurze efektivní, musíme všechny příklady nahoře přepsat tak, aby měly accumulator? To je ale pěknej opruz! Navíc se dost ztrácí hutnost a čitelnost. Co s tím?

Reduce all the lists!

Špatná zpráva je: Ano, aby byla rekurze efektivní a šla automaticky optimalizovat, musíme výše uvedené příklady přepsat. Dobrá zpráva je, že je tu jedna operace s kolekcemi, která má akumulaci takříkajíc v krvi a navíc se jedná o tail recursion:

Tato operace je navíc tak obecná, že většinu ostatních operací s kolekcemi lze přepsat pomocí reduce, a díky tomu i ony budou využívat tail call optimization:

(Když říkám "většinu" operací, všimněte si že třeba pro take(n) to nedává smysl. Nemá smysl iterovat přes všechny prvky kolekce (jak to dělá reduce), když vás zajímá prvních n prvků.)

Vtip dne

Implementace tail recursion se v různých jazycích liší. Javistům jsme se posmívali minule, takže teď je na řadě jediný možný způsob tail recursion v Pythonu:

Tail recursion je navíc děsně vtipná sama o sobě. Akorát musíte nastudovat poměrně dlouhé vysvětlení.

A pokud to pořád ještě nechápete, klikněte zde.