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í. +more 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í

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. +more Chyba v rekurzi může způsobit vyčerpání paměti pro zásobník a následně ukončení programu.

Lingvistika

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 . +more“ 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

Reference

Externí odkazy

Související články

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