FAV-ZCU/KIV PPA2/07. Odstranění rekurze.md

2 KiB

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