Rekurzió és barátai
Programozás során mondhatni állandó jelleggel találkozunk azzal a szituációval, hogy valamilyen utasításokat újra és újra végre kell hajtani, hogy elérjük a kívánt eredményt. Épp ezért az imperatív programozási nyelvek egyik alapvető nyelvi eleme a ciklus (angolul loop) és a rekurzió, amik segítenek nekünk ilyen szituációkban. Nézzük először a ciklust! A ciklus szerepe többes.
Utasítások ismétlése
Fordítási időben ismert ismétlésszám esetén
Képzeld el először azt az egyszerű helyzetet, hogy ki szeretnéd íratni a konzolra azt az üzenetet, hogy „Ain’t nobody got time for that”! Ez egyszerű. Java-ban, így néz ki:
public class LoopDemo {
public static void main(String[] args) {
System.out.println("Ain't nobody got time for that");
}
}
Ha most annyiban változik a feladatod, hogy nem egyszer, hanem 10-szer szeretnéd kiíratni, akkor ezt nyilván meg tudnád így valósítani:
public class LoopDemo {
public static void main(String[] args) {
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
System.out.println("Ain't nobody got time for that");
}
}
Ez egy megoldás, de nem a legjobb több szempontból sem:
- sokat kell gépelni
- hosszú lesz a kész program forráskódja
- nehéz rajta változtatni
Ha egyszerűen megismételted a kiíratás parancsot, mint a fenti megoldásnál, és később kiderül, hogy nem is pont ezt a szöveget kell kiíratni (és ez a valódi szoftver projekteknél is így van, hogy folyton változik az, hogy mit is kell a programnak csinálnia), akkor bajban vagy, mert mind a 10 sorban ki kell javítani. Például ha kell egy felkiáltójel is a sor végére, akkor mind a 10 sorban ki kell tenned:
public class LoopDemo {
public static void main(String[] args) {
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
System.out.println("Ain't nobody got time for that!");
}
}
Sokkal egyszerűbb közölni a géppel, hogy van itt ez a parancs:
System.out.println("Ain't nobody got time for that!");
és ezt ismételd meg 10-szer! Ezt ciklussal így tudod megtenni:
public class LoopDemo {
public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.println("Ain't nobody got time for that!");
}
}
}
Így sokkal tömörebb kódot kaptál. Ha nem 10-szer kell ismételni, hanem 100 000-szer (és van ilyen a gyakorlatban), akkor még sokkal kiélezettebb a helyzet és még nagyobbat nyersz azzal, hogy ezt a tömör formát használod.
Futási időben ismert ismétlésszám esetén
De van egy másik fontos helyzet, amikor a ciklusok nagyon jól jönnek és nélkülözhetetlenek. Ha már akkor biztosan tudod, hogy egy adott parancsot hányszor kell ismételtetni a géppel, amikor írod a programot (vagyis fordítási időben), akkor még nem is annyira kardinális kérdés, hogy ciklussal valósítod-e ezt meg, vagy nem. De ha időben sokkal később derül csak az ki, hogy egy parancsot hányszor kell ismételni (futási időben), konkrétan akkor, amikor a programodat valaki használja, vagyis futtatja, akkor nincs más lehetőséged, mint ciklust használni. Például a programodnak lehet, hogy úgy kell működnie, hogy amikor elindítja a felhasználó, akkor először be kell kérnie a programnak, hogy hányszor szeretné látni az üzenetet, és a felhasználó válasza alapján más és más eredményt fog adni:
import java.util.Scanner;
public class LoopDemo {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.print("Kérlek, adj meg egy számot: ");
int times = in.nextInt();
for (int i = 0; i < times; i++) {
System.out.println("Ain't nobody got time for that!");
}
}
}
Azonban ciklikus utasítás végrehajtást nem csak ciklussal lehet elérni.
Faktoriális példa – ciklussal és rekurzióval
Vegyünk egy példát, a faktoriális számítást! Javaslom, hogy ez te is próbáld ki és programozd le saját gépeden, hisz nagy sikerélményt ad, ha meg tudod beszélni a gépeddel, hogy mit tegyen meg neked! Ehhez ezen az oldalon találod meg a fejlesztői környezet beállításának lépéseit. Kövesd végig az ottani lépéseket és térj vissza ide utána!
A faktoriális jele a matematikában a felkiáltójel. Csak pozitív egész számnak értelmezzük a faktoriálisát. Az 5 faktoriálisát például így írjuk le: 5!
Az 5! nem jelent mást, mint 5 * 4 * 3 * 2 * 1, vagyis igazából néhány szorzás műveletnek a rövidítése. Az 5! az előbbiek alapján 120. Ezt Java programmal is jól le tudod modellezni, hisz annyit kell tenned, hogy veszed a számot, aminek a faktoriálisát ki szeretnéd számolni és elkezdet összeszorozni a tőle eggyel kisebb számokkal, amíg el nem éred az 1-et. Amikor eléred az egyet, akkor kész vagy.
Megvalósítás ciklussal
Iterációval, vagyis hagyományos ciklussal ezt így tudod megvalósítani:
public class FactorialWithIteration {
public static void main(String[] args) {
int theNumber = 5;
int result = factorial(theNumber);
System.out.println("The factorial of " + theNumber + " is " + result + ".");
}
private static int factorial(int theNumber) {
int result = 1;
for (int i = theNumber; i > 0; i--) {
result *= i;
}
return result;
}
}
Megvalósítás rekurzióval
A rekurziónál nem kell egyik ciklust sem használnod, ami a Java nyelvben elérhető, hisz az utasítások ismételt végrehajtását azzal is elérheted, hogy egy metódust önmagából újra meghívsz:
public class FactorialWithRecursion {
public static void main(String[] args) {
int theNumber = 5;
int result = factorial(theNumber);
System.out.println("The factorial of " + theNumber + " is " + result + ".");
}
private static int factorial(int theNumber) {
if (theNumber == 1) {
return 1;
}
return theNumber * factorial(theNumber - 1);
}
}
Az 5! az nem más, mint 5 * 4!
A 4! az nem más, mint 4 * 3!
A 3! az nem más, mint 3 * 2!
A 2! az nem más, mint 2 * 1!
Az 1! az 1.
Lényegében ezt a logikát valósítottad meg a fenti kódban.
Ciklus és rekurzió összehasonlítása
Hasonlóságok rekurzió és ciklus között
Közös a két módszerben, hogy mindkettővel utasításokat tudunk ismételtetni a Java virtuális géppel, vagyis nem kell kiírnunk többször ugyanazt a parancsot csak azért, hogy újra lefuttassa, hanem elég egyszer. A faktoriális esetén ez a művelet a szorzás. Ha megfigyeled, akkor maga a szorzás művelet * csak egyszer szerepel a forráskódban.
Közös még az is a két módszerben, hogy mindkettőnél van egy feltétel, ami szabályozza, hogy mikor kell az ismétlést abbahagyni. A ciklusnál ezt ciklusban maradási feltételnek hívjuk, a rekurziónál pedig tipikusan kilépési feltételnek. Ha nem lenne ilyen feltételünk, akkor az ismétlés a végtelenségig zajlana, az adott utasításokat újra és újra végrehajtaná a gép, és sose érne véget. Ez működésképtelen programhoz vezetne.
Különbségek rekurzió és ciklus között
Különbség a két módszer között a végrehajtás menete. A rekurziónál egy metódus önmagát hívja meg újra meg újra. Ennek van némi overhead-je a Java virtuális gép szintjén, mind processzorhasználat, mind memóriahasználat terén. A metódushívások láncolatát a JVM egy elkülönített memóriaterületen, a stack-en (verem) tárolja, aminek limitált a mérete. Ha ez megtelik, akkor StackOverflowError-t kapunk, ami egy komoly hiba, és ami az adott végrehajtási szál azonnali leálláshoz vezet. Ez egy nagy alkalmazás esetén elfogadhatatlan.
A ciklus esetén a fent említett overhead nem lép fel, így hatékonyabb program végrehajtáshoz vezet a használata.
Lényeges különbség még a két módszer között az, hogy vannak olyan problémák, amik rekurzióval sokkal tömörebben megfogalmazhatók, és ha ezt használod, akkor maga a forráskód rövidebb lesz, míg ha iterációval írnád, akkor hosszabb kódot kapnál. Ezt az adott szoftverfejlesztési projekt függvényében tudod eldönteni, hogy megéri-e a rekurzív megvalósítással élned.
Összefoglaló
Összességében elmondható, hogy utasítások ismétlésére nem csak ciklusok használhatók, hanem önmagukat meghívó úgynevezett rekurzív metódusok is. Különös figyelemmel kell azonban lenned, amikor ilyen szerkezetet használsz, hisz ha az ismételt végrehajtásnak a kilépési feltételét nem jól adod meg, akkor az hibás program működéshez vezethet. Ez rekurzió esetén StackOverflowError-hoz vezet míg ciklusok esetén végtelen ciklushoz, vagyis a programod egy adott utasításblokkot fog újra és újra végrehajtani anélkül, hogy onnan valaha tovább tudna menni. Ha persze a cikluson belül valamilyen memóriafoglalás is történik, akkor OutOfMemoryError-ra fog futni a programod. Ezen szerkezetek használatakor mindig különös figyelemmel kell eljárnod.
Ha szeretnéd gyakorolni a rekurziót további Java példákon keresztül, akkor ajánlom figyelmedbe a CodingBat oldalt, ahol több apró példán keresztül elsajátíthatod ennek fortélyait.