Rekurze

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání
Tento článek pojednává o základním významu rekurze. Možná hledáte: rekurzi v programování.
Rekurzivně definovaný Sierpińského trojúhelník.

Rekurze je stav, kdy je určitý objekt v nějakém smyslu součástí sebe samotného. S rekurzí se můžeme setkat v různých oborech, ale nejčastěji je používána v matematice a informatice.

Příklady rekurze:

  • Definice pojmu používá tento pojem samotný.
  • Datová struktura obsahuje odkaz na strukturu stejného typu.
  • Obraz obsahuje zmenšenou kopii sama sebe.

Termín je pravděpodobně odvozen z latinského slovesa recurrō (vrátit se).

Matematika[editovat | editovat zdroj]

V matematice rekurzi chápeme jako definování objektu pomocí sebe sama. Využívá se například pro definici přirozených čísel a některých funkcí. Definice tohoto typu mají zpravidla dvě základní části: počáteční tvrzení a způsob, jak z aktuálního stavu odvodíme stav následující.

Příkladem rekurzivní definice může být definice přirozených čísel:

  • 0 je přirozené číslo.
  • Pokud n je přirozené číslo, pak n + 1 je přirozené číslo.
  • Soubor přirozených čísel je nejmenší soubor splňující předchozí dvě vlastnosti.

Programování[editovat | editovat zdroj]

Podrobnější informace naleznete v článku Rekurze (programování).

V programování rekurze představuje opakované vnořené volání stejného podprogramu (funkce). Součástí rekurzivní funkce by měla být ukončující podmínka určující, kdy se má vnořování zastavit. Chyba v rekurzi může způsobit vyčerpání paměti pro zásobník a následně ukončení programu.

Lingvistika[editovat | editovat zdroj]

Podrobnější informace naleznete v článku Generativní gramatika.

Podle Noama Chomského a dalších lingvistů mají všechny známé lidské jazyky rekurzivní strukturu. Projevuje se to tím, že lze vytvářet potenciálně nekonečnou strukturu vedlejších vět (pomocí konstrukcí jako „viděl, že ...“ nebo „tvrdil, že ...“ apod.).

Humor založený na rekurzi[editovat | editovat zdroj]

Některé definice rekurze v sobě zahrnují prvky humoru a parodie na výkladové slovníky:

Cyklus nekonečný
viz Nekonečný cyklus
Nekonečný cyklus
viz Cyklus nekonečný

Tento žertík v sobě nese i poučení o nesprávném užívání rekurze: vidíme, že zde chybí ukončující podmínka.

Podobnými hříčkami jsou rekurzivní zkratky. Například zkratka GNU v angličtině znamená „GNU's Not Unix“ (česky „GNU Není Unix“).

Související články[editovat | editovat zdroj]