Vysvětlení pojmů rekurze z článku PHP rekurze - jak...
Tak protože mnoho z vás se s pojmem rekurze ještě nesetkala,tak si v tomto článku rozebereme co to rekurze je,jak funguje a jak ji implementovat.
S rekurzí se můžeme celkem snadno potkat i v běžném životě,jako nejjednodušší příklad je pohled kamery na obraz toho co zobrazuje.
Dalším příkladem je Kochova vločka (křivka):
Tak teď si povíme trochu teorie.Rekurzivní (rekurentní) metoda je metoda,která volá buď přímo nebo nepřímo sebe sama.Jedním z typických příkladů je funkce faktoriál: 1!=1,n!=n*(n-1)!,0!=1 (! - je značka pro faktoriál,vyzkoušejte si na vědecké kalkulačce 1!, 2!, 4!) Rozebereme si například 5!:
5!=5*(5-1)!
5*4!=5*4*(4-1)!
5*4*3!=5*4*3*(3-1)!
5*4*3*2!=5*4*3*2*(2-1)!
5*4*3*2*1!=5*4*3*2*1*(1-1)!
5*4*3*2*1*0!=5*4*3*2*1*1
nebo se to dá napsat také takto:
5!=5*(5-1)*(5-2)*(5-3)*(5-4)*(5-5)!Pokud bychom uvažovali,že již máme vytvořenu funkci pro výpočet faktoriálu tak by to vypadalo následovně:
- f(n)=1 pro n=1- f(n)=n*f(n-1) pro n>1.
Rekurzní metoda(funkce) se pak rozkládá na menší podmetody.V každé rekurzní metodě musí existovat "základní stav" ,který vrátí nějakou hodnotu bez rekurzního volání.V našem případě by to byla hodnota 0! = 1(resp. 1! = 1,výsledek je stejný ale pro 1! ušetříme jednu rekurzi). Takže následné(zpětné) skládání podmetod nám pak vyřeší naši metodu.Zpětně - protože nejprve se v našem příkladu dojde k poslední rekurzi a teprve s návratem její hodnoty se budou dopočítávat výsledky jednotlivých rekurzí a jako poslední se spočítá 5*f(5-1).
Jak jsme se již zmínili tak každá rekurze musí skončit,to znamená,že každá rekurzní funkce musí mít v sobě podmínku,které výpočet dosáhne a po jejím vyhodnocení skončí (v našem příkladu je to 0!=1,je li n = 0 funkce již nebude volat sama sebe,ale vrátí hodnotu 1).
V našem případě jsme použili tzv. přímou rekurzi.Cože znamená že metoda M se odkazuje sama na sebe(volá samu sebe). Pak je tu ještě druhý typ tzv. Nepřímá rekurze - metoda M1 se odkazuje na metodu M2,která se odkazuje na metodu M1 (přímo nebo nepřímo).
Rekurze vs. Iterace
- Rekurze často poskytuje elegantnější a jednodušší řešení problému než iterace.
- Rekurzivní řešení je obvykle méně efektivní než iterační (vzhledem k paměťovým a časovým nárokům).
- Rekurze je mocným nástrojem pro řešení problémů, které jsou rekurzivně definovány.
- Rekurze může být ekonomickým řešením problému, pokud není hloubka rekurzivního volání příliš velká.
Konkrétní příklad funkce pro výpočet faktoriálu:
skript je v pseudojazyce)
int fakt(int n) {
if (n == 0) return 1;
else return (n * fakt(n-1));
}
následná implementace do jakéhokoliv jazyka by neměla činit potíže.
Autor: fingarfae
2024 ©