Rekurzia
Rekurziu chápeme vtedy, ak nejaká funkcia alebo metóda(termín z OOP, zatiaľ pre vás nepodstatné) volá samu seba. Inak povedané, v tele funkcie sa nachádza prepis volania tej samej funkcie. Rekurzia tak môže ušetriť pár riadkov kódu, spriehľadniť kód a zefektívniť algoritmus.
Fungovanie rekurzie je najlepšie ukázať na príklade výpočtu faktoriálu čísla. Na porovnanie si ukážeme najprv tradičný iteratívny spôsob výpočtu. Iterácia znamená viacnásobne opakovanie toho istého bloku kódu. Napríklad pomocou cyklu sa vytvárajú iterácie. Iteráciu i rekurziu napíšeme vo funkcii, ktorá bude volaná z hlavnej procedúry.
Ešte predtým, než sa na to vrhneme, by som mal ozrejmiť, čo je to ten faktoriál? Faktoriál čísla n je rovný súčinu všetkých prirodzených čísel, ktoré sú rovné alebo menšie ako n. Áno, súhlasím že je to strašne krkolomná definícia. Lepšie nám to ozrejmí ukážka. Pre tých, ktorí nevedia, ako sa označuje faktoriál, tak symbolom !.
0! = 1
1! = 1
2! = 2 * 1 = 2
3! = 3 * 2 * 1 = 6
4! = 4 * 3 * 2 * 1 = 24
5! = 5 * 4 * 3 * 2 * 1 = 120
6! = 6 * 5 * 4 * 3 * 2 * 1 = 720
atď...
1. príklad: Výpočet faktoriálu cez iteratívny spôsob
Sub Factorial MsgBox IterativnyFactorial(6) End Sub Function IterativnyFactorial(ByVal i As Long) As Long Dim zaklad As Long zaklad = 1 Do While i > 1 zaklad = zaklad * i i = i – 1 Loop IterativnyFactorial = zaklad End Function
Výsledok činností makra
Rozbor makra: Vo funkcii IterativnyFactorial vypočítame hodnotu faktoriálu čísla, ktorú sme predali ako argument funkcie. Vytvoríme si premennú základ ktorú inicializujeme na hodnotu 1. Táto premenná bude úložisko, tak aby počas iterácie sa nám výsledok nestratil. V cykle už realizujeme iteratívny spôsob výpočtu faktoriálu. Argument funkcie sa bude znižovať dovtedy, pokým jeho hodnota je väčšia ako 1. Takto získame faktoriál čísla a následne funkcia vráti do primárnej procedúry hodnotu. Vidíme, že iterácia nie je nič iné, len opakovanie nejakej častí kódu.
2. príklad: Výpočet faktoriálu cez rekurziu
Sub Factorial MsgBox RekurziaFactorial(6) End Sub Function RekurziaFactorial(ByVal i As Long) As Long If i = 1 Then RekurziaFactorial = 1 Else RekurziaFactorial = RekurziaFactorial(i - 1) * i End If End Function
Výsledná činnosť programu
Rozbor makra: Tento príklad si rozoberieme podrobne, pretože ide o netriviálnu zaležitosť na pochopenie. Začíname tak ako v minulom príklade, hlavnou procedúrou. Procedúra volá funkciu RekurziaFactorial a predáme funkcii jeden parameter typu Long. Aj samotná funkcia je rovnako typu Long.
Začne beh funkcii. Ak hodnota premennej i sa rovná 1, tak funkcia vráti hodnotu 1 a makro skončilo. A tu sa zastavím, pretože táto podmienka, že ak i sa rovná 1, bude základom rekurzie. Vysvetlím hneď. Teraz ďalej pokračujeme. Funkcia volá samu seba a ešte má byť vynásobená premennou i. Čo sa práve stane? Ukážeme si presne na ukážke správania sa programu.
1. krok: RekurziaFactorial = RekurziaFactorial(5) * 6
Zavolá sa RekurziaFactorial(5) a začne vykonávanie funkcie s novým parametrom typu Long
2. krok: RekurziaFactorial = RekurziaFactorial(4) * 5
Zavolá sa RekurziaFactorial(4) a začne vykonávanie funkcie s novým parametrom typu Long
3. krok: RekurziaFactorial = RekurziaFactorial(3) * 4
Zavolá sa RekurziaFactorial(3) a začne vykonávanie funkcie s novým parametrom typu Long
4. krok: RekurziaFactorial = RekurziaFactorial(2) * 3
Zavolá sa RekurziaFactorial(2) a začne vykonávanie funkcie s novým parametrom typu Long
5. krok: RekurziaFactorial = RekurziaFactorial(1) * 2
Zavolá sa RekurziaFactorial(1) a začne vykonávanie funkcie s novým parametrom typu Long
A tú skončí rekurzia. Premenná i má hodnotu 1. Ak by sme nedali podmienku i=1, tak by rekurzia nikdy neskončila. A ideme teraz spätne k výsledku. Hodnotu 1 získa posledne volaná funkcia. Dopracovanie sa k výsledku je nasledovné:
2 = 1 * 2 REM náš piaty krok 6 = 2 * 3 REM náš štvrtý krok 24 = 6 * 4 REM náš tretí krok 120 = 24 * 5 REM náš druhý krok 720 = 120 * 6 REM náš prvý krok Výsledok = 720