Tailová rekurze je speciální případ rekurze , ve kterém je jakékoli rekurzivní volání poslední operací před návratem z funkce. [1] Tento typ rekurze je pozoruhodný tím, že jej lze snadno nahradit iterací formálně a zaručeně správným přeskupením kódu funkce. V mnoha optimalizačních kompilátorech je implementována optimalizace koncové rekurze převedením na plochou iteraci. V některých funkčních programovacích jazycích specifikace zaručuje povinnou optimalizaci rekurze ocasu.
Typický mechanismus pro implementaci volání funkce je založen na ukládání návratové adresy, parametrů a lokálních proměnných funkce do zásobníku a vypadá takto:
S každým voláním rekurzivní funkce se tedy vytvoří nová sada jejích parametrů a lokálních proměnných, která se spolu s návratovou adresou umístí na zásobník, což omezuje maximální hloubku rekurze na velikost zásobníku. V čistě funkčních nebo deklarativních jazycích (jako je Prolog), kde je rekurze jediným možným způsobem, jak organizovat opakující se výpočty, se toto omezení stává extrémně významným, protože se ve skutečnosti mění v omezení počtu iterací v jakýchkoli cyklických výpočtech, výše. u kterého dojde k přetečení zásobníku .
Je snadné vidět, že potřeba rozšířit zásobník pro rekurzivní volání je diktována požadavkem na obnovení stavu volající instance funkce (tj. jejích parametrů, lokálních dat a návratové adresy) po návratu z rekurzivního volání. Pokud je ale rekurzivní volání poslední operací před ukončením volající funkce a výsledkem volající funkce by měl být výsledek, že se rekurzivní volání vrátí, na uložení kontextu již nezáleží – již se nebudou používat parametry ani lokální proměnné a zpáteční adresa je již v zásobníku. Proto v takové situaci můžete místo plnohodnotného rekurzivního volání funkce jednoduše nahradit hodnoty parametrů v zásobníku a přenést řízení na vstupní bod. Dokud provádění probíhá podél této rekurzivní větve, bude se ve skutečnosti provádět obvyklá smyčka. Když rekurze skončí (to znamená, že provedení projde terminální větví a dosáhne příkazu return z funkce), dojde okamžitě k návratu do výchozího bodu, odkud byla rekurzivní funkce volána. V žádné hloubce rekurze tedy zásobník nepřeteče.
Rekurze ocasu se často používá v programech ve funkcionálních programovacích jazycích . Je přirozené vyjádřit mnoho výpočtů v takových jazycích ve formě rekurzivních funkcí a schopnost kompilátoru automaticky nahradit koncovou rekurzi iterací znamená, že z hlediska výpočetní efektivity se rovná ekvivalentnímu kódu napsanému v iterativní formě. .
Tvůrci funkčního jazyka Scheme , jednoho z dialektů Lisp , natolik ocenili význam tail rekurze , že ve specifikaci jazyka nařídili každému kompilátoru tohoto jazyka bezchybně implementovat tail rekurzi optimalizaci a popsali přesnou sadu podmínek , které rekurzivní funkce musí splňovat, aby se v ní rekurze optimalizovala. [2]
Příklad rekurzivní funkce pro faktoriál využívající koncovou rekurzi v programovacích jazycích Scheme , C a Scala :
| Systém | C | Scala |
|---|---|---|
| ( definovat ( faktoriál n ) ( definovat ( fac-times n acc ) ( if ( = n 0 ) acc ( fac-times ( - n 1 ) ( * acc n )))) ( fac-times n 1 )) | int fac_times ( int n , int acc ) { návrat ( n == 0 ) ? acc : fac_times ( n - 1 , acc * n ); } int faktoriál ( int n ) { return fac_times ( n , 1 ); } | @tailrec def faktoriál ( it : Int , výsledek : Int = 1 ) : Int = { jestliže ( to < 1 ) výsledek jiný faktoriál ( it - 1 , výsledek * it ) } |
Je třeba poznamenat, že ne každý jednoduchý rekurzivní program je tail-rekurzivní. Mechanismus optimalizace tail rekurze popsaný výše ukládá řadu významných omezení na programy, na které jej lze aplikovat, což musí vývojáři, kteří spoléhají na použití této optimalizace, vzít v úvahu.
Jako příklad jednoduché rekurzivní funkce, která není tail-rekurzivní a nelze ji automaticky převést na iterativní funkci, uvádíme nejzřejmější rekurzivní způsob výpočtu faktoriálu , který se v učebnicích obvykle uvádí jako nejjednodušší příklad rekurzivní funkce:
| Systém | C |
|---|---|
| ( definovat ( faktoriál n ) ( if ( = n 0 ) 1 ( * n ( faktoriál ( - n 1 ))))) | int faktoriál ( int n ) { návrat ( n == 0 ) ? 1 : n * faktoriál ( n - 1 ); } |
V tomto příkladu, přestože je rekurzivní volání na posledním místě ve funkčním textu, automatická optimalizace rekurze nebude fungovat, protože ve skutečnosti poslední provedenou operací je operace násobení n , což znamená, že konec není splněna podmínka rekurze. Výše uvedené tail-rekurzivní varianty výpočtu faktoriálu jsou modifikací zřejmé metody, která je přesně zaměřena na přenos operace násobení. Metoda, která se k tomu používá, je mimochodem jedním z typických způsobů, jak převést rekurzi do koncové rekurzivní formy. Spočívá v tom, že do parametrů volání funkce se přenese množina lokálních dat, která je potřeba uložit při rekurzivním volání. V případě uvedených příkladů faktoriálového výpočtu je tímto parametrem proměnná, accve které je výsledek akumulován.
Obecně mohou být takové úpravy zcela netriviální. Zejména je možná varianta, kdy pouze jedna, „nejproblematičtější“ větev provádění funkce je provedena jako koncová rekurzivní, zatímco zbytek zůstává rekurzivní.