Dieses ausführliche Tutorial über Rekursion in Java erklärt, was Rekursion mit Beispielen, Typen und verwandten Konzepten ist und behandelt auch Rekursion im Vergleich zu Iteration:
In unseren früheren Java-Tutorials haben wir den iterativen Ansatz kennen gelernt, bei dem wir eine Schleife deklarieren und dann eine Datenstruktur iterativ durchlaufen, indem wir ein Element nach dem anderen nehmen.
Wir haben auch den bedingten Ablauf gesehen, bei dem wir wieder eine Schleifenvariable behalten und ein Stück Code wiederholen, bis die Schleifenvariable die Bedingung erfüllt. Bei Funktionsaufrufen haben wir auch den iterativen Ansatz für Funktionsaufrufe untersucht.
In diesem Tutorium werden wir einen anderen Ansatz zur Programmierung diskutieren, nämlich den rekursiven Ansatz.
Was ist Rekursion in Java?
Rekursion ist ein Prozess, bei dem eine Funktion oder eine Methode sich selbst immer wieder aufruft. Diese Funktion, die entweder direkt oder indirekt immer wieder aufgerufen wird, nennt man "rekursive Funktion".
Wir werden verschiedene Beispiele sehen, um die Rekursion zu verstehen. Nun wollen wir uns die Syntax der Rekursion ansehen.
Rekursionssyntax
Jede Methode, die Rekursion implementiert, hat zwei grundlegende Teile:
- Methodenaufruf, der sich selbst aufrufen kann, d.h. rekursiv
- Eine Vorbedingung, die die Rekursion stoppt.
Beachten Sie, dass eine Vorbedingung für jede rekursive Methode notwendig ist, denn wenn wir die Rekursion nicht unterbrechen, wird sie unendlich weiterlaufen und zu einem Stapelüberlauf führen.
Die allgemeine Syntax der Rekursion lautet wie folgt:
methodName (T parameters...) { if (precondition == true) //Vorbedingung oder Basisbedingung { return result; } return methodName (T parameters...); //rekursiver Aufruf } Beachten Sie, dass die Vorbedingung auch als Grundbedingung bezeichnet wird. Wir werden im nächsten Abschnitt mehr über die Grundbedingung erfahren.
Verständnis der Rekursion in Java
In diesem Abschnitt werden wir versuchen, den Rekursionsprozess zu verstehen und zu sehen, wie er abläuft. Wir werden etwas über die Basisbedingung und den Stapelüberlauf lernen und sehen, wie ein bestimmtes Problem mit Rekursion und anderen solchen Details gelöst werden kann.
Rekursion Basisbedingung
Wenn wir ein rekursives Programm schreiben, sollten wir zunächst die Lösung für den Basisfall angeben und dann das größere Problem in Form von kleineren Problemen ausdrücken.
Als ein Beispiel, können wir ein klassisches Problem der Berechnung der Fakultät einer Zahl nehmen: Bei einer Zahl n müssen wir eine Fakultät von n finden, die mit n!
Nun wollen wir das Programm zur Berechnung der n-Faktoriellen (n!) mittels Rekursion implementieren.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } Ausgabe
In diesem Programm sehen wir, dass die Bedingung (n<=1) die Basisbedingung ist, und wenn diese Bedingung erreicht ist, gibt die Funktion 1 zurück. Der else-Teil der Funktion ist der rekursive Aufruf. Aber jedes Mal, wenn die rekursive Methode aufgerufen wird, wird n um 1 dekrementiert.
Daraus können wir schließen, dass der Wert von n schließlich 1 oder kleiner als 1 wird, und an diesem Punkt wird die Methode den Wert 1 zurückgeben. Diese Basisbedingung wird erreicht und die Funktion wird beendet. Beachten Sie, dass der Wert von n alles sein kann, solange er die Basisbedingung erfüllt.
Problemlösung mit Rekursion
Der Grundgedanke der Rekursion besteht darin, ein größeres Problem in Form kleinerer Probleme auszudrücken. Außerdem müssen wir eine oder mehrere Basisbedingungen hinzufügen, damit wir aus der Rekursion herauskommen können.
In diesem Programm haben wir die n-Faktorielle (n!) in Form kleinerer Werte ausgedrückt und eine Basisbedingung (n <=1) festgelegt, so dass wir die rekursive Methode beenden können, wenn n 1 erreicht.
Stack Overflow Fehler in Rekursion
Wir wissen, dass beim Aufruf einer Methode oder Funktion der Zustand der Funktion auf dem Stack gespeichert und bei der Rückkehr der Funktion wieder abgerufen wird. Der Stack wird auch für die rekursive Methode verwendet.
Im Falle einer Rekursion kann jedoch ein Problem auftreten, wenn wir die Basisbedingung nicht definieren oder wenn die Basisbedingung irgendwie nicht erreicht oder ausgeführt wird. In diesem Fall kann es zu einem Stapelüberlauf kommen.
Betrachten wir das folgende Beispiel der faktoriellen Notation.
Hier haben wir eine falsche Grundbedingung angegeben, n==100.
public class Main { static int fact(int n) { if (n == 100) // Grundbedingung, die zu einem Stapelüberlauf führt return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } } Wenn also n> 100 ist, gibt die Methode 1 zurück, aber die Rekursion hört nicht auf. Der Wert von n wird unendlich weiter dekrementiert, da es keine andere Bedingung gibt, um es zu stoppen. Das geht so weiter, bis der Stack überläuft.
Ein anderer Fall ist, wenn der Wert von n <100. Auch in diesem Fall wird die Methode nie die Basisbedingung ausführen und zu einem Stapelüberlauf führen.
Rekursionsbeispiele in Java
In diesem Abschnitt werden wir die folgenden Beispiele mit Hilfe der Rekursion umsetzen.
#1) Fibonacci-Reihen mit Rekursion
Die Fibonacci-Reihe ist gegeben durch,
1,1,2,3,5,8,13,21,34,55,…
Die obige Folge zeigt, dass das aktuelle Element die Summe der beiden vorhergehenden Elemente ist und dass das erste Element der Fibonacci-Reihe 1 ist.
Wenn also n die aktuelle Zahl ist, dann ist sie im Allgemeinen durch die Summe von (n-1) und (n-2) gegeben. Da das aktuelle Element in Form der vorherigen Elemente ausgedrückt wird, können wir dieses Problem durch Rekursion ausdrücken.
Das Programm zur Implementierung der Fibonacci-Reihe ist unten angegeben:
public class Main { //Methode zur Berechnung der Fibonacci-Reihe 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; //Drucke die ersten 10 Zahlen der Fibonacci-Reihe System.out.println ("Fibonacci-Reihe: Erste 10 Zahlen:"); for (int i = 1; i <= number; i++) { System.out.print(fibonacci(i) + " ");} } } Ausgabe
#2) Prüfen, ob eine Zahl ein Palindrom ist, mit Rekursion
Ein Palindrom ist eine Folge, die gleich ist, wenn man sie von links nach rechts oder von rechts nach links liest.
Wenn wir die Zahl 121 von links nach rechts und von rechts nach links lesen, ist sie gleich, also ist die Zahl 121 ein Palindrom.
Nehmen wir eine andere Zahl, 1242. Wenn wir sie von links nach rechts lesen, ist sie 1242, und wenn wir sie von rechts nach links lesen, ist sie 2421. Es handelt sich also nicht um ein Palindrom.
Wir implementieren das Palindrom-Programm, indem wir die Ziffern von Zahlen umkehren und die gegebene Zahl rekursiv mit ihrer umgekehrten Darstellung vergleichen.
Das folgende Programm implementiert das Programm zur Überprüfung des Palindroms.
import java.io.*; import java.util.*; public class Main { // prüfen, ob num nur eine Ziffer enthält public static int oneDigit(int num) { if ((num>= 0) && (num <10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // Basisbedingung; return if num=0 if (num == 0) { return revNum; } else { //aufrufenUtility-Funktion rekursiv revNum = isPalindrome_util(num / 10, revNum); } // Prüfen, ob die erste Ziffer von num und revNum gleich ist if (num % 10 == revNum % 10) { // wenn ja, wandert revNum mit num return revNum / 10; } else { // exit throw new Exception(); } } } //Methode zur Prüfung, ob eine gegebene Zahl ein Palindrom ist, unter Verwendung der Palindrom-Utility-Funktion 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("Ja, die angegebene Zahl " + n + " ist ein Palindrom."); } catch (Exception e) { System.out.println("Nein, die angegebene Zahl " + n + " ist kein Palindrom."); } n = 1221; try { isPalindrome(n);System.out.println("Ja, die gegebene Zahl " + n + " ist ein Palindrom."); } catch (Exception e) { System.out.println("Nein, die gegebene Zahl " + n + " ist kein Palindrom."); } } } Ausgabe
#3) Umgekehrte String-Rekursion Java
Bei einer Zeichenkette "Hallo" müssen wir sie umkehren, so dass die resultierende Zeichenkette "olleH" ist.
Dies geschieht durch Rekursion: Beginnend mit dem letzten Zeichen in der Zeichenkette wird jedes Zeichen rekursiv gedruckt, bis alle Zeichen in der Zeichenkette aufgebraucht sind.
Das folgende Programm verwendet eine Rekursion, um eine gegebene Zeichenkette umzukehren.
class String_Reverse { //rekursive Methode zur Umkehrung einer gegebenen Zeichenkette void reverseString(String str) { //Basisbedingung; Rückgabe, wenn string null oder mit 1 oder weniger Zeichen ist if ((str==null)} } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("Der gegebene String: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("Der umgekehrte String: "); obj.reverseString(inputstr); } } Ausgabe
#4) Binäre Suche Java Rekursion
Ein binärer Suchalgorithmus ist ein berühmter Suchalgorithmus. Bei diesem Algorithmus wird in einem sortierten Array mit n Elementen nach dem angegebenen Schlüsselelement gesucht. Zu Beginn wird das Array in zwei Hälften geteilt, indem das mittlere Element des Arrays gefunden wird.
Je nachdem, ob der Schlüssel in der Mitte liegt, schränken wir die Suche auf die erste oder zweite Hälfte des Arrays ein und wiederholen den Vorgang so lange, bis wir die Schlüsselelemente gefunden haben.
Wir werden diesen Algorithmus hier mit Hilfe von Rekursion implementieren.
import java.util.*; class Binary_Search { // Rekursive binäre Suche int binarySearch(int numArray[], int left, int right, int key) { if (right>= left) { // Berechne Mitte des Arrays int mid = left + (right - left) / 2; // wenn der Schlüssel in der Mitte liegt, gib mid zurück if (numArray[mid] == key) return mid; // wenn Schlüssel key) return binarySearch(numArray, left, mid - 1, key); // Sonst rekursive Suche imrechtes Subarray return binarySearch(numArray, mid + 1, right, key); } // keine Elemente im Array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //Array deklarieren und drucken int numArray[] = { 4,6,12,16,22}; System.out.println("Das gegebene Array : " + Arrays.toString(numArray)); int len = numArray.length; //Länge des Arraysint key = 16; //zu suchender Schlüssel int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " nicht vorhanden"); else System.out.println("Element " + key + " gefunden bei Index " + result); } } Ausgabe
#5) Minimalwert in Array mit Rekursion finden
Mit Hilfe der Rekursion können wir auch den kleinsten Wert in der Matrix finden.
Das Java-Programm zur Ermittlung des Mindestwerts im Array ist unten angegeben.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //Rückgabe des ersten Elements, wenn nur ein Element oder das Minimum der Arrayelemente 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("Gegebenes Array : " + Arrays.toString(numArray)); int n =numArray.length; System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); } Ausgabe
Abgesehen von diesen Beispielen können viele andere Probleme in der Software mit rekursiven Techniken implementiert werden.
Rekursionstypen
Es gibt zwei Arten von Rekursionen, je nachdem, wann der Aufruf der rekursiven Methode erfolgt.
Sie sind:
#1) Schwanzrekursion
Wenn der Aufruf der rekursiven Methode die letzte Anweisung ist, die innerhalb der rekursiven Methode ausgeführt wird, nennt man dies "Tail Recursion".
Bei der Tail-Rekursion wird die rekursive Aufrufanweisung normalerweise zusammen mit der Return-Anweisung der Methode ausgeführt.
Die allgemeine Syntax für die Tail-Rekursion ist unten angegeben:
methodName ( T Parameter ...){ { if (base_condition == true) { return result; } return methodName (T Parameter ...) //tail recursion } #2) Kopf-Rekursion
Eine Kopfrekursion ist jeder rekursive Ansatz, der keine Schwanzrekursion ist, also auch eine allgemeine Rekursion ist eine Kopfrekursion.
Die Syntax der Kopfrekursion lautet wie folgt:
methodName (T Parameter...){ if (some_condition == true) { return methodName (T Parameter...); } return result; } Rekursion vs. Iteration in Java
| Rekursion | Iteration |
|---|---|
| Rekursion ist ein Prozess, bei dem eine Methode sich selbst wiederholt aufruft, bis eine Grundbedingung erfüllt ist. | Iteration ist ein Prozess, bei dem ein Codestück wiederholt eine endliche Anzahl von Malen ausgeführt wird oder bis eine Bedingung erfüllt ist. |
| Ist die Anwendung für Funktionen. | Gilt für Schleifen. |
| Funktioniert gut bei kleinerer Codegröße. | Funktioniert gut bei größerem Code. |
| Verbraucht mehr Speicher, da jeder rekursive Aufruf auf den Stack geschoben wird | Es wird vergleichsweise wenig Speicherplatz benötigt. |
| Schwierig zu debuggen und zu warten | Leichtere Fehlersuche und Wartung |
| Führt zu einem Stapelüberlauf, wenn die Basisbedingung nicht angegeben oder nicht erreicht wird. | Kann unendlich oft ausgeführt werden, bricht aber bei Speicherfehlern die Ausführung ab. |
| Die Zeitkomplexität ist sehr hoch. | Der zeitliche Aufwand ist relativ gering. |
Häufig gestellte Fragen
F #1) Wie funktioniert die Rekursion in Java?
Antwort: Bei der Rekursion ruft sich die rekursive Funktion so lange selbst auf, bis eine Basisbedingung erfüllt ist. Der Speicher für die aufgerufene Funktion wird auf den Stack am oberen Ende des Speichers für die aufrufende Funktion geschoben. Für jeden Funktionsaufruf wird eine separate Kopie der lokalen Variablen erstellt.
Q #2) Warum wird die Rekursion verwendet?
Antwort: Die Rekursion wird verwendet, um Probleme zu lösen, die in kleinere Probleme zerlegt werden können, und das gesamte Problem kann in Form eines kleineren Problems ausgedrückt werden.
Die Rekursion wird auch für Probleme verwendet, die zu komplex sind, um mit einem iterativen Ansatz gelöst zu werden. Neben den Problemen, bei denen die Zeitkomplexität keine Rolle spielt, wird die Rekursion verwendet.
Q #3) Was sind die Vorteile der Rekursion?
Antwort:
Zu den Vorteilen der Rekursion gehören:
- Die Rekursion reduziert den redundanten Aufruf von Funktionen.
- Die Rekursion ermöglicht es uns, Probleme im Vergleich zum iterativen Ansatz leichter zu lösen.
F #4) Was ist besser - Rekursion oder Iteration?
Antwort: Bei der Rekursion werden die Aufrufe so lange wiederholt, bis die Basisfunktion erreicht ist. Dadurch entsteht ein Speicher-Overhead, da für jeden Funktionsaufruf ein Speicher auf den Stack geschoben wird.
Die Iteration hingegen hat keinen großen Speicher-Overhead. Die Ausführung der Rekursion ist langsamer als der iterative Ansatz. Die Rekursion reduziert die Größe des Codes, während der iterative Ansatz den Code groß macht.
Q #5) Was sind die Vorteile der Rekursion gegenüber der Iteration?
Antwort:
- Die Rekursion macht den Code übersichtlicher und kürzer.
- Die Rekursion ist besser als der iterative Ansatz für Probleme wie den Turm von Hanoi, Baumüberquerungen, usw.
- Da bei jedem Funktionsaufruf Speicher auf den Stack geschoben wird, verbraucht die Rekursion mehr Speicher.
- Die Rekursionsleistung ist langsamer als beim iterativen Ansatz.
Schlussfolgerung
Die Rekursion ist ein sehr wichtiges Konzept in der Software, unabhängig von der Programmiersprache. Die Rekursion wird vor allem bei der Lösung von Datenstrukturproblemen wie den Türmen von Hanoi, Baumüberquerungen, verknüpften Listen usw. verwendet. Obwohl sie mehr Speicherplatz benötigt, macht die Rekursion den Code einfacher und klarer.
In diesem Tutorial haben wir uns mit dem Thema Rekursion beschäftigt und zahlreiche Programmierbeispiele zum besseren Verständnis des Konzepts implementiert.