Rekurze

V této části se podíváme na to, co je to rekurze. Je to věc, která vám ze začátku možná může přijít trochu složitější a matoucí, obzvlášť u složitějších algoritmů. Ale občas si jejím použitím můžeme ušetřit práci.

Co je to rekurze

Rekurze je proces, při kterém funkce volá sama sebe. Nevím co bych k tomu dodal. Následující ukázka ji ukazuje:

const pozdrav = function(pocet) {
    // pokud se proměnná pocet rovná 0, tak se provádění funkce ukončí
    if (pocet <= 0) return;
    console.log("ahoj");

    // funkce volá sama sebe
    pozdrav(pocet-1);
}

pozdrav(3);

Call Stack

Důvod proč rekurze funguje je ten, že JavaScript má v sobě zabudovaný mechanismus, kterému se říká Call Stack. Je to takové místo, kam si JavaScript ukládá na jakém místě se zrovna nachází. Pokud zavoláme nějakou funkci, tak si JavaScript musí nějakým způsobem pamatovat, kde předtím skončil aby se tam po vykonání funkce mohl vrátit. Když nějakou funkci zavoláme, tak si ji JavaScript přidá na Call Stack. Ten si můžeme představit jako na sobě naskládané papíry v nějaké krabici. Pokud do krabice přidáme papír, musíme jej přidat na ostatní papíry v krabici, které se tam už nacházejí. A pokud si budeme chtít z krabice papír vzít, tak si můžeme vzít jen ten, který jsme tam vložili naposled. Takže když JavaScript narazí na příkaz, který mu říká že má jít vykonat nějakou funkci, přidá si ji na Call Stack. A když JavaScript dokončí provádění funkce, tak z Call Stacku odstraní poslední funkci, kterou do něj vložil.

Následující ukázka Call Stack vizuálně ukazuje. Napravo od ukázky kódu se nachází box, ve kterém si můžete při spuštění ukázky prohlédnou, jak se Call Stack zaplňuje. V ukázce se volá funkce, která vypíše průměr dvou předaných čísel. Tato funkce volá jinou funkci, která zase volá ještě jinou funkci. Díky tomu si můžete prohlédnout, jak se Call Stack postupně zaplňuje.

function soucet(cislo1, cislo2) {
    return cislo1 + cislo2;
}
function prumer(cislo1, cislo2) {
    return soucet(cislo1, cislo2) / 2;
}
function vypisPrumer(cislo1, cislo2) {
    const vysledek = prumer(cislo1, cislo2);
    console.log("Průměr: " + vysledek);
}

vypisPrumer(3, 5);

Příklad použití rekurze

Jako příklad použití rekurze bychom si mohli zkusit vytvořit funkci, která vypočítá faktoriál (např. faktoriál 5 je 1 * 2 * 3 * 4 * 5). Pro tuto operaci by namísto rekurze bylo lepší použít cyklus, ale pro ukázku rekurze se výpočet faktoriálu hodí.

function factorial(n) {
    if (n === 0 || n === 1){
        // pokud je n 0 nebo 1, tak se vrátí 1
        return 1;
    } else {
        // vrátí se n * hodnota vrácená funkcí factorial,
        // které předáváme jako parametr n - 1
        return n * factorial(n-1);
    }
}

const vysledek = factorial(5);
console.log("Faktoriál 5 je: " + vysledek);

Doufám že jste díky interaktivním ukázkám, které jsou ná této stránce rekurzy pochopili. Jak už jsem psal na začátku této části, ze začátku pro vás možná bude rekurze dost matoucí a budete se obtížněji orientovat v kódu, který ji používá. Myslím že je to normální. Když jsem se snažil pochopit některé algoritmy, které rekurzy používají, tak jsem si občas musel na papíře algoritmus rozepsat abych pochopil co se vlastně v kódu děje.