Rekurzia (matematika)

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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[upraviť | upraviť zdroj]

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[upraviť | upraviť zdroj]

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í[upraviť | upraviť zdroj]

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)

Tento článok je čiastočný alebo úplný preklad článku Power set na anglickej Wikipédii (číslo revízie nebolo určené).

Tento článok je čiastočný alebo úplný preklad článku Recursion na anglickej Wikipédii (číslo revízie nebolo určené).