Rekurze: Porovnání verzí

Smazaný obsah Přidaný obsah
m →‎Efektivita rekurzivních algoritmů: ++koncova rekurze, mozna to patri tam
→‎Odstraňování rekurze: styl: +se programuje
Řádek 249:
=== Odstraňování rekurze ===
;Odlišení rekurzivního popisu a vhodné implementace
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 nemámeprogramá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ě''' implementujemeimplementuje, 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í). 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
# Speciální přístupy jsou tabelace, koncová rekurze a návrhový vzor [[trampolína]], zahrnujíc i [[dynamické programování]].
# Fibonacciho čísla i při naivní zápisu algoritmu s exponenciální složitostí potřebují pouze lineární počet položek na zásobníku. JsouPoložky jsou sice velké, ale úměrně výsledku, takže tuta paměť bychomse muselimusí stejně alokovat.
# Rekurze implementovaná obecně uchovává na zásobníku případně systémové informace kromě vlastních (lokálních) proměnných algoritmu. Spotřeba paměti je větší než při ručním uchovávání pouze potřebných informací.