Rekurze: Porovnání verzí
Smazaný obsah Přidaný obsah
→Co je rekurze: lfix |
→Efektivita rekurzivních algoritmů: lfix, pamet |
||
Řádek 212:
Pro vyjasnění spotřeby paměti, programová rekurze ukládá obvykle všechny lokální proměnné (protože [[statická analýza kódu]] je ještě nedokonalá), kdežto ruční obsluha zásobníku ukládá pouze potřebné informace.
Pokud máme víc rekurzivních volání za sebou v stejném podprogramu, tak jedno volání po skončení dealokuje svojí paměť a další volání ji znovupoužívá. Paměť se tím přirozeně a ''automaticky'' šetří a spotřeba paměti je obvykle menší než časová složitost, i když existují i výjimky, například [[Prohledávání do hloubky|prohledávání grafu do hloubky]] může na zásobník uložit všechny vrcholy grafu. Viz také ''vhodná'' implementace [[quicksort]]u a fibonacciho posloupnosti. Stručně řečeno, paměť pro zásobník odpovídá maximálnímu zanoření rekurze. <!-- kce6to 4as celkov0mu po4tu volani -->
[[Koncová rekurze]] je automatická optimalizacní technika, která snižuje spotřebu paměti pro ukládání návratových adres. V případě lineární rekurze optimalizovaný program může počítat bez používání zásobníku (v konstantní paměti), stejně jako while cyklus. V obecném případě poslední volání neukládá data na zásobník, ale přepíše nebo dealokuje rámec volající procedury. Optimalizaci lze provádět pro přímou i nepřímou rekurzi. Ne všechny kompilátory tuto techniku podporují. V některých případech je nutné (a vhodné) upravit program, aby se optimalizace koncové rekurze dala použít.
| |||