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í

[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