Rekurzia

Úvod

Aby sme ľahšie zistili, ako sa menia hodnoty premenných, pripravíme si funkciu Vypis(int n). Tá, pri každom zavolaní, vypíše do komponentu Memo hodnotu premennej n. Komponent Memo funguje ako jednoduchý informatika/textovy-editor/" class="wiki-link" title="Viac o: textový editor">textový editor, nachádza sa na záložke Standard a umožňuje pracovať s textom aj pomocou svojich vlastností a metód:

void Vypis(int n) { Form1->Memo1->Lines->Add(n); }

Príkaz Form1->Memo1->Lines->Add(text) pridá nový riadok s textom (v našom prípade sa hodnota premennej n konvertuje na text).

Rekurzívne volanie

Máme funkciu:

void F() { F(); // volanie funkcie }

Príkaz z tela funkcie spôsobí opätovné volanie funkcie F - rekurzívne volanie funkcie (rekurzia):

• rekurziu poznáme aj v matematike - rekurzívne definované funkcie: n-faktoriál, fibonanciho čísla a iné
• používa sa pri riešení úloh, ktoré možno rozdeliť na menšie pod-úlohy, pričom sa na ich riešenie sa používa rovnaký algoritmus, ako pre celú úlohu.

Rekurzívne volanie sa môže, na prvý pohľad, zdať veľmi komplikované, ale ak sa správne používa, nemusí tomu tak byť. Preto sa na nasledujúcich príkladoch postupne naučíme správne používať rôzne typy rekurzie.

Nekonečná rekurzia

void Test(int n) { Vypis(n); Test(n+1); }

void __fastcall TForm1::Button1Click(TObject *Sender) { Test(1); }

Funkcia Test rekurzívne volá samú seba - donekonečna sa vykonávajú príkazy:

Vypis(n); Test(n+1);

Mali by sa vypisovať čísla 1, 2, 3... až do nekonečna. V skutočnosti sa funkcia nevolá donekonečna, pretože po určitom čase volanie skončí s chybou stack overflow - pretečenie zásobníka. Zásobník je časť pamäte, do ktorej sa ukladajú:

• informácie o tom, kde má program po skončení funkcie pokračovať (tzv. návratová adresa)
• hodnoty parametrov a lokálnych premenných všetkých volaných funkcií

Zásobník má obmedzenú veľkosť a po určitom počte volaní sa zaplní. Preto program skončí a vyhlási chybu.

Predchádzajúcu funkciu vieme triviálne prepísať tak, aby nenastávalo rekurzívne volanie: void Test(int n) { while (true) { Vypis(n); n++; } }

Chvostová rekurzia

Rekurzívne volanie môžeme kontrolovať a vo vhodnom okamihu zastaviť: void Test(int n) { if (n>3) return; // nerekurzívna vetva Vypis(n); Test(n+1); }

Krokujme, čo sa deje pri zavolaní Test(1):

• vidíme, že pokým je n=100) { // ukončenie volania - nerekurzívna vetva

k.ZmenFarbu(clRed); return; } k.dp(d); k.vp(90); Kresli(d+10); // rekurzívne volanie k.vp(90); k.dp(d); }

Pre Kresli(10) - obrázok sa začne kresliť v strede čierne špirály a skončí v strede červenej špirály.

Príklad z matematiky - funkcia n-faktoriál je definovaná nasledovne: n=1 Þ n!=1 n>1 Þ n!=n*(n-1)!

Naprogramujeme n! v jazyku C++:

int Fakt(int n) { if (n