Rekurzivní funkce
Pojem rekurze znamená definování pojmu nebo procesu pomocí jeho samotného. Používá se především v matematice a informatice.
Rekurzi používáme v případě, když známe jenom rekurzivní algoritmus nebo když je zápis rekurzivního algoritmu podstatně jednodušší než u iterativního algoritmu.
Rekurzivní funkce jsou hodně náročné na paměť – pro každé volání funkce se ukládají v paměti parametry a lokální proměnné. Formulace problému musí být přesná.
Obecnou úlohu rozložíme na dílčí úlohy, které se řeší stejným způsobem. Rozklad zastaví omezující podmínka. Tato programovací technika se hodí pouze pro určitý omezený okruh úloh. Je-li použitelná, vede zpravidla k poměrně krátkému a efektivnímu programu.
Pravidla rekurze
- musí být definována podmínka pro ukončení rekurze
- v každém kroku rekurze musí dojít ke zjednodušení problému
- v případě, že nenastala koncová situace, provede se v algoritmu rekurzivní krok
Příklady rekurzivních funkcí
Výpočet xn pro n>0
Uvedeme matematický zápis i kód funkce pro iterativní a rekurzivní výpočet.
Iterativní definice: xn = x . x . …. . x , násobení se provede n-krát.
float mocnina(float x, int n)
{
float m=1;
int i;
for(i=1; i<=n; i++)
{
m = m * x;
}
return m;
}
Rekurzivní definice: x0 = 1, xn = x . xn-1
float mocnina(float x, int n)
{
if(n==0) return 1;
else return (x * mocnina(x, n-1));
}
V daném případě je vhodnější použít v praxi iterační algoritmus. Rekurzivní algoritmus uvádíme proto, že je jednoduchý a vhodný pro vysvětlení rekurze.
Algoritmy, ve kterých je použití rekurze nutné, jsou např. Hanojské věže, binární vyhledávací stromy, řazení metodou Quicksort.