Rekursija nepanaikina steko

Ketvirtoje pamokoje pastatei steką ir baigei ją pastaba: transit paiešką rašo cikliškai, su aiškia eile, o ne rekursija. Ši pamoka paaiškina kodėl.

Rekursija nepanaikina steko

Biblioteka su aplankais aplankuose — natūraliai rekursyvi struktūra:

  root
   ├── rokas
   │    ├── 90-ieji
   │    └── klasika
   └── džiazas
        └── bebopas

Kad suskaičiuotum visus įrašus, reikia nusileisti į kiekvieną aplanką ir grįžti ten, kur buvai. Kažkas turi atsiminti, kur grįžti.

Rekursijoje tas kažkas yra iškvietimų stekas (call stack) — ta pati struktūra, kurią pastatei praeitoje pamokoje, tik ją tvarko ne tu, o programos vykdymo aplinka. Kiekvienas WalkRecursive iškvietimas paguldo ant jo kadrą (frame): argumentus, vietinius kintamuosius ir adresą, į kurį grįžti.

Rekursija ne pašalina steką. Ji paslepia jį — ir atiduoda jo valdymą kitam.

Šioje pamokoje parašysi tą patį apėjimą du kartus: rekursyviai ir cikliškai su savo steku. Rezultatai bus identiški, nes tai tas pats algoritmas.

Kur tai svarbu

Jei stekas tavo, jį matai: gali paklausti, koks jo gylis, gali nustatyti ribą, gali jį išsaugoti ir tęsti vėliau.

Jei stekas paslėptas, nieko iš to negali. O kai jis baigiasi — programa ne grąžina klaidą, o miršta.

Trečiame žingsnyje pamatysi, kaip tiksliai.