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ý 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<=3, funkcia volá samú seba
* ak n dosiahne hodnotu 4, vykoná sa príkaz return, čo spôsobí návrat z posledného volania funkcie:
o program pokračuje od miesta posledného volania funkcie - za príkazom Test(n+1)
o za týmto príkazom už nie je žiaden príkaz iný príkaz, preto sa aj toto volanie funkcie skončí - podobne sa ukončia aj zostávajúce volania funkcie.
1
2
3
Tento typ rekurzívneho volania sa nazýva chvostová rekurzia (rekurzívne volanie funkcie spôsobuje iba posledný príkaz funkcie). Chvostovú rekurziu vieme jednoducho prepísať pomocou cyklu while:
while (n<=3) {
Vypis(n);
n++;
}
Jednoduchá rekurzia
Vo funkcii Test doplníme za príkaz rekurzívneho volania (už to nebude chvôstová rekurzia) výpis parametra n - zistíme, akú má hodnotu po skončení rekurzívneho volania:
void Test(int n) {
if (n>3) return;
Vypis(n);
Test(n+1);
Vypis(n);
}
1
2
3
3
2
1
Jednoduchú rekurziu vieme prepísať pomocou dvoch cyklov:
while (n<=3) { // rekurzívne "vnáranie" sa
Vypis(n);
n++;
}
while (n>1) { // "vynáranie" sa z rekuzie
n--;
Vypis(n);
}
}
Iná ukážka jednoduchého rekurzívneho volania - využijeme korytnačku:
void Kresli(float d) {
if (d>=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<=1) return 1;
return n*Fakt(n-1);
}
Ako vyzerá priebeh volaní pre Fakt(3):
* začne sa vyhodnocovať výraz 3*Fakt(2) ... Fakt(2) je volanie funkcie:
o vyhodnocuje sa výraz 2*Fakt(1) ... Fakt(1) je volanie funkcie:
+ pre Fakt(1) sa vykoná príkaz return 1, ktorý vráti hodnotu 1;
o pokračuje sa vo vyhodnotení výrazu ... 2*1 a príkaz return vráti hodnotu 2;
* pokračuje sa vo vyhodnocovaní výrazu ... 3*2 a príkaz return vráti hodnotu 6
Výsledkom funkcie je číslo 6.
Pravá (naozajstná) rekurzia
Predchádzajúce funkcie obsahovali vo svojom tele najviac 1 rekurzívne volanie. Rekurzívne volania môžu byť aj komplikovanejšie - telo funkcie obsahuje 2 alebo viac rekurzívnych volaní.
Funkcia Rozdel rozdelí intervaly <L, P> na dva intervaly - dve polovice:
<L, (L+P)/2>
<(L+P)/2, P>
Funkcia ďalej pokračuje v delení týchto dvoch intervalov. Nerekurzívna vetva nastane pre interval kratší ako 1. Vtedy sa nakreslíme jeden bod:
void Rozdel(float L, float P) {
if (P-L<=1) {
g->Pixels[(L+P)/2][100]=clBlack;
return;
}
Rozdel(L, (L+P)/2);
Rozdel((L+P)/2, P);
}
Funkcia nakreslí vodorovnú čiaru.
Funkciu upravíme tak, aby sa interval delil na tretiny. Ďalej však budeme rekurzívne rozdeľovať iba krajné intervaly (prostredný interval ostane prázdny):
void Rozdel(float L, float P) {
if (P-L<=1) {
g->Pixels[(L+P)/2][100]=clBlack;
return;
}
Rozdel(L, L+1*(P-L)/3);
Rozdel(L+2*(P-L)/3, P);
}
Takto sa vykreslia iba niektoré body - tie znázorňujú cantorovú množinu. Obrazec, ktorý uvidíme je fraktál.
Fraktály
Fraktál ("rozkúskovaný", z latinského fractus) je obrázok alebo útvar, ktorý sa skladá z častí, ktoré sa podobajú samotnému obrázku. Pomerne jednoducho môžeme aj veľmi zaujímavé fraktály kresliť iba pomocou korytnačky.
Binárny strom:
stupeň