Namų darbas

Ką atiduoti

algo su walk ir depth, praeinantį go test ./..., ir savo steko ribos ataskaitą.

1. Rask savo ribą

Padidink -n, kol rekursija lūžta. Užrašyk:

• didžiausią n, kuris praėjo;
• mažiausią n, kuris lūžo;
• frames elided skaičių iš pranešimo;
• apskaičiuotą kadro dydį baitais.

Palygink su 3 žingsnio 119 baitų. Jei tavo skaičius kitoks — paaiškink, kas tavo WalkRecursive skiriasi.

2. Kadro dydis nėra pastovus

Pridėk prie WalkRecursive didelį vietinį kintamąjį, pvz. var buf [1024]byte (ir panaudok jį, kad kompiliatorius neišmestų).

Vėl rask ribą. Kiek kartų ji sumažėjo? Ar tai atitinka pridėtą kilobaitą?

3. Greitis

Pamatuok abu apėjimus, n = 10⁵ … 10⁷:

n	rekursyviai	cikliškai	santykis

Ciklinė versija turi laimėti visur. Vienu sakiniu — kodėl.

4. Šakotas medis

Grandinė yra blogiausias atvejis. Sukurk subalansuotą medį su tuo pačiu aplankų skaičiumi (-depth ir -branch).

Koks rekursijos gylis dabar? Susiek atsakymą su medžio aukščiu, ne su aplankų skaičiumi.

Šitas skaičius yra 11 ir 12 pamokų anonsas. Užsirašyk jį — grįši.

5. Sprendimas

Vienas pastraipos atsakymas: kada tavo programoje rašysi rekursiją, o kada — savo steką?

Suformuluok taisyklę, kuri remiasi gyliu, ne skoniu. Taisyklė turi leisti atsakyti nepaleidus programos.