Rekursion ist der Prozess, etwas in Bezug auf zu definierenselbst. In Bezug auf die Java-Programmierung ist Rekursion das Attribut, mit dem sich eine Methode selbst aufrufen kann. Eine Methode, die sich selbst aufruft, wird als rekursiv bezeichnet, und Java unterstützt die Rekursion.
Auf den ersten Blick mag dies wie eine Endlosschleife erscheinen.und es scheint, dass unsere Methode niemals enden wird. Dies mag in einigen Fällen zutreffen, aber in der Praxis können wir überprüfen, ob eine bestimmte Bedingung erfüllt ist, und in diesem Fall unsere Methode beenden (von ihr zurückkehren). Der Fall, in dem wir unsere Rekursion beenden, heißt a Basisfall. Außerdem müssen wir wie in einer Schleife einen Wert ändern und schrittweise näher an unseren Basisfall heranrücken.
Jede Rekursion sollte die folgenden Merkmale aufweisen:
- Ein einfacher Basisfall, für den wir eine Lösung und einen Rückgabewert haben.
- Eine Möglichkeit, unser Problem dem Basisfall näher zu bringen. d.h. eine Möglichkeit, einen Teil des Problems herauszuschneiden, um ein etwas einfacheres Problem zu erhalten.
- Ein rekursiver Aufruf, der das einfachere Problem an die Methode zurückgibt.
Vorteile
Die wichtigsten rekursiven Methoden sind, dass sie sein könnenwird verwendet, um klarere und einfachere Versionen mehrerer Algorithmen zu erstellen als ihre iterativen Verwandten. Beispielsweise ist es schwierig, den QuickSort-Sortieralgorithmus iterativ zu implementieren.
Nachteile
Rekursive Versionen vieler Routinen können a ausführenetwas langsamer als das iterative Äquivalent aufgrund des zusätzlichen Overheads der zusätzlichen Funktionsaufrufe. Viele rekursive Aufrufe einer Methode können zu einem Stapelüberlauf führen. Aufgrund der Speicherung von Parametern und lokalen Variablen ist es möglich, dass der Stapel erschöpft ist. In diesem Fall verursacht das Java-Laufzeitsystem eine Ausnahme. Sie müssen sich jedoch wahrscheinlich keine Sorgen machen, es sei denn, eine rekursive Routine läuft wild.
Zum Beispiel:
int myFactorial(int integer) {
if( integer == 1) {
return 1;
}
else {
return(integer*(myFactorial(integer-1);
}
}Schwanzrekursion wird definiert als auftritt, wenn dieDer rekursive Aufruf befindet sich am Ende der rekursiven Anweisung. Dies ist bei meiner oben genannten faktoriellen Lösung nicht der Fall. Es ist nützlich zu bemerken, wenn ein Algorithmus die Schwanzrekursion verwendet, da in einem solchen Fall der Algorithmus normalerweise neu geschrieben werden kann, um stattdessen die Iteration zu verwenden. Tatsächlich konvertiert (oder sollte) der Compiler das rekursive Programm in ein iteratives. Dies beseitigt das potenzielle Problem des Stapelüberlaufs.
Dies ist bei der Kopfrekursion nicht der Fall oder wennDie Funktion ruft sich rekursiv an verschiedenen Stellen auf, wie in der Towers of Hanoi-Lösung. Selbst in diesen Fällen könnten wir natürlich auch die Rekursion entfernen, indem wir unseren eigenen Stapel verwenden und im Wesentlichen simulieren, wie die Rekursion funktionieren würde.
In meinem Beispiel von Fakultät über dem Compilermuss die rekursive Funktion aufrufen, bevor die Multiplikation durchgeführt wird, da sie den (Rückgabe-) Wert der Funktion auflösen muss, bevor sie die Multiplikation abschließen kann. Die Ausführungsreihenfolge ist also "Kopf" -Rekursion, d. H. Die Rekursion erfolgt vor anderen Operationen.
Um dies in eine Schwanzrekursion umzuwandeln, müssen wir bekommenDie gesamte Multiplikation wurde beendet und aufgelöst, bevor die Funktion rekursiv aufgerufen wurde. Wir müssen die Reihenfolge der Operation erzwingen, damit wir nicht auf die Multiplikation warten, bevor wir zurückkehren. Wenn wir dies tun, kann der Stapelrahmen freigegeben werden.
Zuvor haben Sie unser Java-Programm zur Berechnung der Fakultät einer Ganzzahl gesehen.
Der richtige Weg, um eine schwanzrekursive Fakultät zu erstellen, ist folgender:
int factorial(int number) {
if(number == 0) {
return 1;
}
factorial_i(number, 1);
}
int factorial_i(int currentNumber, int sum) {
if(currentNumber == 1) {
return sum;
} else {
return factorial_i(currentNumber - 1, sum*currentNumber);
}
}Beachten Sie, dass in der Anrufrückgabefactorial_i (currentNumber - 1, sum * currentNumber); Beide Parameter sind sofort auflösbar. Wir können berechnen, was jeder Parameter ist, ohne auf die Rückkehr eines rekursiven Funktionsaufrufs zu warten. Dies ist bei der vorherigen Version von Fakultät nicht der Fall. Diese Rationalisierung ermöglicht es dem Compiler, die Stapelverwendung wie oben erläutert zu minimieren.
Sie können die Nummer auch vom Benutzer als Befehlszeilenargument verwenden.
Java-Rekursionsprogramm
class Factorial{
int fact(int n){
int result;
if ( n ==1)
return 1;
result = fact (n-1) * n;
return result;
}
}
class Recursion{
public static void main (String args[]){
Factorial f =new Factorial();
System.out.println("Factorial of 3 is " + f.fact(3));
System.out.println("Factorial of 4 is " + f.fact(4));
System.out.println("Factorial of 5 is " + f.fact(5));
}
}Ausgabe
Erläuterung des Java-Codes und der Ausgabe
Wenn Sie mit rekursiven Methoden nicht vertraut sind, dann ist die Operation von Tatsache() mag etwas verwirrend erscheinen. So funktioniert es. Wann Tatsache() wird mit dem Argument 1 aufgerufen, die Funktion gibt 1 zurück; Andernfalls wird das Produkt von zurückgegeben Tatsache (n-1) * n. um diesen Ausdruck zu bewerten, Tatsache() heißt mit n-1. Dieser Vorgang wiederholt sich bis n gleich 1 und die Aufrufe der Methode kehren zurück.
Um besser zu verstehen, wie die Tatsache() Methode funktioniert, lassen Sie uns ein kurzes Beispiel durchgehen. Wenn Sie die Fakultät 3 berechnen, wird der erste Aufruf an Tatsache() wird einen zweiten Aufruf mit einem Argument von 2 veranlassen. Dieser Aufruf wird verursachen Tatsache() ein drittes Mal mit einem Argument von 2 genannt werden. Dieser Aufruf gibt 1 zurück, das dann ein drittes Mal mit dem Argument 1 aufgerufen wird. Dieser Aufruf gibt 1 zurück, das dann mit 2 multipliziert wird (der Wert von n im zweiten Aufruf). Dieses Ergebnis (das 2 ist) wird dann zum ursprünglichen Aufruf von zurückgegeben Tatsache() und multipliziere mit 3 (der ursprüngliche Wert von n). Dies ergibt die Antwort 6. Das Einfügen könnte interessant sein println () Aussagen in Tatsache() Dies zeigt, auf welcher Ebene sich jeder Anruf befindet und welche Zwischenantworten vorliegen.
Wenn sich eine Methode selbst aufruft, werden neue lokale Variablen erstelltund Parametern wird Speicher auf dem Stapel zugewiesen, und der Methodencode wird von Anfang an mit diesen neuen Variablen ausgeführt. Ein rekursiver Aufruf erstellt keine neue Kopie der Methode. Nur die Argumente sind neu. Bei jeder Rückkehr eines rekursiven Aufrufs werden die alten lokalen Variablen und Parameter aus dem Stapel entfernt, und die Ausführung wird am Punkt des Aufrufs innerhalb der Methode fortgesetzt.
Als nächstes werden wir lernen, wie man damit umgeht Array in Java.
Weitere nützliche Tutorials und definitive Richtlinien zur Java-Programmierung finden Sie hier.
Bemerkungen