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

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

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

  1. rekurze, rekurse - ABZ.cz: slovník cizích slov. slovnik-cizich-slov.abz.cz [online]. [cit. 2022-04-09]. Dostupné online. 
  2. REKURZIVITA | Nový encyklopedický slovník češtiny. www.czechency.org [online]. [cit. 2022-04-09]. Dostupné online. 

Externí odkazy

Související články

Média použitá na této stránce