Rekurzia
Rekurzia (po latinsky: recurrere = bežať naspäť) je matematike a informatike využitie časti vlastnej vnútornej štruktúry. V definícii funkcie sa nachádza volanie samotnej funkcie. Inak povedané, funkcia volá samú seba.
Obsah
Rekuzia - definície, princípy
Rekurzia v grafike
Najjednoduchsim prikladom rekuzie, ktorý sa dá zobraziť je dať 2 zrkadlá oproti sebe. Ďalším príkladom môže byť spustenie programu vzdialená pracovná plocha, kde adresa vzdialeného počítača bude ten počítač, na ktorom bola aplikácia spustená. Rekurzia sa občas objaví i na obaloch potravín (pozri obrázok).
Rekurzívny obraz v zrkadlách
Rekurzívny obraz ´vzdialenej´ pracovnej plochy
Rekurzívny obal kakaa
Rekurzia v matematike
Rekurzia v informatike
Princíp fungovania rekurzívnych funkcií:
- Zložitý problém môžeme riešiť rekurzívnym spôsobom tak, že:
- Daný problém rozložíme na elementárne podproblémy, ktoré dokážeme jednoducho vyriešiiť.
- Tieto podproblémy musia byť rovnakého typu.
- Riešenie spočíva v opakovanom (rep. rekurzívnom) vykonávaní funkcie riešiacej daný problém.
- Dôležitou bodom je určiť podmienku, kedy sa ukončí riešenie úlohy.
Príklad: Vypíšte za sebou čísla od n do 0. Nech n=5
- Zložitý´ problém
- vypísať dané čísla: (Dajme tomu, že nepoznám cykly)
- Rozloženie problému na elementárne podproblémy
- vypíšem len jedno číslo (to viem)
- Podmienka ukončenia výpisu
- Prestanem keď vypíšem posledné číslo - 0
- Doterajšie riešenie
- Funkcia, ktorý vypíše len jedno číslo (n)
void vypis(int n) { cout<<n; }
- Doplnenie rekurzie;Vo funkcii vypis pridam volanie funkcie vypis, ktorá má parameter n o 1 menší
void vypis(int n) { cout<<n; vypis(--n); }
- Analýza riešenia;Vyrobili sme deadlock, čiže uviaznutie programu. Funckia vypis sa nikdy neukonci, bude sa volať do nekonečna (resp. dotiaľ, dokiaľ bude mať program dostatok pamäti. Potom spadne).
- Doplnenie ukončujúcej podmienky
- Vypisovanie ukončím pri výpise 1.
void vypis(int n) {
cout<<n;
if(n>0)
vypis(--n);
}
Na začiatok uvedieme niekoľko prípadov rekurzívnej definície funkcie:
