Rekurze: Porovnání verzí
Smazaný obsah Přidaný obsah
m →Rekurze a datové struktury: Odstranění nesmyslného odkazu značka: editace z Vizuálního editoru |
m Náhrada dle ŽOPP z 4. 11. 2015; kosmetické úpravy |
||
Řádek 4:
'''Rekurze''' je často používaná technika v [[matematika|matematice]] a [[Informatika|informatice]]. Termín je pravděpodobně odvozen z latinského slovesa ''recurso'' (vrátit se) nebo substantiva ''recursus'' (návrat, zpětný běh).
Používá se i v přirozeném jazyce a jsou i rekurzivní obrázky, např. od [[M. C. Escher]]a.
== Co je rekurze ==
Řádek 10:
V oblasti matematiky pojem rekurze chápeme jako definování objektu pomocí sebe sama. Využívá se například pro definici [[Přirozené číslo|přirozených čísel]], [[Strom (datová struktura)|stromových struktur]] a některých [[Funkce (matematika)|funkcí]].
V imperativním [[programování]] rekurze představuje opakované vnořené volání stejné [[Funkce (programování)|funkce]] (podprogramu), v takovém případě se hovoří o [[Rekurzivní funkce (programování)|rekurzivní funkci]]. Obvyklou součástí rekurzivní funkce je ukončující podmínka určující, kdy se má vnořování zastavit. V tom případě funkce vrací výsledky spočítané nerekurzivně. Chyba v rekurzi může způsobit vyčerpání zásobníku a následně ukončení programu anebo zacyklení.
<!-- Jelikož bývá nejčastějším zdrojem chyb{{Doplňte zdroj}}, je třeba ji navrhnout dostatečně robustním způsobem a prověřit veškeré možné stavy.
-- NE VZDY Při selhání ukončující podmínky dochází k plnému obsazení paměti a zhroucení programu.-->
Pro uplatnění rekurzivních algoritmů je zapotřebí, aby programovací jazyk umožňoval volání podprogramu ještě před ukončením jeho předchozího volání. Obvyklý způsob implementace (v překladači) je, že data volající funkce se uloží na zásobník předtím, než se volá rekurze.
V praktických aplikacích obvykle po každém rekurzivním volání funkce dochází ke zjednodušení problému. Takové funkce končí.
<!-- NO, NEMUSI. Ale pokud má výpočet končit, tak aspoň občas se zjednodušit musí.-->
Pokud nenastane koncová situace, provede se rekurzivní krok.
Nicméně jsou i programy, které ukončující podmínku neobsahují nebo se k ní nedostanou, např. [[filtr (informatika)|filtry]] nebo [[roura (Unix)|pípy v Unixu]]. Ty cyklí v nekonečném cyklu, ale přitom můžou zpracovávat nekonečný proud dat ([[Datový proud|stream]]) a/nebo ho generovat.
Každý [[algoritmus]] využívající rekurzi lze přepsat do nerekurzivního tvaru při použití [[Zásobník (datová struktura)|zásobníku]] nebo jiné paměťové struktury. A spíš v teorii, i naopak.
Řádek 54:
</source>
Dalším využitím je řešení obecných úloh rozkladem na dílčí úlohy stejného typu, které řešíme stejným způsobem. Tento způsob řešení je klíčem k návrhu mnoha důležitých algoritmů. <s>proto</s> Je jednou ze základních částí v jednom z popisů [[dynamické programování|dynamického programování]]. Často jej nalezneme v algoritmech typu „[[rozděl a panuj]]“, anglicky „divide and conquer“. Tato programovací technika je vhodná pouze pro omezený okruh úloh,{{
Rekurze se velmi často využívá při syntaktické analýze textů formálních jazyků ([[programovací jazyk]]y, matematické vzorce{{
Typickým příkladem přirozeně rekurzivního algoritmu je průchod stromem:
Řádek 73:
Pro zpracování celého stromu voláme na počátku proceduru s počátečním parametrem - kořenový uzel. Procedura rekurzivně volá sebe sama pro potomky aktuálního uzlu (tedy pro podstromy daného stromu), dokud nedosáhne k uzlům, které nemají žádné potomky (uzly bez potomků jsou nazývány „listy“).
Při vykonání určité operace se všemi soubory v [[Adresář (informatika)|adresářové]] struktuře na [[pevný disk|pevném disku]] je možné použít rekurzi, neboť na každý nalezený podadresář lze automaticky zavolat stejnou funkci.
Obecně, popis algoritmů pro rekurzivní datové struktury (stromy, adresáře, ale i čísla) se jednoduše zapíše rekurzivně.
Velmi zajímavou oblastí použití rekurze jsou [[fraktál]]y.{{
=== Rekurze v programovacích jazycích ===
Řádek 84:
Jednou ze základních součástí většiny programovacích jazyků jsou cykly. Jedná se o nejrozmanitější obměny syntaxe příkazů [[For cyklus|for]], [[While-do cyklus|while]] a jim podobných. Cílem těchto nástrojů je umožnit programování opakovaných činností. Existují však i jazyky, které dokazují, že cykly nejsou jedinou cestou, a jejich užití buď nepodporují vůbec, či využívají těchto nástrojů pouze zřídka. Jedná se například o Lisp či Prolog. Pro řešení opakovaných činností používají právě rekurzi a suverénně dokazují, že v mnoha případech se jedná o mocnější a univerzálnější techniku.
Rekurzi obsahují v nějaké podobě všechny moderní programovací jazyky, jako (podle abecedy) C, C++, Java, Pascal a dnes ''snad'' i [[Fortran]], který ji původně neměl.
I klasické jazyky dokáží i klasicky zadané rekurzivní algoritmy (například quicksort a mergesort) vyjádřit přímočaře rekurzivně anebo pomocí cyklů či jiných prostředků jazyka, a to i v případě , že použitá datová struktura je pole.
Řádek 134:
<source lang="c">
double faktorial(int f){
if (f <= 1)
return 1;
else
return f * faktorial(f - 1);
}
Řádek 162:
=== Quicksort ===
Ukázkou vhodného užití rekurze je třídící algoritmus [[QuickSort]]. Jedná se o jeden z nejrychlejších (pouze v příznivém případě (je častý)) a zároveň i jednodušších algoritmů řazení. Princip spočívá v rozdělení posloupnosti čísel do dvou oblastí na základě srovnání s hodnotou nějakého vhodně zvoleného členu posloupnosti – nazýváme ji ''pivot''. Do první oblasti umístíme čísla menší než pivot a do druhé čísla větší. (Pivot se často volí z prostřed posloupnosti pro případ uspořádané nebo částečně uspořádané posloupnosti.) Dále se obě části rekurzivně řadí stejným postupem, dokud nebudou mít jednotlivé úseky pouze jeden člen. V momentě, kdy jsou takto seřazeny obě části, je seřazená i celá posloupnost.
;Program v jazyce C++
Řádek 199:
Strom výpočtu může sloužit pro ilustraci algoritmu a pro výuku a obvykle se explicitně v programu nevytváří, ale např. při syntaktické analýze v algoritmu [[analýze rekurzivním sestupem]] je strom ve vhodné podobě výstupem této fáze zpracování.
Rekurzí se přirozeně procházejí a zpracovávají rekurzivní datové struktury.
Rekurze, ale nejen ona,
Data se můžou generovat líně a zpracovávat [[synchronizovaně]], takže může stačit konečná, někdy i malá paměť ([[buffer]]).
Pro odlišení potenciálně nekonečných dat (stream) od obvyklých konečných dat (spojový seznam), i když libovolně velkých, se pro ty první používá pojem {{cizojazyčně|en|codata}}. Pro představu, simulátor konečného automatu, který dostává nekonečný proud písmenek a vrací nekonečný proud svých stavů, bude ukončen z jiných příčin. Pokud simulátor rozeznává konec proudu [[EOF]], tak může i skončit.
Řádek 239:
</pre>
''n''-té Fibonacciho číslo lze spočítat i bez rekurze. Stačí prvky posloupnosti počítat od začátku a ukládat je například do [[Pole (datová struktura)]]. První dva členy jsou dány (0, 1) a každým součtem předchozích dvou prvků lze získat další prvek. Na podobné chování, tj. ne příliš optimalizované - z hlediska paměti, vede použití tabelace na rekurzivní algoritmus.
<pre>
Řádek 263:
Výhoda tabelace je, že nemusíme měnit rekurzivní algoritmus. Nevýhoda je potřeba paměti pro tabulku, která je případně větší než při "ručním" návrhu a počítání zdola. V případě Fibonacciho čísel přímočaře použijeme pole P[] velikosti N, kdežto při ručním návrhu stačí pamatovat si poslední dvě čísla.
Speciálně, některé úlohy dynamického programování dovolují reformulaci algoritmu šetřící paměť.
<!--Pokud je struktura výpočtu pravidelná, resp. známá anebo odvoditelná, tak je efektivnější výpočet zdola, tj. bez rekurze, když už máme pole -->
Řádek 272:
Rekurze dovoluje stručný zápis. To je i tím, že některé věci se berou implicitně, konvencí, a tudíž se nemusí explicitně vypisovat. Ale protože jsou následně řízeny softwarem, tak nad nimi programátor nemá plnou kontrolu a jsou realizovány obecně a tudíž neefektivně pro danou konkrétní úlohu.
Stručný zápis je vhodný pro úvodní seznámení s algoritmem či jeho hlavní myšlenkou, pokud teda čtenář už ví, co to je rekurze a nečiní mu problémy. Tento stručný zápis bez mnoha technických detailů nemusí být vhodný pro přímočarou implementaci.
Následně se algoritmus '''vhodně''' implementuje, což může znamenat i opuštění rekurzivního popisu, návrh nových datových struktur (vlastního zásobníku či pole pro dynamické programování) a jejich vhodnou obsluhu. Vhodná implementace pak funguje dostatečně dobře a případně se to dá i zdůvodnit. Například [[quicksort]] dovoluje taková implementační rozhodnutí.
;Související problémy
| |||