1. diel - Úvod do rekurzie

Vitajte pri prvej lekcii kurzu o rekurzii. Rekurzia je jednou zo zdanlivo ťažších kapitol programovania as jej praktickou aplikáciou sa v každodennom programátorskom živote príliš často nestretneme. Na druhej strane nám jej zvládnutie otvorí nové obzory a umožní riešiť problémy, ktoré by sme inými spôsobmi riešili len veľmi ťažko.

V dnešnom tutoriále o rekurzii si ukážeme, čo je to rekurzia, a ako sa vytvára rekurzívne funkcie.

Rekurzívny charakter úlohy

Začnime príkladom. Predstavme si, že chceme napísať funkciu suma(n), ktorá ako parameter preberá kladné celé číslo n a vracia súčet čísel od jednej do n. Klasickú implementáciu takejto funkcie pomocou cyklu by sme určite zvládli, my si ale môžeme všimnúť, že výpočet suma(n) v sebe obsahuje výpočet niekoľkých ďalších sum, napr. pre suma(4) dostaneme:

Vzoreček na výpočet sumy by sme teda mohli zapísať takto:

suma(n) = 1, pokud n == 1,
suma(n) = n + suma(n – 1), pokud n > 1.

O takýchto úlohách hovoríme, že majú rekurzívny charakter, tzn. že vo svojom riešení obsahujú čiastkové úlohy rovnakého typu, ako celá pôvodná úloha.

Rovnaký rekurzívny charakter by sme našli pri mnohých ďalších úlohách, napr. pri výpočte celočíselnej mocniny (x^n = x · x<sup>n-1</sup>) alebo faktoriálu (n! = n · (n-1)!).

Rekurzívne funkcie

Vráťme sa ale k funkcii na výpočet sumy. Vyjdeme z rekurzívneho vzorčeka, ktorý prepíšeme do podoby funkcie:

def suma(n):
    if n == 1:
        return 1
    else:
        return n + suma(n - 1)

int suma(int n)
{
    if (n == 1)
        return 1;
    else
        return n + suma(n - 1);
}

function suma($n)
{
    if ($n == 1)
        return 1;
    else
        return $n + suma($n - 1);
}

static int suma(int n)
{
    if (n == 1)
        return 1;
    else
        return n + suma(n - 1);
}

Práve sme napísali tzv. rekurzívnu funkciu.

V programátorskej terminológii je rekurzívna funkcia taká funkcia, ktorá niekde vo svojom tele volá seba samú.

Všimnime si dve dôležité veci:

funkcia má ukončovaciu podmienku, pri splnení ktorej sa ďalšie volanie už nevykoná (tu if n == 1),
pri rekurzívnom volaní sa mení argument funkcie – proces sa posúva na splnenie úlohy.

Ako prebiehajú rekurzívne volania

Pri rekurzívnom volaní sa deje to isté, čo pri akomkoľvek inom volaní funkcie. Dôjde k pozastaveniu prebiehajúceho vlákna, volajúca funkcia odovzdá riadenie volanej funkcii a čaká na návratovú hodnotu. Dôležité je ale pochopiť, že v prípade rekurzie sa toto deje opakovane av jednej chvíli máme rozpracovaných niekoľko funkcií, ktoré postupujú podľa rovnakej schémy. Časový priebeh pri volaní napr. suma(4) vyzerá takto:

Rekurzívne volanie - Rekurzívne algoritmy

Všimnime si dôležité veci: Funkcia, ktorá bola volaná ako prvá, končí ako posledná a naopak. Použili sme schému LIFO.

Schéme LIFO – L ast I n F irst O ut zodpovedá fungovaniu dátovej štruktúry zásobníka, ktorý funkcie pre svoj beh využívajú.

Ďalšie jednoduché rekurzívne funkcie

Uveďme si niekoľko ďalších príkladov jednoduchých rekurzívnych funkcií.

Klesajúca postupnosť čísel

Začneme funkciou, ktorá ako parameter dostane celé číslo n a na terminál vypíše klesajúcu postupnosť čísel od n do 1. Implementácia takejto rekurzívnej funkcie môže vyzerať napríklad takto:

def vypisKlesajici(n):
    if n == 0:
        return
    print(n)
    vypisKlesajici(n - 1)

void vypisKlesajici(int n)
{
    if (n == 0)
        return;
    Console.WriteLine(n);
    vypisKlesajici(n - 1);
}

function vypisKlesajici($n)
{
    if ($n == 0)
        return;
    echo("$n<br>");
    vypisKlesajici($n - 1);
}

static void vypisKlesajici(int n)
{
    if (n == 0)
        return;
    System.out.println(n);
    vypisKlesajici(n - 1);
}

Rastúca postupnosť čísel

Teraz si skúsme napísať podobnú funkciu, ktorá ale vypisuje rastúcu postupnosť čísel od 1 do n. Mohli by sme samozrejme začať od jednotky, vždy vypísať číslo a zavolať funkciu s parametrom o jedničku väčším. My ale môžeme urobiť inú úpravu: Prehodíme poradie výpisu čísla a volania funkcie:

def vypisRostouci(n):
    if n == 0:
        return
    vypisRostouci(n - 1)
    print(n)

void vypisRostouci(int n)
{
    if (n == 0)
        return;
    vypisRostouci(n - 1);
    Console.WriteLine(n);
}

function vypisRostouci($n)
{
    if ($n == 0)
        return;
    vypisRostouci($n - 1);
    echo("$n<br>");
}

static void vypisRostouci(int n)
{
    if (n == 0)
        return;
    vypisRostouci(n - 1);
    System.out.println(n);
}

Funkcia pre výpis rastúcej postupnosti teda najprv zavolá svojho rekurzívneho potomka, čaká na jeho návrat a až nakoniec vypisuje svoje číslo. Funkcia volaná ako prvá (vypisujúce číslo n) teda vykoná výpis úplne naposledy a naopak, teda opäť LIFO schému. Výsledkom je výpis rastúcej postupnosti, hoci sme začali volaním s parametrom n. Pokiaľ je nám fungovanie týchto dvoch funkcií jasné, sme k pochopeniu celej rekurzie veľmi blízko.

Najvyššie nepárne číslo

Posledným príkladom bude funkcia, ktorá prehľadá pole celých čísel a vráti najvyššie v ňom obsiahnuté nepárne číslo. Ak pole neobsahuje žiadne nepárne číslo, funkcia vráti nulu:

def najdiNejvyssiLiche(pole, index = 0, maxLiche = 0):
    if index == len(pole):
        return maxLiche
    if pole[index] % 2 == 1 and pole[index] > maxLiche:
        maxLiche = pole[index]
    return najdiNejvyssiLiche(pole, index + 1, maxLiche)

int najdiNejvyssiLiche(int[] pole, int index = 0, int maxLiche = 0)
{
    if (index == pole.Length)
        return maxLiche;
    if (pole[index] % 2 == 1 && pole[index] > maxLiche)
        maxLiche = pole[index];
    return najdiNejvyssiLiche(pole, index + 1, maxLiche);
}

function najdiNejvyssiLiche($pole, $index = 0, $maxLiche = 0)
{
    if ($index == count($pole))
        return $maxLiche;
    if ($pole[$index] % 2 == 1 && $pole[$index] > $maxLiche)
        $maxLiche = $pole[$index];
    return najdiNejvyssiLiche($pole, $index + 1, $maxLiche);
}

static int najdiNejvyssiLiche(int[] pole, int index, int maxLiche)
{
    if (index == pole.length)
        return maxLiche;
    if (pole[index] % 2 == 1 && pole[index] > maxLiche)
        maxLiche = pole[index];
    return najdiNejvyssiLiche(pole, index + 1, maxLiche);
}

Funkcia preberá tri parametre:

prehľadávané pole,
index aktuálne skúmaného prvku a
najvyššiu doteraz nájdenú hodnotu.

Pokiaľ je aktuálne skúmaný prvok väčší ako doterajšie maximum, je do ďalšieho volania dosadený na jeho miesto. Opäť nezabudnime na schému LIFO: Najvyššia hodnota sa nakoniec dostane k prvej volanej funkcii, ktorá ju tiež vráti.

Kedy rekurziu použiť

Doteraz sme rekurziu demonštrovali na jednoduchých úlohách. Ich účelom bolo ukázať princíp rekurzie. Avšak všetky tieto úlohy sa dajú ľahko vyriešiť pomocou cyklov. Rekurzívnymi funkciami môžeme nahradiť akýkoľvek cyklus, ale v skutočnosti to máloktorý programátor urobí. Dôvody sú tieto:

rekurzia zbytočne spotrebováva systémové prostriedky, pretože volanie funkcií vyžaduje vykonanie množstva operácií a alokáciu pamäte pre argumenty, čomu sa pri iterácii vyhneme,
program so zbytočnou rekurziou je menej zrozumiteľný, horšie sa spravuje a ťažšie sa v ňom hľadajú chyby.

Rekurziu nepoužívame pre úlohy, ktoré sa dajú ľahko vyriešiť jednoduchým cyklom.

Užitočnou pomôckou pri rozhodovaní je koľkokrát funkcia vo svojom tele volá seba samú. Pokiaľ iba raz, označujeme takú rekurziu za lineárnu a je veľmi pravdepodobné, že takáto funkcia pôjde nahradiť cyklom. Pokiaľ funkcia seba samú volá viac ako raz, označujeme ju ako stromovú av tom prípade nám rekurzia môže veľmi pomôcť.

V nasledujúcom článku, Stromová rekurzia - Generovanie všetkých možností , si ukážeme, ako sa rekurzia skutočne používa. Naučíme sa, ako vygenerovať všetky možnosti pri riešení nejakej úlohy.

Článok pre vás napísal Jan Hnilica

Užívateľské hodnotenie:

1 hlasov

Autor se věnuje hlavně programování v C a v Pythonu

Aktivity