XIX. Diel C++ - Rekurzia a rekurzívne funkcie

Michal Kyžňanský  /  03. 02. 2006, 00:00

Dnes si povieme o rekurzii a rekurzívnych funkciách. Je to veľmi dôležitá časť programovania v C++ jazyku, pretože patrí už k prepracovaným častiam tohto jazyka, bez ktorých sa nedá zaobísť v rôznych projektoch. Poďme si vysvetliť o čo ide.

Rekurzia od nej odvodené pomenovanie rekurzívna funkcia – pomenúva funkcie v programovacom jazyku, ktoré odkazujú sami na seba, to znamená, že obsahujú vo svojom tele príkaz na volanie samej seba. Volanie prebieha stále donekonečna, preto sa používa pre implementovanie rekurzie napríklad podmienka if, ktorá ak prestane platiť tak sa preskočí na kód, ktorý obsahuje príkaz na zavolanie samej seba. Rekurzia sa využíva ako náhrada cyklu, pretože jej použitie je niekedy omnoho praktickejšie a výhodnejšie ako cyklu. Konštrukcia rekurzívnej funkcie nevyžaduje nejaké nové sady príkazov, je to len jednoduché volanie funkcie. Pre jasnú demonštráciu si ukážeme jej použitie v zhodných programoch, ale jeden bude využívať rekurziu a druhý cykly.


Program na počítanie faktoriálu a spočítanie radu čísel od jednotky po n.

1. spôsob – faktoriál cez cyklus

void __fastcall TForm1::Button5Click(TObject *Sender) 
{

int a,b = 1;

a = Edit1->Text.ToInt();

for(a;a > 0; a--){
b = b * a;
}
Memo1->Lines->Add(b);
}


2. spôsob – faktoriál cez rekurzívnu funkciu

//udalosť stlačenie tlačidla zavolá funkciu a vypíše jej výsledok 

void __fastcall TForm1::Button2Click(TObject *Sender)
{
int c;
c = Edit1->Text.ToInt();

Memo1->Lines->Add(faktorial(c));
//volanie funkcie
}
//---------------------------------------------------------------

//telo funkcie
int TForm1::faktorial(int i) //deklarovanie rekurzívnej funkcie
{

if(i >= 1){
return i * faktorial(i - 1);
}
else{
return 1;
}
}


Zameriame sa na zápis return i * faktorial(i - 1);, ktorý predstavuje prvok – rekurziu, pretože obsahuje volanie funkcie - príkaz na zavolanie tej istej funkcie v jej tele. Dôležité je, že v momente keď sa program dostane k tomuto príkazu pokračuje vykonávanie funkcie faktorial(i-1) bez vykonania príkazov nasledujúcich po príkaze volania funkcie. Až keď sa stane podmienka, vďaka ktorej sa funkcia volá stále dokola neplatná, až potom sa začnú vykonávať príkazy zapísané pod príkazom na jej volanie a to v opačnom poradí. Príklad, aby sme jasne videli, že sa príkazy vykonávajú v opačnom poradí po skončení volania funkcie by sa skladal z jednoduchej rekurzívnej funkcie a po nej by nasledovalo vypisovanie čísel od 1 po 5. Ale výpis by paradoxne vyzeral 5..4..3..2..1. To len potvrdzuje tvrdenie o tom, že príkazy sa vykonajú v opačnom poradí.

Náš výpis sme postavili na tom, že funkcia faktorial je typu int – čiže po skončení vracia hodnotu a tá sa vypíše do komponenty Memo. Pri tomto programe použijeme dve komponenty Button jednu komponentu Edit a jednu komponentu Memo.

Druhý program, na ktorom si demonštrujeme rekurziu bude obdobný, len bude čísla spočítavať a nie násobiť od čísla n až po 1.

1. spôsob – pomocou cyklu


void __fastcall TForm1::Button1Click(TObject *Sender) { 
int c,p = 0;

c = Edit1->Text.ToInt();

for(c; c > 0; c--){
p = p + c;
}
Memo1->Lines->Add(p);
}


2. spôsob – pomocou rekurzie


//udalosť, ktorá spúšťa funkciu a vypisuje jej výsledok 

void __fastcall TForm1::Button2Click(TObject *Sender)
{
int c;
c = Edit1->Text.ToInt();

Memo1->Lines->Add(spocitanie(c));
}

//telo funkcie
int TForm1::spocitanie(int a)
{

if(a >= 1){
return a + spocitanie(a - 1);
}
else{
return 0;
}
}


Rekurzia môže byť aj zložitejšia, že v tele funkcie sa bude tá istá funkcia volať aj niekoľkokrát. Dôležité je si predstaviť ako program bude pracovať a postupne prejsť kroky, pretože rekurzia vytvára spletitý sled udalostí náročných na predstavivosť. Ďalším typom rekurzie je nekonečná rekurzia, ktorá by sa mala teoreticky vykonávať donekonečna. Ale pri vypisovaní napríklad čísel od jedna po nekonečno, sa volanie zastaví, pretože príde k chybe – pretečeniu zásobníkastack overflow. Zásobník ma obmedzenú kapacitu.


Nabudúce začneme rozsiahlu kapitolu – triedy.

Súvisiace články:

Prehľad všetkých dielov

Neprehliadnite: