45 lines
2 KiB
Markdown
45 lines
2 KiB
Markdown
# Odstranění rekurze
|
|
|
|
**Proč?**
|
|
- problémy s hloubkou zanoření (velikost zásobníku je malá)
|
|
- neefektivní, protože se při volání metod kopírují hodnoty skutečných parametrů do zásobníku
|
|
|
|
### Koncová rekurze
|
|
|
|
- kód končí jediným rekurzivním voláním
|
|
- nejjednodušší druh rekurze, je snadné přepsat na cyklus
|
|
|
|
### Eliminace vlastním zásobníkem
|
|
|
|
- použití zásobníku jako seznamu úkolů (například třída `Task`)
|
|
- položky v zásobníku budou obsahovat:
|
|
- co se má udělat (parametry)
|
|
- v jaké části úkolu jsme (segment)
|
|
- data nutná pro pokračování výpočtu (mezivýsledky)
|
|
- pokud je potřeba pro dokončení úkolu rekurze, přidá se do zásobníku nový úkol
|
|
- až se dojde k triviálnímu úkolu, data se předají dalšímu úkolu
|
|
|
|
**Jak rekurzi odstranit?**
|
|
- rozdělíme kód na segmenty mezi rekurzivními voláními
|
|
- na začátku do zásobníku vložíme pouze hlavní úkol
|
|
- zpracováváme položky zásobníku, dokud není prázdný
|
|
- místo rekurzivního volání:
|
|
- uložíme stav výpočtu položky na vrcholu zásobníku (stavové proměnné)
|
|
- zvýšíme segment na vrcholu zásobníku (jsme o jednu část úkolu dál)
|
|
- do zásobníku přidáme nový úkol reprezentující rekurzi
|
|
- ukončíme zpracování aktuálního úkolu (smyčka se k němu vrátí později)
|
|
- místo vrácení hodnoty:
|
|
- uložíme výsledek do proměnné `result`
|
|
- odebereme úkol z vrcholu zásobníku
|
|
- při pokračování dalším segmentem:
|
|
- obnovíme stavové proměnné z položky na vrcholu zásobníku
|
|
- výsledek posledního rekurzivního volání se nachází v proměnné `result`
|
|
- na konci vrátíme proměnnou `result`
|
|
|
|
**Závěr**
|
|
- každou rekurzivní funkci je možné přepsat bez použití rekurze
|
|
- pracný mechanický postup
|
|
- horší přehlednost kódu
|
|
- potřeba implementace zásobníku
|
|
- přepsání bez rekurze zachovává třídu složitosti (nezajišťuje efektivitu)
|
|
- pro nalezení efektivnější implementace mechanický postup neexistuje |