Rekurze

Z Wikipedie, otevřené encyklopedie

Rekurze znamená sebeopakování. Používá se velmi často v matematice a programování.

Obsah 1 Příklad 2 Oblasti použití 2.1 Nevhodné použití 3 Podívejte se také na

[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 konstantním čase.

[editovat] Podívejte se také na

• Rekurzivní funkce