| 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.
A függvényhívás - avagy mi történik a színfalak mögött
Most, hogy tisztáztuk a veremmemória fogalmát, megvizsgálhatjuk, mi is történik a kulisszák mögött egy függvény hívásakor.
"Egy függvény hívásakor a következõ történik:
- a hívott függvény paraméterei bekerülnek a verembe (jobbról-balra haladva a paraméterlistában); A VisualC++ fordítója különbözõ függvényhívási konvenciókat alkalmaz, és elõfordulhat, hogy verem helyett aC++processzor regisztereit használja, így optimalizálva a paraméterek átadását. A Microsoft-specifikus függvényhívási konvenciókra hamarosan kitérek.
Megjegyzés
Ha a függvényparaméterek érték szerint kerülnek átadásra, akkor létrejön róluk egy lokális másolat. Pointer vagy referencia átadása esetén ez nem történik meg, ezért osztály típusú paraméterek esetében megspórolhatjuk az ideiglenes objektum létrehozásával majd megszuntetésével járó - másoló konstruktor illetve destruktor - függvényhívásokat. A cím átadásával azonban lehetõvé válik az objektum módosítása, amit kivédhetünk a const kulcsszóval. - a függvényhívást követő utasítás címe is bekerül a verembe; ezáltal a processzor tudni fogja, hogy a hívott függvényből visszatérve honnan kell folytassa a végrehajtást
- a vezérlés a hívott függvény címére ugrik
- megtörténik a függvény saját veremterületének felállítása - létrejön az ún. "stack-frame", amire a függvénynek a lokális illetve automatikus változói számára van szüksége
- az érték szerint átadott paraméterekből másolatok jönnek létre; ezek a másolatok lokálisak a hívott függvényben, ezért megszűnnek a verem visszafejtése során;
- végrehajtódik a függvény kódja
- a függvény kódjának végrehajtása után megtörténik a függvény lokális veremterületének visszafejtése; ezt végezheti a hívó vagy a hívott függvény, függvényhívási konvenciótól függõen. Lényeges, hogy a verem visszafejtés végén a verem utolsó eleme a 2. pontban elmentett visszatérési cím legyen - különben a vezérlés nem a megfelelõ helyre kerül, aminek kellemetlen következményei lesznek. Ez szerencsére csak extrém esetekben fordulhat elõ (lásd következõ fejezet), hiszen a verem karbantartását a fordító által generált kód biztosítja."
"A függvényhívás. Függvényhívási konvenciók - mi történik a színfalak mögött" részlet "Gyakorlati C++" című könyvemből
Nyisztor Károly
| < Előző | Következő > |
|---|
