Rekurzivní funkce

Rekurzivní funkce

Funkce, která ve svém těle volá sama sebe (jeden nebo více příkazů těla této funkce obsahuje volání této funkce), se nazývá rekurzivní.

Princip rekurze spočívá ve “zjednodušování” daného problému při postupném volání funkce. V rekurzivních funkcích vždy existuje mezní podmínka (vyjadřující řešení elementárního problému, např. faktoriál čísla 0, třídění jednoprvkové posloupnosti), při jejímž splnění dojde k přerušení rekurze. Příklady rekurzivních funkcí

  • výpočet faktoriálu,
  • výpočet fibonacciho čísla,
  • quicksort,
  • metoda půlení intervalu, …
  • h0nza: hmm, jakýkoli cyklus lze jako rekurzi?

Pro a proti:

  • elegance
  • režie zásobníku!!! nemáme ocasní rekurzi (tailcall)
  • nemáme lambda, letrec, y-kombinator …
jazykc/rekurzivni-funkce.txt · Last modified: 2015/01/15 20:48 (external edit)
CC Attribution-Share Alike 3.0 Unported
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0