Gyakorlati alapok II.
Rekurzió
A rekurzió érdekes programozás-technikai megoldás: a függvény önmagán belül mindig önmagát hívja meg. Mitológiailag nézve ez abszolút az önmagába harapó kígyó, az Uroboros esete:
A fenti mitológiai példából még nem igazán érthetjük meg a rekurzió informatikai jelentőségét. A tapasztaltak számára azonban már feltűnhetett, hogy a rekurzív, azaz mindig önmagát meghívó függvény ciklikusan végez azonos jellegű tevékenységet. Az ilyen függvény tehát iterál, a fenti példával élve: mintha a kígyó többször is felfalná önmagát (de mindközben nem látogatná meg az illemhelyet). Ebben a pillanatban egyértelmű párhuzamot állíthatunk az iteráló műveletek...
...és a rekurzió között: ezek a műveletfajták legtöbbször szabadon egymásba alakíthatók (amint erre később látni fogunk példákat). Némely esetben a rekurzív megoldás az optimális implementáció, máskor viszont a kód jobb átláthatósága érdekében (tipikusan ilyenek az oktató kódok), inkább érdemes más iteráló megoldást keresni.
Lényegében kétféle rekurzió létezik:
-
végtelen idejű,
-
véges idejű.
Előre venném a végtelen rekurziót, mert egyszer és mindenkorra le kell szögeznünk, hogy egy rekurzív művelet futását szabadon hagyni, azt semmilyen módon nem korlátozni programozási-technikai esztelenség és könnyen lehet állásvesztés a jutalma. A végtelen rekurzió sérti az egyik legfontosabb általános, algoritmikus alapelvet (Az algoritmus fogalma című fejezet), miszerint bár egy algoritmus működhet végtelen ideig, mégiscsak véges számú lépést tartalmazhat (például jelzőlámpa-algoritmus kereszteződésben).
Végtelen rekurzió esetében azonban az "önfüggvényhívás" előbb-utóbb az Univerzum összes műveleti memóriáját meg fogja tölteni; legalábbis ennek elvileg nem lesz akadálya, amely hibalehetőségre persze a Java alkotói is gondoltak, amikor bevezették a veremtúlcsordulás-, azaz stackoverflow-kivételkezelést.
Ellentétben a végtelen rekurzióval, a véges idejű rekurzióba mindig beépítésre kerül egy belső szabályozás, amely le fogja állítani a folyamatos önfüggvényhívást. Ez az egyedüli követendő eljárás.
Pénzes László