Rekurze
Z Wikipedie, otevřené encyklopedie
Rekurze znamená sebeopakování. Používá se velmi často v matematice a programování.
Obsah |
[editovat] Příklad
Rekurzivní postup pro výpočet faktoriálu N! je:
Definice faktoriálu: N = 0 => N! = 1 N > 0 => N! = N * (N - 1)!
tedy pro N < 0 faktoriál není definován. Faktoriál je definovaný na celých kladných číslech a nule.
[editovat] Oblasti použití
- Rekurze se velmi často využívá při syntaktické analýze textů formálních jazyků (programovací jazyky, matematické vzorce), například pomocí regulárních výrazů.
- Velmi zajímavou oblastí použití rekurze jsou fraktály.
- Rekurzivně lze snadno popsat řadicí algoritmus quicksort.
[editovat] Nevhodné použití
Existují i případy, kdy použití rekurze není vhodné. Jako příklad může sloužit:
- Fibonacciho posloupnost – Rekurzivní algoritmus má exponenciální výpočetní složitost. Oproti tomu běžný algoritmus (počítající členy od začátku) má složitost lineární. Navíc existuje i algoritmus výpočtu jednoho prvku pracující prakticky v konstatním čase.
