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