Rekurze

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

Matematika

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.

Programování

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

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

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

Odkazy

Externí odkazy

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

Související články

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

Autoritní data	GND: 4191814-9