Pratybos
Penkios užduotys. Visos apie tą patį: kur laikomas stekas.
1. MaxDepth(f *Folder) int
Grąžina giliausio aplanko gylį. Parašyk abu variantus — rekursyvų ir ciklinį.
Ciklinis turi laikyti poras (aplankas, gylis). Kodėl gylio negali laikyti
atskirai nuo aplanko?
2. WalkIterativeDepth(root *Folder) (items, maxStack int)
Papildyk ciklinį apėjimą taip, kad jis grąžintų didžiausią pasiektą steko gylį.
Paleisk su savo medžiu ir su grandine. Kuriuo atveju gylis lygus n? Kodėl šakotame medyje jis daug mažesnis?
Šito rekursyvi versija pasakyti negali. Paaiškink, kodėl.
3. Faktorialas ir uodeginė rekursija
Parašyk Fact(n int) int rekursyviai, tada perrašyk be rekursijos.
Kai kurios kalbos tokį atvejį optimizuoja ir steko nenaudoja. Go — ne.
Patikrink: kiek giliai nueina tavo Fact, kol nulūžta? Palygink su 3 žingsnio
119 baitų kadru.
4. Fibonačis ir pakartotas darbas
Fib(n int, c *metrics.Counter) int — naivi rekursija, skaičiuok iškvietimus.
Paleisk su n = 10, 20, 30 ir surašyk skaičius. Augimas nėra tiesinis ir nėra kvadratinis. Įvertink jį.
Tada pridėk map[int]int jau apskaičiuotoms reikšmėms. Kiek iškvietimų dabar?
5. Kada rekursija yra teisingas pasirinkimas
Trys žingsniai parodė, kad ciklinė versija greitesnė ir saugesnė.
Tai kodėl kas nors rašo rekursiją? Nurodyk konkretų atvejį iš savo algo
projekto, kur rekursija akivaizdžiai aiškesnė, ir įvertink, koks gylis jai
gresia blogiausiu atveju.
Jei gylis ribotas ir žinomas — rekursija yra teisingas atsakymas. Parodyk, kad taip yra.