Nahoru
 

Koncová rekurze

Už při slovu rekurze se některým programátorům ježí vlasy na hlavě, nicméně správný kodér ji zná. Každý by měl mít ve svém arzenálu zvláště jeden specifický typ rekurze, jímž je tzv. „koncová rekurze“.

Pokud nejste obeznámeni s rekurzí, přečtěte si o ní v článku „Funkcionální programování“. Jedná se o velice zajímavý styl programování a v některých případech ušetří obrovský objem práce. V případě že ovládáte jak cykly, tak rekurzi, budete moci zvolit adekvátní přístup k problému a vyřešit jej tím nejlepším, nejpřehlednějším a nejelegantnějším způsobem.

Nejprve si upřesněme, jak funguje volání funkcí z pohledu běhu programu. Jestliže zavoláme nějakou funkci, program do ní vkročí a začne vykonávat její příkazy. Jak si však program pamatuje, kam se vrátit? Před skočením do funkce si program uloží tzv. návratovou adresu na vrchol zásobníku. Při potřebě vyskočit z funkce ven si ze zásobníku návratovou hodnotu přečte a tím pádem ví, kam „skočit“ zpět.

Schéma skoku do funkce a uložení návratové adresy na zásobník
Obrázek č. 1: Schéma skoku do funkce a uložení návratové adresy na zásobník
//Zavolání funkce. Současná pozice se uloží
// na zásobník.
DoWeHaveTurtles();
//Pokračování v kódu

void DoWeHaveTurtles()
{
    //Provedení kódu uvnitř funkce
    printf("We have turtles!");
    
    //Načtení návratové adresy ze zásobníku a vrácení na místo volajícího
}

Bohužel, rekurze jakožto opakované volání funkcí s sebou přinese oproti cyklům jistou režii navíc, a to ve formě uchovávání a výběru návratových adres na zásobníku. Společně s návratovými adresami se na zásobník také ukládají lokální proměnné. Čím hlouběji se zanoříme, tím více dat navíc musíme uložit. Někdy může mít rekurze tak ohromnou hloubku, že ji zásobník nebude schopný celou pojmout (dojde mu paměť) a dočkáme se slavného erroru „Stack overflow“. Přetečení zásobníku většinou nastává pouze v případech, kdy se rekurze „zacyklila“.

//Nekonečná rekurze
void StackOverflowTrigger()
{
    StackOverflowTrigger();
}

Zmíněná koncová rekurze má obrovskou výhodu právě v tom, že jej kompilátor dokáže do strojového kódu přeložit a rozběhnout takovým způsobem, aby si nemusel pamatovat návratové adresy a lokální proměnné. Zásobník si tedy vystačí s jedinou návratovou adresou a jednou sadou lokálních proměnný, které jsou z prvního „normálního“ volání funkce. Kompilátor z rekurzivní funkce v podstatě vytvoří funkci se smyčkou.

int FactorialTailRecursion(int index, int prevResult = 1)
{
    if (index == 0)
        return prevResult;

    //Nepotřebujeme si nic v kontextu pamatovat, vynoření bude jednoduché,
    // rekurzi můžeme snadno předělat na smyčku.
    return FactorialTailRecursion(index - 1, prevResult * index);
}
//Toto je hrubý námět, jak by mohla vypadat funkce FactorialTailRecursion
// přeložená optimalizátorem. Každý programátor by to pravděpodobně napsal
// jako tradiční cyklus, nicméně strojový jazyk zná pouze skoky v podobě "goto".
//
// Jinými slovy: manuálně to lze napsat daleko lépe, ale toto je
// universální postup.
int FactorialLoopFromTailRecursion(int index, int prevResult = 1)
{
//Pomocné proměnné - jsou nutné z důvodů chyb způsobených
// špatným pořadím přiřazení
int indexTMP = index;
int preResultTMP = prevResult;

//Návěstí pro začátek funkce
zacatekFunkce:

    //Dosazení do proměnných (jako v parametrech)
    index = indexTMP;
    prevResult = preResultTMP;

    if (index == 0)
        return prevResult;

    //Místo vnoření do další funkce přepíšeme současné proměnné, a to
    // úplně stejným způsobem jako při vkládání parametrů.
    indexTMP = index - 1;
    preResultTMP = prevResult * index;

    //Vrátíme se na začátek funkce (bývalé zanoření)
    goto zacatekFunkce;
}

Kdy však člověk nebo kompilátor pozná, že je daná rekurze koncová? Je to principiálně jednoduché: Pokud si rekurzivní funkce nepotřebuje pamatovat a použít žádné prostředky při vynořování (kromě návratové adresy), jedná se o koncovou rekurzi. Jestli tedy existuje nějaká nekoncová rekurze a chceme ji předělat na koncovou kvůli efektivitě, stačí všechny proměnné, které by normálně „vysely ve vzduchu“ a čekaly na vynořovací proces, předat parametrem do dalšího zanoření.

int Factorial(int index)
{
    if (index == 0)
        return 1;

    //Číslo "index" zamezuje předělání na smyčku,
    // protože si jej potřebujeme pamatovat při vynořování.
    // Tato rekurze je neefektivní.
    return index * Factorial(index - 1);
}

int FactorialTailRecursion(int index, int prevResult = 1)
{
    if (index == 0)
        return prevResult;

    //Nepotřebujeme si nic v kontextu pamatovat, vynoření bude jednoduché,
    // rekurzi můžeme snadno předělat na smyčku.
    return FactorialTailRecursion(index - 1, prevResult * index);
}

Bohužel, některé rekurze se do té koncové přepsat nedají. Jsou to hlavně ty, které rekurzivní strom volání dělí do více větví. Zpravidla platí, že koncovou rekurzi můžeme vytvořit pouze pro nevětvená zanoření. Pokud totiž funkce tvoří více větví rekurzivního stromu, pochopitelně se jejich výsledky musí nějak zpracovat, což zamezuje předělání na koncovou rekurzi.

Nyní leckoho může napadnout otázka: „Proč bych tuto rekurzi měl vůbec psát, když ji mohu snadno realizovat jako smyčku? Vždyť to zvládne i kompilátor!“ Ano, skutečně tomu tak je, nicméně úplně každou rekurzi lze napsat jako cyklus a naopak. Pokud jazyk umí obojí, můžeme si vybrat a docílit tak co nejvíce přehledného a elegantního řešení. Zkrátka máme díky tomu na výběr. Důležité je podotknout, že některé jazyky, například funkcionální jazyk lisp, smyčky neumí, proto je zde znalost koncové rekurze důležitá.

I když je koncová rekurze úžasná a lehce optimalizovatelná, musíme být na pozoru. Některé jazyky nativně koncovou rekurzi optimalizovat neumí, například Java nebo Python. Jazyky jako C#, C++, C, novější JavaScript, Prolog a všechny funkcionální jazyky koncovou rekurzi optimalizovat umí.

Koncová rekurze dokáže být kompilátorem přeložena velice efektivně, oproti „běžné“ rekurzi a je dokonce i jednodušší na pochopení. Tím se pochopitelně stává daleko atraktivnější. Umožňuje nám volit mezi cykly a rekurzí s vědomím, že oboje bude stejně efektivní. Můžeme tak psát maximálně přehledný a elegantní kód.

Pozn.: Vysvětlené procesy ve skutečnosti fungují trochu složitěji. Tento článek slouží pouze pro představu a jednoduché pochopení principů koncové rekurze.