6. Rekurzió I. Flashcards

Question 1

Q

Rekurzív algoritmusok (RA) jellemzői

(*rekurzív hívások (RH))

Answer

A

A RA(Rekurzív algoritmusok)-kat olyan fg (függvény)kel vagy eljárásokkal valósítjuk meg, melyek önmagukat hívják meg. Lehetséges közvetett rekurzív hívás is.Pl.: ha A fg meghívja a B fgt, majd a B hívja az A-t

Olyan fgek/eljárások lehetnek rekurzívak, melyekbe be van építve egy olyan eset, amikor már nem történik újabb RH(rekurzív hívás). (Ez biztosítja, hogy a RH egyszer véget érjenek, azaz ne alakuljon ki végtelen hívási lánc. A leállást biztosító esetet alapesetnek nevezzük. Pl.: FaktoriálisRekurzív fg-nél az alapeset az N = 0)

A RHk során a fgk/eljárások paraméterei folyamatosan változnak. (Ha nem változnának, akkor végtelen hívási láncba kerülnénk. A paraméterek változásának olyannak kell lennie, hogy a hívások során közeledjünk az alapeset felé.) (A FaktoriálisRekurzív fgnél a RHk során a fg bemeneti paramétere mindig eggyel csökkent, így közeledett az N = 0 alapesethez.)

A rekurzív fg egyszer kerül eltárolásra a memóriában. Az egyes fg.hívásokat a fg. paraméterei különböztetik meg egymástól. A paraméterek és a hozzájuk tartozó lokális változók viszont minden új fg.híváskor eltárolásra kerülnek a memória ún. verem részében.

(A RHnál a paraméterek és lokális változók eltárolása, azaz a hívások adminisztrálása idő és
memóriaigényestevékenység. Emiatt általában igaz, hogy egy algoritmus rekurzív megvalósítása lassabb, mint a hasonló logikára épülo iteratív megvalósítás.) (Konkrét implementáció esetén gyakran találkozhatunk azzal, hogy elfogy az „adminisztráció” számára fenntartott memória hely, mert túl sok rekurzív hívás történt már. Ez a probléma ciklusok alkalmazásával nem szokott előállni. A rekurzív gondolkodás sok esetben sokkalközelebb áll a probléma egyszeru megoldásához, mint az iteratív megvalósítás.)