Rekurze

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

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

V matematice se rekurze chápe 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 se z aktuálního stavu odvodí 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.

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.

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.).^[2]

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: je vidět, ž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“).

• Obrázky, zvuky či videa k tématu rekurze na Wikimedia Commons

• Autoreference
• Peanova aritmetika
• Matematická indukce
• Fraktál