Ez a mélyreható oktatóanyag a rekurzióról Java-ban elmagyarázza, mi az a rekurzió példákkal, típusokkal és kapcsolódó fogalmakkal. A rekurzió kontra ismétlés fogalmakkal is foglalkozik:
A korábbi Java oktatóanyagainkból már láttuk az iteratív megközelítést, amelyben kijelölünk egy hurkot, majd iteratív módon végigmegyünk egy adatstruktúrán, és egyszerre egy elemet veszünk.
Láttuk a feltételes áramlást is, ahol ismét megtartunk egy ciklusváltozót, és addig ismételjük a kódot, amíg a ciklusváltozó nem teljesíti a feltételt. Amikor függvényhívásokról van szó, a függvényhívások iteratív megközelítését is feltártuk.
Ebben a bemutatóban a programozás egy másik megközelítését, a rekurzív megközelítést fogjuk tárgyalni.
Mi az a rekurzió Java-ban?
A rekurzió egy olyan folyamat, amelynek során egy függvény vagy egy módszer újra és újra meghívja önmagát. Ezt a közvetlenül vagy közvetve újra és újra meghívott függvényt "rekurzív függvénynek" nevezzük.
A rekurzió megértéséhez különböző példákat fogunk látni. Most nézzük meg a rekurzió szintaxisát.
Rekurzió szintaxis
Minden rekurziót megvalósító metódusnak két alapvető része van:
- Módszerhívás, amely önmagát hívhatja, azaz rekurzív
- Előfeltétel, amely megállítja a rekurziót.
Vegyük észre, hogy minden rekurzív metódushoz szükséges egy előfeltétel, mivel ha nem szakítjuk meg a rekurziót, akkor az a végtelenségig fog futni, és a verem túlcsordulását eredményezi.
A rekurzió általános szintaxisa a következő:
methodName (T paraméterek...) { if (előfeltétel == true) //előfeltétel vagy alapfeltétel { return result; } return methodName (T paraméterek...); //rekurzív hívás } Megjegyezzük, hogy az előfeltételt alapfeltételnek is nevezik. Az alapfeltételről a következő szakaszban lesz szó bővebben.
Rekurzió megértése Java-ban
Ebben a részben megpróbáljuk megérteni a rekurzió folyamatát, és megnézzük, hogyan zajlik. Megismerjük az alapfeltételt, a verem túlcsordulását, és megnézzük, hogyan oldható meg egy adott probléma rekurzióval és más hasonló részletekkel.
Rekurzió alapfeltétel
A rekurzív program megírásakor először az alapeset megoldását kell megadnunk. Ezután a nagyobb problémát kisebb problémák formájában fejezzük ki.
Mint egy példa, vehetünk egy klasszikus problémát, egy szám faktoriálisának kiszámítását. Adott egy n szám, meg kell találnunk az n faktoriálisát, amelyet n-vel jelölünk!
Most valósítsuk meg a programot az n faktoriális (n!) kiszámítására rekurzióval.
public class Main{ static int fact(int n) { if (n == 1) // alapfeltétel return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Kimenet
Ebben a programban láthatjuk, hogy a feltétel (n<=1) az alapfeltétel, és ha ez a feltétel teljesül, a függvény 1-t ad vissza. A függvény else része a rekurzív hívás. De minden alkalommal, amikor a rekurzív módszer meghívásra kerül, n 1-gyel csökken.
Ebből arra következtethetünk, hogy végül az n értéke 1 lesz, vagy kisebb, mint 1, és ekkor a módszer 1 értéket fog visszaadni. Ez az alapfeltétel elérkezik, és a függvény leáll. Megjegyezzük, hogy az n értéke bármi lehet, amíg kielégíti az alapfeltételt.
Problémamegoldás rekurzióval
A rekurzió használatának alapgondolata, hogy a nagyobb problémát kisebb problémák formájában fejezzük ki. Emellett egy vagy több alapfeltételt is hozzá kell adnunk, hogy kiléphessünk a rekurzióból.
Ezt már a fenti faktoriális példában is bemutattuk. Ebben a programban az n faktoriálist (n!) kisebb értékekkel fejeztük ki, és volt egy alapfeltételünk (n <=1), hogy amikor n eléri az 1-et, kiléphessünk a rekurzív módszerből.
Stack Overflow hiba rekurzióban
Tudjuk, hogy bármely metódus vagy függvény hívásakor a függvény állapota a veremben tárolódik, és a függvény visszatérésekor visszakereshető. A veremet a rekurzív módszer is használja.
A rekurzió esetében azonban probléma léphet fel, ha nem definiáljuk az alapfeltételt, vagy ha az alapfeltétel valahogy nem érhető el, illetve nem hajtódik végre. Ha ez a helyzet bekövetkezik, akkor a verem túlcsordulása léphet fel.
Nézzük az alábbi példát a faktoriális jelölésre.
Itt rossz alapfeltételt adtunk meg, n==100.
public class Main { static int fact(int n) { if (n == 100) // stack túlcsordulást eredményező alapfeltétel return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } } Tehát amikor n> 100, a módszer 1-et ad vissza, de a rekurzió nem áll meg. Az n értéke a végtelenségig csökken, mivel nincs más feltétel, ami megállítaná. Ez addig fog tartani, amíg a verem túlcsordul.
Egy másik eset az lesz, amikor az n értéke <100. Ebben az esetben is a módszer soha nem hajtja végre az alapfeltételt, és stack túlcsordulást eredményez.
Rekurzió példák Java-ban
Ebben a szakaszban a következő példákat rekurzióval fogjuk megvalósítani.
#1) Fibonacci-sorozat rekurzió segítségével
A Fibonacci-sorozat a következő,
1,1,2,3,5,8,13,21,34,55,…
A fenti sorozat azt mutatja, hogy az aktuális elem az előző két elem összege. A Fibonacci-sorozat első eleme is 1.
Tehát általánosságban, ha n az aktuális szám, akkor az (n-1) és (n-2) összegéből adódik. Mivel az aktuális elemet az előző elemekkel fejezzük ki, ezt a problémát rekurzióval fejezhetjük ki.
A Fibonacci-sorozatot megvalósító program az alábbiakban található:
public class Main { //módszer a fibonacci-sorozat kiszámítására static int fibonacci(int n) { if (n <= 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //a fibonacci-sorozat első 10 számának kiírása System.out.println ("Fibonacci-sorozat: Első 10 szám:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Kimenet
#2) Ellenőrizze, hogy egy szám palindrom-e rekurzió segítségével
A palindrom olyan sorozat, amely balról jobbra vagy jobbról balra olvasva egyenlő.
Adott egy 121-es szám, és azt látjuk, hogy ha balról jobbra és jobbról balra olvassuk, akkor egyenlő. A 121-es szám tehát palindrom.
Vegyünk egy másik számot, az 1242-t. Ha balról jobbra olvassuk, akkor 1242, ha pedig jobbról balra, akkor 2421. Ez tehát nem palindróma.
A palindrom programot a számok számjegyeinek felcserélésével valósítjuk meg, és rekurzív módon összehasonlítjuk az adott számot a felcserélt ábrázolásával.
Az alábbi program a palindróma ellenőrzésére szolgáló programot valósítja meg.
import java.io.*; import java.util.*; public class Main { // ellenőrzi, hogy a szám csak egy számjegyet tartalmaz-e public static int oneDigit(int szám) { if ((szám>= 0) && (szám <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int szám, int revNum) throws Exception { // alapfeltétel; return if szám=0 if (szám == 0) { return revNum; } else { //callsegédfunkció rekurzív revNum = isPalindrome_util(num / 10, revNum); } // Ellenőrizzük, hogy num és revNum első számjegye megegyezik-e if (num % 10 == revNum % 10) { // ha igen, revNum együtt mozog num-al return revNum / 10; } else { // exit throw new Exception(); } } } // módszer annak ellenőrzésére, hogy egy adott szám palindrom-e a palindrom segédfunkció segítségével public static int isPalindrome(int num) throwsException { if (num <0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Igen, az adott szám " + n + " palindróma."); } catch (Exception e) { System.out.println("Nem, az adott szám " + n + " nem palindróma."); } n = 1221; try { isPalindrome(n);System.out.println("Igen, az adott szám " + n + " palindróma."); } catch (Exception e) { System.out.println("Nem, az adott szám " + n + " nem palindróma."); } } } } Kimenet
#3) Fordított string rekurzió Java
Adott egy "Hello" karakterlánc, amit meg kell fordítanunk, hogy az eredmény "olleH" legyen.
Ezt rekurzióval végezzük: a karakterlánc utolsó karakterétől kezdve rekurzívan kiírunk minden egyes karaktert, amíg a karakterlánc összes karaktere ki nem merül.
Az alábbi program rekurziót használ egy adott karakterlánc visszafordítására.
class String_Reverse { //rekurzív módszer egy adott karakterlánc visszafordítására void reverseString(String str) { //alapfeltétel; visszatér, ha a karakterlánc nulla vagy 1 vagy kevesebb karaktert tartalmaz if ((str==null)} } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Az adott karakterlánc: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("A visszafordított karakterlánc: "); obj.reverseString(inputstr); } } } Kimenet
#4) Bináris keresés Java rekurzió
A bináris keresési algoritmus egy híres keresési algoritmus. Ebben az algoritmusban egy n elemű, rendezett tömböt adva, ezt a tömböt keressük a megadott kulcselem után. Kezdetben a tömböt két félre osztjuk a tömb középső elemének megtalálásával.
Ezután attól függően, hogy a kulcs közepén van-e, a tömb első vagy második felében korlátozzuk a keresést. Így ugyanezt a folyamatot addig ismételjük, amíg a kulcselemek helyét meg nem találjuk.
Ezt az algoritmust itt rekurzióval fogjuk megvalósítani.
import java.util.*; class Binary_Search { // rekurzív bináris keresés int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { // kiszámítjuk a tömb közepét int mid = left + (right - left) / 2; // ha a kulcs a közepén van, akkor visszaadjuk a közepét if (numArray[mid] == key) return mid; // ha kulcs key) return binarySearch(numArray, left, mid - 1, key); // Máskülönben rekurzív keresés a tömbbenjobb oldali altömb return binarySearch(numArray, mid + 1, right, key); } // nincs elem a tömbben, return -1 return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("Az adott tömb : " + Arrays.toString(numArray)); int len = numArray.length; //a tömb hossza.int key = 16; //a keresendő kulcs int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " nincs jelen"); else System.out.println("Element " + key + " found at index " + result); } } } Kimenet
#5) Keresse meg a minimális értéket a tömbben rekurzió segítségével
A rekurzió segítségével a tömb minimális értékét is meg tudjuk találni.
A tömb minimális értékének megtalálására szolgáló Java program az alábbiakban látható.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //visszaadja az első elemet, ha csak egy elem vagy a tömb elemeinek minimuma return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Adott tömb : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("A tömb minimális eleme: " + getMin(numArray, 0, n) + "\n"); } } } Kimenet
Ez néhány példa a rekurzióra. Ezeken a példákon kívül számos más szoftveres probléma is megvalósítható rekurzív technikákkal.
Rekurziós típusok
A rekurziónak két típusa van aszerint, hogy mikor történik a rekurzív metódus hívása.
Ezek a következők:
#1) Farok rekurzió
Ha a rekurzív metódus hívása az utolsó utasítás, amelyet a rekurzív metóduson belül végrehajtanak, akkor ezt "Tail Recursion"-nak nevezzük.
A farokrekurzióban a rekurzív hívó utasítás általában a metódus visszatérési utasításával együtt kerül végrehajtásra.
A farok rekurzió általános szintaxisát az alábbiakban adjuk meg:
methodName ( T parameters...){ { if (base_condition == true) { return result; } return methodName (T parameters ...) //tail rekurzió } #2) Fej rekurzió
A fej rekurzió minden olyan rekurzív megközelítés, amely nem farok rekurzió. Tehát még az általános rekurzió is előre rekurzió.
A fej rekurzió szintaxisa a következő:
methodName (T parameters...){ if (some_condition == true) { return methodName (T parameters...); } return result; } Rekurzió Vs Iteráció Java-ban
| Rekurzió | Iteráció |
|---|---|
| A rekurzió egy olyan folyamat, amikor egy metódus ismételten meghívja önmagát, amíg egy alapfeltétel nem teljesül. | Az ismétlés olyan folyamat, amelynek során egy kódrészletet véges számú alkalommal vagy egy feltétel teljesüléséig ismételten végrehajtunk. |
| Az alkalmazás a funkciók. | Hurokra alkalmazható. |
| Jól működik kisebb kódméret esetén. | Jól működik nagyobb kódméret esetén. |
| Több memóriát használ, mivel minden egyes rekurzív hívás a veremre kerül. | Viszonylag kevesebb memóriát használ. |
| Nehéz hibakeresés és karbantartás | Könnyebb hibakeresés és karbantartás |
| A verem túlcsordulását eredményezi, ha az alapfeltétel nincs megadva vagy nem érhető el. | Végtelenül végigfuttatható, de végül leállítja a végrehajtást bármilyen memóriahiba esetén. |
| Az időbeli összetettség nagyon magas. | Az időigény viszonylag alacsony. |
Gyakran ismételt kérdések
K #1) Hogyan működik a rekurzió Java-ban?
Válasz: A rekurzióban a rekurzív függvény ismételten meghívja önmagát, amíg egy alapfeltétel nem teljesül. A meghívott függvény memóriája a hívó függvény memóriájának tetejére kerül a veremre. Minden egyes függvényhívásnál külön másolat készül a helyi változókról.
Q #2) Miért használják a rekurziót?
Válasz: A rekurziót olyan problémák megoldására használják, amelyek kisebbekre bonthatók, és a teljes probléma egy kisebb probléma formájában fejezhető ki.
A rekurziót olyan problémáknál is használják, amelyek túl bonyolultak ahhoz, hogy iteratív megközelítéssel megoldhatóak legyenek. Azokon a problémákon kívül, amelyeknél az időbonyolultság nem jelent problémát, használjuk a rekurziót.
Q #3) Milyen előnyei vannak a rekurziónak?
Válasz:
A rekurzió előnyei a következők:
- A rekurzió csökkenti a függvények felesleges hívását.
- A rekurzió lehetővé teszi, hogy az iteratív megközelítéshez képest könnyen megoldjuk a problémákat.
Q #4) Melyik a jobb - a rekurzió vagy az ismétlés?
Válasz: A rekurzió ismételt hívásokat végez, amíg el nem éri az alapfüggvényt. Így memóriaterheléssel jár, mivel minden egyes függvényhíváshoz egy memória kerül a veremre.
Az iterációnak viszont nincs nagy memóriaterhelése. A rekurzív végrehajtás lassabb, mint az iteratív megközelítés. A rekurzió csökkenti a kód méretét, míg az iteratív megközelítés a kódot nagyméretűvé teszi.
Q #5) Milyen előnyei vannak a rekurziónak az ismétléssel szemben?
Válasz:
- A rekurzió egyértelműbbé és rövidebbé teszi a kódot.
- A rekurzió jobb, mint az iteratív megközelítés az olyan problémáknál, mint a Hanoi tornya, a fák átjárása stb.
- Mivel minden függvényhívás memóriát tol a veremre, a rekurzió több memóriát használ.
- A rekurziós teljesítmény lassabb, mint az iteratív megközelítés.
Következtetés
A rekurzió nagyon fontos fogalom a szoftverekben, függetlenül a programozási nyelvtől. A rekurziót leginkább olyan adatszerkezeti problémák megoldására használják, mint a Hanoi-tornyok, faátjárások, összekapcsolt listák stb. Bár több memóriát igényel, a rekurzió egyszerűbbé és világosabbá teszi a kódot.
Ebben az oktatóanyagban mindent feltártunk a rekurzióról, és számos programozási példát is megvalósítottunk a koncepció jobb megértése érdekében.