Vizuální forma rekurze známá jako Drostův efekt.
Rekurze je v matematice a informatice metoda definování funkcí, ve které je definovaná funkce aplikována v rámci vlastní definice. Termín se také používá obecněji k popisu procesu opakování objektů podobným způsobem. Například když jsou plochy dvou zrcadel téměř rovnoběžné, nastoupené obrázky, které se vyskytují, jsou formou rekurze.
Formální definice rekurze
V matematice a informatice rekurze určuje (nebo konstruuje) třídu objektů nebo metod (nebo objekt z určité třídy) definováním několika velmi jednoduchých základních případů nebo metod (často jen jedné) a pak definováním pravidel pro rozdělení složitých případů na jednodušší případy.
Například následující je rekurzivní definice předků osoby:
Je vhodné si myslet, že rekurzivní definice definuje objekty ve smyslu „dříve definovaných“ objektů třídy, kterou definují.
Definice, jako jsou tyto, se často vyskytují v matematice. Například formální definice přirozených čísel v teorii množin je: 0 je přirozené číslo a každé přirozené číslo má svého nástupce, což je také přirozené číslo.
Použití rekurze v lingvistice a použití rekurze obecně se datuje od staroindického lingvisty Pāṇiniho v 5. století př. n. l., který rekurzi použil ve svých gramatických pravidlech sanskrtu.
Lingvista Noam Chomsky teoretizuje, že neomezené rozšíření jazyka, jako je angličtina, je možné pouze rekurzivním prostředkem vkládání vět do vět. Tak může ukecaná holčička říct: „Dorotka, která se setkala se zlou čarodějnicí ze Západu v Munchkin Landu, kde byla zabita její zlá čarodějnická sestra, ji zlikvidovala vědrem vody.“ Je jasné, že dvě jednoduché věty – „Dorotka se setkala se zlou čarodějnicí ze Západu v Munchkin Landu“ a „Její sestra byla zabita v Munchkin Landu“ – mohou být vloženy do třetí věty, „Dorotka ji zlikvidovala vědrem vody“, aby se získala velmi upovídaná věta.
Příklady matematických objektů často definovaných rekurzivně jsou funkce, množiny a zejména fraktály.
Myšlenku, že rekurze je nezbytná pro neomezené rozšíření jazyka, zpochybňuje lingvista Daniel Everett ve svém díle Cultural Constraints on Grammar and Cognition in Pirahã: Another Look at the Design Features of Human Language (Kulturní omezení gramatiky a poznávání v Pirahã: Jiný pohled na designové rysy lidského jazyka), ve kterém předpokládá, že kulturní faktory způsobily, že rekurze je zbytečná při vývoji jazyka Pirahã. Tento koncept zpochybňuje Chomského myšlenku a přijatou jazykovou doktrínu, že rekurze je jediný rys, který rozlišuje lidskou a zvířecí komunikaci a je v současné době předmětem intenzivní diskuse.
Rekurze v jednoduché angličtině
Rekurze je proces, kterým procedura prochází, když jeden z kroků procedury zahrnuje opakování celé stejné procedury. O proceduře, která prochází rekurzí, se říká, že je rekurzivní. Něco se také říká, že je rekurzivní, když je to výsledek rekurzivní procedury.
Abychom pochopili rekurzi, musíme si uvědomit rozdíl mezi procedurou a průběhem procedury. Procedura je soubor kroků, které mají být podniknuty na základě souboru pravidel. Průběh procedury zahrnuje skutečné dodržování pravidel a provádění jednotlivých kroků. Analogie by mohla být taková, že procedura je jako menu v tom, že se jedná o možné kroky, zatímco běh procedury je ve skutečnosti výběr chodů pro jídlo z menu.
Zákrok je rekurzivní, pokud jeden z kroků, které tvoří zákrok, vyžaduje nový průběh zákroku. Proto rekurzivní jídlo o čtyřech chodech by bylo jídlo, ve kterém jeden z možností předkrmu, salátu, předkrmu nebo dezertu byl celé jídlo samo pro sebe. Takže rekurzivní jídlo by mohlo být bramborové slupky, baby greens salát, kuřecí parmazán, a jako dezert, jídlo o čtyřech chodech, skládající se z krabích koláčů, Caesar salát, pro entrée, jídlo o čtyřech chodech, a čokoládový dort jako dezert, tak dále, dokud každé z jídel v rámci jídla je dokončena.
Rekurzivní procedura musí dokončit každý ze svých kroků. I když je v jednom ze svých kroků vyvolán nový běh, každý běh musí projít zbývajícími kroky. To znamená, že i když je salát celé čtyřchodové jídlo samo pro sebe, stejně musíte sníst předkrm a dezert.
Běžný geeky vtip (například ) je následující „definice“ rekurze.
Další příklad se vyskytuje v Kernighanově a Ritchieho „Programovací jazyk C“. Následující záznam rejstříku je na straně 269:
Jedná se o parodii na odkazy ve slovnících, která v některých neopatrných případech může vést ke kruhovým definicím. Vtipy mají často prvek moudrosti a také prvek nepochopení. Tento je také druhým nejkratším možným příkladem chybné rekurzivní definice objektu, chybou je absence podmínky ukončení (nebo absence počátečního stavu, pokud se na to podíváme z opačného úhlu pohledu). Nově příchozí na rekurzi jsou často zmateni její zdánlivou kruhovitostí, dokud se nenaučí vážit si toho, že podmínka ukončení je klíčová. Varianta je:
Dalšími příklady jsou rekurzivní zkratky jako GNU, PHP nebo TTP (Dilbert; „The TTP Project“).
Sierpinského trojúhelník – ohraničená rekurze trojúhelníků do tvaru geometrické mřížky.
Kanonický příklad rekurzivně definované množiny je dán přirozenými čísly:
Dalším zajímavým příkladem je množina všech pravdivých „dosažitelných“ tvrzení v axiomatickém systému.
(Všimněte si, že určení, zda se určitý objekt nachází v rekurzivně definované množině, není algoritmická úloha.)
Funkce může být částečně definována sama sebou. Známým příkladem je Fibonacciho číselná řada: F(n) = F(n − 1) + F(n − 2). Aby byla taková definice užitečná, musí vést k hodnotám, které nejsou rekurzivně definovány, v tomto případě F(0) = 0 a F(1) = 1.
Slavná rekurzivní funkce je Ackermannova funkce, která na rozdíl od Fibonacciho posloupnosti, je poměrně obtížné vyjádřit bez rekurze.
Standardní způsob, jak definovat nové systémy matematiky nebo logiky, je definovat objekty (například „pravdivé“ a „nepravdivé“ nebo „všechna přirozená čísla“), pak definovat operace na nich. To jsou základní případy. Poté jsou všechny platné výpočty v systému definovány pravidly pro jejich sestavení. Tímto způsobem, pokud se ukáže, že základní případy a pravidla jsou vypočitatelné, pak bude vypočitatelný i jakýkoliv vzorec v matematickém systému.
Zní to nenápadně, ale tento typ důkazu je běžným způsobem, jak dokázat, že výpočet je nemožný. To může často ušetřit spoustu času. Například tento typ důkazu byl použit k prokázání, že plocha kruhu není jednoduchý poměr jeho průměru a že žádný úhel nemůže být trisected s kompasem a přímočarý – obě hádanky, které fascinovaly starověké.
Rekurze v informatice
Běžnou metodou zjednodušení je rozdělení problému na dílčí problémy stejného typu. Jako technika počítačového programování se tomu říká rozděl a panuj a je klíčem k návrhu mnoha důležitých algoritmů, stejně jako je základní součástí dynamického programování.
Rekurze v počítačovém programování je příkladem, když je funkce definována sama sebou. Příkladem použití rekurze jsou parsery pro programovací jazyky. Velkou výhodou rekurze je, že nekonečný soubor možných vět, návrhů nebo jiných dat může být definován, analyzován nebo produkován konečným počítačovým programem.
Relace rekurence jsou rovnice, které rekurzivně definují jednu nebo více posloupností. Některé specifické druhy relace rekurence lze „vyřešit“ a získat tak nerekurzivní definici.
Funkce se volá rekurzivně na menší verzi vstupu (n – 1) a násobí výsledek rekurzivního volání číslem n, až dosáhne základního případu, analogicky k matematické definici faktoriálu.
Použití rekurze v algoritmu má své výhody i nevýhody. Hlavní výhodou je obvykle jednoduchost. Hlavní nevýhodou je často to, že algoritmus může vyžadovat velké množství paměti, pokud je hloubka rekurze velmi velká. Bylo tvrzeno, že rekurzivní algoritmy jsou srozumitelnější, protože neobsahují změť (např. extra proměnné) spojenou s algoritmy smyčky. Pro toto tvrzení neexistuje žádný experimentální důkaz.
Často je možné nahradit rekurzivní volání jednoduchou smyčkou, jak ukazuje následující příklad faktoriálu:
Příkladem rekurzivního algoritmu je procedura, která zpracovává (dělá něco s) všechny uzly stromové datové struktury:
Pro zpracování celého stromu je volána procedura s kořenovým uzlem představujícím strom jako počáteční parametr. Procedura se volá rekurzivně na všech podřízených uzlech daného uzlu (tj. podstromech daného stromu), až do dosažení základního případu, kterým je uzel bez podřízených uzlů (tj. strom bez větví, obvykle nazývaný „list“).
Samotná stromová datová struktura může být definována rekurzivně (a tak predestinována pro rekurzivní zpracování) takto:
V teorii množin se jedná o větu zaručující, že rekurzivně definované funkce existují. Vzhledem k tomu, množina , Prvek a funkce , Věta uvádí, že existuje unikátní funkce (kde označuje množinu přirozených čísel) taková, že
Vezměte dvě funkce a domény a codomain tak, že:
kde je prvek . Chceme dokázat, že . Dvě funkce jsou stejné, pokud:
měli byste zvážit N union {0} jako doménu F.
Některé běžné relace opakování jsou:
Toto je přesměrování, které by nepatřilo do tisku.
Může se však jednat o platnou navigační pomůcku pro vyhledávání v počítači.
Další informace najdete na odkazu kategorie.