| Tartalomjegyzék |
|---|
| Rekurzivitás - elegancia veszélyekkel |
| függvényhívás |
| Minden oldal |
könyvtárbejáró program forrása is bemutatásra kerül, mely kiaknázza a rekurzivitás elõnyeit.
Rekurzivitás - elegancia veszélyekkel
“Ahhoz, hogy megérthessük a rekurzivitást, előbb meg kell értsük a rekurzivitást."
Az elõbbi mondatot egy C++ fórumon olvastam, és elég frappánsan foglalja össze a rekurzivitás lényegét.
A rekurzív szó legjobban az "önmagára hivatkozó", "önmagát hívó" fogalmakkal lehet megközelíteni, és az utóbbi forma az, ami legjobban tükrözi a jelentését, ha programozásról illetve függvényekrõl beszélünk. Az önmagát meghívó függvényt tehát rekurzív függvénynek nevezzük.
void fv()
{
// ... kód
fv(); // a függvény ezen a ponton önmagát hívja
// ... kód
}
A fenti kódrészletben az fv()fügvény implementációja látható, mely egy bizonyos ponton meghívja önmagát. Az a furcsa helyzet áll elõ, hogy a hívó és a hívott függ-vény ugyanaz; lényeges, hogy a hívó függvény lokális változói ebben a különleges esetben is konzisztensek maradjanak.
Ahhoz, hogy megértsük a rekurzivitás eleganciája mögött megbúvó veszélyeket, nézzük meg, mi is történik valójában egy függvény hívásakor.
Félretéve egy kis idõre a rekurzivitást (de csak azért, hogy utána még nagyobb lendülettel rávessük magunkat), vizsgáljuk meg az alábbi kódot:
void g()
{
//...
int i = 0;
short j = 255;
fv(); // meghívjuk fv()-t
//... fv() hívása után ide kerül a vezérlés
return;
}
Amikor a g() függvénybõl meghívjuk fv()függvényt, gondoskodni kell g() lokális vál-tozóinak elmentésérõl; ezek értéke adott esetben változatlan kell maradjon miután a vezérlés az fv()hívásának befejeztével újra a g() kódjában folytatódik. Szerencsére errõl nem a programozó, hanem a fordító gondoskodik. Az ideiglenes illetve lokális változók tárolása az ún. verem-memóriában történik (angolul STACK), ami egy LIFO típusú adatstruktúra.
A LIFO (Last In First Out) szó jól mutatja a verem szervezését: mindig az utoljára behelyezett elemet nyerjük ki elõször. A működése nagyjából olyan, mintha tányérokat helyeznénk egymásra, és az utolsót tudjuk leemelni elõször (persze csak akkor, ha a megszokott módon közelítjük meg a problémát ;)).
Minden alkalmazás számára lefoglalásra kerül egy bizonyos méretu szelet a memóriából, ennek egy része a verem-memória számára van fenntartva. A veremmemória tehát véges, és "lefele nõ", azaz az újabb elemek egyre csökkenõ memóriacímekre kerülnek.
| < Előző | Következő > |
|---|
