Rekurzia (matematika)

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 ${\displaystyle S}$ je konečná množina, tak existuje rekurzívny algoritmus na získanie všetkých podmnožín ${\displaystyle S}$. Množina podmnožín sa označuje ${\displaystyle P(S)}$a je určená vzťahom

${\displaystyle {\mathcal {F}}(e,T)=\{X\cup \{e\}|X\in T\}}$, kde ${\displaystyle e\in S}$a ${\displaystyle T=S\setminus \{e\}}$(teda T je doplnok ${\displaystyle e}$ k ${\displaystyle S}$).

Ď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)

Zdroje

Tento článok je čiastočný alebo úplný preklad článkov Power set na anglickej Wikipédii a Recursion na anglickej Wikipédii.