Ti hogyan értettétek meg a rekurzív algoritmusokat?

A rekurzív algoritmusok nagyon egyszerűek: szinte mindig van egy 0 eset, amire visszavezetődik.

Ha problémás, kezdd a hátulrekurzióval (amikor a függvény utolsó dolga az, hogy meghívja önmagát, tehát a visszatérés után már nem csinál semmit), az annyira triviálisan egy sima ciklus, hogy elég könnyű megérteni. Aztán azt is végiggondolhatod, hogy tulajdonképpen te egy verembe pakolsz bele állapotokat, és azokban haladsz lejjebb (vagy feljebb, attól függ, merről nézed a vermed). Hiszen tényleg egy veremre pakolod le a függvények keretét meg a lokális változókat. Gyakorlatilag egy mélységi bejárást folytatsz.

A tipikusan jó példa a faktoriális számítás. Oké, az megoldható rekurzió nélkül. Hogy számoljuk a faktoriálist?

Pl. 5! = 5*4*3*2*1 = 5 * 4!

Mennyi 16 faktoriálisa? Ha tudnám, hogy mennyi 15 faktoriálisa, akkor nem lenne gond, mert azt már csak meg kell szorozni 16-al. De mennyi 15 faktoriálisa? Ha tudnám 14 faktoriálisát, nem lenne gond, mert azt már csak meg kell szorozni 15-el… stb… stb… Mennyi 2 faktoriálisa? Ha tudnám mennyi 1 faktoriálisa, nem lenne gond, mert azt már csak meg kell szorozni 2-vel. Mennyi egy faktoriálisa? Hát azt történetesen tudjuk: 1! = 1.

function faktorialis1() {

return 1;

}

function faktorialis2() {

return 2 * faktorialis1();

}

function faktorialis3() {

return 3 * faktorialis2();

}

function faktorialis4() {

return 4 * faktorialis3();

}

…

function faktorialis16() {

return 16 * faktorialis15();

}

Gyakorlatilag erről van szó. Csak ugye egy függvénynek lehetnek paraméterei, így nem kell külön-külön függvényeket kreálni minden számhoz…

function faktorialis(n) {

if (n==1) return 1; //Ha n==1, akkor 1 faktoriálisát, azaz 1-et adunk vissza

return n*faktorialis(n-1); // Ha n!=1, akkor a faktoriálist az n! = n*(n-1)! képlettel adjuk vissza.

}

Azt próbáld meglátni, hogy mikor meghívsz egy ilyen függvényt, akkor az milyen állapotot "kap meg". Ezek az állapotok formailag ugyanolyanok, csak más konkrét adatokkal.

Egy (másik) példa a könyvtárfa bejárása. Amikor a gyökér könyvtárral meghívod a függvényt, akkor kap egy gyökeret, ami alatt fájlok és további mappák vannak. A fájlokat pl. feldolgozza, aztán elkezd végiglépkedni az almappákon. ?Minden ilyen almappával egy olyan függvényt kellene meghívni, ami belenéz, hogy milyen fájlok és további almappák vannak benne. De hát ez a függvényünk pont ezt csinálja! :) Szóval minden almappára sorban meghívjuk ugyanezt a függvény. Ilyenkor ugyanúgy fut le, mintha először hívtuk volna, csak most egy almappát fog gyökérnek látni, és az az alatti könyvtárakkal kezdi ugyanezt. Amikor elfogynak a közvetlenül a gyökér alatt lévő mappák, akkor return. Előbb utóbb az elsőként hívott szinten is elfogynak, és akkor lefutott a teljes bejárás.

A lényeg, hogy ezek a hívások úgy működnek, mintha minden egyes almappára egy új bejáró függvényt hívnánk, amelyik tiszta lappal indul. De mivel minden mappa tekinthető az alatta lévő struktúra gyökerének, ezért mindegyik ilyen függvény tök ugyanúgy működik, tehát nem kell külön megírni, hanem lehet mind ugyanaz a függvény. Ilyenkor önmagát hívogatja, de minden híváskor külön adatokkal, külön rutinként fut. (Kivéve persze a static változókat.)