Metody

Objekt je rekurzivní, jestliže se skládá nebo je definován pomocí sebe samého. Co nám tato poučka říká, není nic jiného než, že v rámci těla metody deklarované metody, bude tato metoda znovu volána. Je provedeno tzv. rekurzivní volání metody. Jde o princip vnořování metody dovnitř sebe samé.

Podstatu rekurze zachycuje následující obrázek, který ilustruje obraz v obraze (metoda volá sama sebe, ta zase volá sama sebe atd.) – viz Obrázek 1.

Obrázek 1: Podobenství rekurze

Rekurzivní volání nastane dříve, než je předchozí vyvolání dokončeno. Rekurze může být přímá (metoda volá sama sebe) nebo vzájemná (2 nebo více metod se volá navzájem).

Metoda ale s vnořováním do sebe také musí někdy přestat, tzn., že pokud má mít výpočet smysl, musí být rekurzivní volání prováděno v konečném počtu kroků. Znamená to, že uvnitř metody s rekurzí musí být definována podmínka, že další rekurzivní volání skončí a dojde také k návratu ze všech rozpracovaných volání metody.

Ilustrativní příklad FaktorialRekurze 

Program FaktorialRekurze 

• Popis: Příklad deklarace metody s využitím rekurze pro výpočet faktoriálu
• Zadání: Zkuste deklarovat metodu s celočíselným návratem nazvanou FaktorialRekurze, která přijímá celočíselný parametr pojmenovaný n. Pomocí rekurze vypočtěte hodnotu faktoriálu pro tento parametr. Hodnotu výstupu této metody vypište v metodě Main
• Řešení: Bude postupně probráno v následujícím textu

Procvičme si podstatu rekurze na typickém příkladu výpočtu faktoriálu. Z matematiky víme, že faktoriál čísla n (značeno jako n!) je roven součinu všech přirozených čísel menších nebo rovných n (přičemž platí 0! = 1) např. 3! = 3*2*1. Pomocí rekurze bychom mohli faktoriál kladného čísla rozepsat jako 3! = 3*2!, kde bychom 2! uvnitř výrazu mohli zase rozepsat 2! = 2*1! a další rozepsání již není zapotřebí, protože 1! je roven 1. Postupným zpětným dosazením nám tedy vznikl výraz 3! = 3*2*1!, tedy  3! = 3*2*1 = 6. Výpočet faktoriálu rekurzivním způsobem, lze zapsat jako n*(n-1)! . Pokud bychom použili metodu pro výpočet faktoriálu, nazvěme ji např. FaktorialRekurze, můžeme náš předchozí zápis výpočtu faktoriálu rekurzivním způsobem zapsat jako n*FaktorialRekurze(n-1). Tohoto principu využijeme v následujícím příkladu – viz Kód 1. 

/*Deklarace statické metody s využitím rekurze s jedním celočíselným výstupem 
 * a s jedním vstupním parametrem*/
static int FaktorialRekurze(int n)
{
    //Podmínka ukončení dalšího rekurzivního volání metody
    if (n == 1)
        //Faktorial 1 je roven 1
        return 1;
    //Nedosáhli jsme podmínky ukončení další rekurze (vnoření)
    else
        return (n * FaktorialRekurze(n - 1));
}

Kód 1: Příklad deklarace metody FaktorialRekurze s využitím rekurze pro výpočet faktoriálu

V těle této metody (funkce) je definována podmínka, která určuje, kdy se vnořování metody do sebe samé musí zastavit, tzn., že krok, kdy se metoda postupným snižováním parametru na základě výrazu (n – 1), dostane až do stavu, kdy je předávaná hodnota parametru rovna 1 (tehdy je 1! = 1). Rekurzi vidíme ve čtvrtém řádku kódu (bez komentářů), kdy metoda volá sama sebe (svým jménem FaktorialRekurze) a předává si postupně snižovanou hodnotu parametru o jedna. Až se volaná metoda dostane do stavu, že daný parametr už nejde snížit (splnění podmínky ukončení další rekurze v těle metody), hodnotu 1 předá zpět do metody, která ji naposledy volala. Pak tato volající metoda vypočte hodnotu svého výrazu a tuto hodnotu zase postupně dosazuje zpět do volající metody. Tento cyklus probíhá tak dlouho, dokud neobdržíme výsledek příkazu, který odstartoval volání vnořených metod.

Použití rekurze je velmi účinný ale často také nebezpečný trik!

Následující kód popisuje, jak bychom vytvořenou metodu používající rekurzi pro výpočet faktoriálu volali v metodě Main – viz Kód 2. Této metodě je do parametru předána hodnota 7 uložená v proměnné cislo, která byla inicializována přímo v deklaraci. Poslední řádek kódu ukazuje vypočtenou hodnotu faktoriálu a číslo, pro něhož byl faktoriál vypočten.

static void Main(string[] args)
{
    //Deklarace parametru
    int cislo = 7;
    //Zavolání metody s rekurzí s 1 vstupním parametrem a jedním celočíselným výstupem
    int faktorial = FaktorialRekurze(cislo);
    //Výpis čísla, ze kterého byl vypočten faktoriál a hodnota faktoriálu
    Console.WriteLine("Faktoriál čísla {0}: {1}", cislo, faktorial);
    //Čekání na stisk klávesy -> ukončení programu
    Console.ReadKey();
}

Kód 2: Příklad zavolání metody FaktorialRekurze využívající rekurzi pro výpočet faktoriálu včetně výpisu výsledku

Na následujícím výpisu v konzoli vidíme vypočtený faktoriál – viz Výstup programu - Kód 2.

Faktoriál čísla 7: 5040

Výstup programu - Kód 2: Ukázka výsledku použití rekurze

Co kdybychom zkusili zadat nějaké větší číslo jako vstup, např. 13. Pokud si vypočteme hodnotu faktoriálu pro toto číslo, zjistíme, že faktoriál by měl odpovídat číslu 6,227,020,800 (čárky oddělují řády tisíců). Ale co se stalo? Nám program vypsal jinou hodnotu. Jak již bylo řečeno, každý datový typ má svou horní mez a při výpočtu faktoriálu jsme bohužel horní mez datového typu int překročili (tato horní mez je 2,147,483,647). Jedná se o tzv. přetečení (o přetečení se více dozvíme později). Při volbě datového typu musíme tedy pečlivě zvážit, zda se nám do jeho rozsahu vypočtené hodnoty vejdou. Asi si říkáte, tak použiji jiný datový typ s větším rozsahem. Uvědomte si, že čím větší je rozsah hodnot, tím více zabírá paměti a tím více se obíráte o výpočetní výkon počítače.