Rekurzia (po latinsky: recurrere = bežať znovu) je v matematike a informatike, ale aj v biológii, využitie časti vlastnej vnútornej štruktúry, napríklad definovanie funkcie pomocou seba samej.

Formálna definícia V matematike a informatike sada objektov, funkcií, alebo metód, vykazuje známky rekurzie, ak spĺňa nasledujúce vlastnosti:

Obsahuje "základný prípad" - v ktorom je funkčná hodnota pevne daná, napr. číslom Obsahuje sadu pravidiel, ktoré zredukujú všetky ostatné funkčné hodnoty na "základný prípad"

Rekurzia v matematike

Rekurzívna definícia môže vyzerať napríklad takto:

Ak je konečná množina, tak existuje rekurzívny algoritmus na získanie všetkých podmnožín . Množina podmnožín sa označuje a je určená vzťahom

, kde a (teda T je doplnok k ).

Ďalšou známou postupnosťou využívajúcou rekurziu je Fibonacciho postupnosť.

Rekurzia v programovaní V informatike rekurzívna funkcia, volá samú seba. Musí obsahovať vetvu so základným prípadom pre časovú ohraničenosť funkcie.

Funkcia počítajúca faktoriál pomocou rekurzívneho algoritmu:function faktorial(n) if n == 1 return 1 else return n * faktorial(n - 1)

Iné projekty

Zdroje

Kategória:Programovanie