OpenOffice.cz - web věnovaný kancelářským balíkům OpenOffice.org

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