Beispiel für rekursiven Code ohne Exit-Bedingung
Schauen wir uns noch einmal ein rekursives Problem an. Betrachten Sie als Beispiel die Berechnung von Fibonacci-Zahlen. Jeder wird sich daran erinnern, dass die Fibonacci-Folge eine Zahlenfolge ist, bei der die ersten beiden Zahlen 0 und 1 sind und jede nachfolgende Zahl gleich der Summe der beiden vorherigen Zahlen ist.
Schreiben wir Code, um diese Zahlen zu berechnen und anzuzeigen:
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
printFibonacci(0, 1);
}
private static void printFibonacci(long penultimate, long previous) {
long current = penultimate + previous;
System.out.println(current);
printFibonacci(previous, current);
}
}
Geben Sie vor dem ersten Aufruf der rekursiven Methode printFibonacci die ersten beiden Zahlen der Sequenz aus: Null und Eins. Wir müssen dies tun, da die rekursive Methode nur die Summe der Eingabeparameter anzeigt, nicht die Parameter selbst.
Der Code sieht in Ordnung aus: Wir erhalten zwei Zahlen, berechnen ihre Summe, geben sie auf der Konsole aus und rufen die printFibonacci -Methode erneut rekursiv auf. Als Argumente übergeben wir die vorherige Zahl ( previous ) und die aktuelle Zahl ( current ).
Tatsächlich hat der Code zwei Fehler. Sie können sie sehen, wenn Sie den Code ausführen.
Der erste Fehler ist ein Überlauf des langen Typs. Die 104. Zahl in unserer Folge ist negativ, was darauf hinweist, dass der lange Typ übergelaufen ist.
Der zweite Fehler ist anders. Nach der Berechnung von etwa 12.000 Zahlen erhalten wir:
Jetzt ist es an der Zeit, sich daran zu erinnern, was ein Methodenaufrufstapel in Java ist. Die Java-Maschine zeichnet alle Funktionsaufrufe auf. Zu diesem Zweck wird eine spezielle Art von Sammlung verwendet, die als Stapel bezeichnet wird. Wenn eine Funktion eine andere aufruft, schiebt die Java-Maschine ein neues StackTraceElement auf den Stapel. Wenn die Funktion endet, wird dieses Element vom Stapel entfernt. Dementsprechend speichert der Stack stets aktuelle Informationen über den aktuellen Zustand des Funktionsaufrufstacks. In der Dokumentation für StackTraceElement heißt es, dass es „ausgelöst wird, wenn ein Stapelüberlauf auftritt, weil eine Anwendung zu tief rekursiv ist.“ Eine laufende JVM verfügt über einen speziellen Speicherbereich zum Speichern des Methodenaufrufstapels. Die Größe dieses Speicherbereichs hängt von den Betriebssystem- und JVM-Einstellungen ab. Zusätzlich zum Methodenaufrufstapel selbst, In diesem speziellen Speicherbereich werden primitive Variablen (spezifische Werte von Methodenparametern) und die Adressen von Referenzvariablen (in einem Speicherbereich namens „Heap“) gespeichert. Der Zugriff auf den Aufrufstapel erfolgt nach dem LIFO-Prinzip.
Korrigiertes Beispiel mit einer Exit-Bedingung
Beginnen wir mit der Behebung des zweiten Problems im Code.
Versuchen wir, das Problem direkt zu lösen: Wenn der Stapel zu klein ist, machen wir ihn größer. Starten Sie dazu die JVM mit dem Flag „-Xss“ und geben Sie an, wie viel Speicher für den Stack reserviert werden soll. Versuchen wir, 5 Megabyte zuzuweisen. So wird es in IDEA aussehen:
Es ist uns gelungen, die Länge der Ausgabe zu erhöhen. Jetzt können mehr als 49.000 Zahlen der Folge berechnet werden, anstatt auf etwa 12.000 Zahlen beschränkt zu sein. Aber irgendwann erhalten wir immer noch einen StackOverflowError .
Sie können versuchen, den Stapel zu vergrößern, aber das löst das grundlegende Problem nicht. Suchen wir also nach einem Problem in der Logik. Es muss einen Punkt geben, an dem die Rekursion stoppt. Mit anderen Worten: Es muss eine Bedingung geben, die bestimmt, wann die rekursive Methode nicht mehr aufgerufen wird, sodass der Aufrufstapel abgewickelt werden kann. Um eine solche Bedingung zu definieren, machen wir unser Ziel explizit: Zeigen Sie die Fibonacci-Reihe an, solange ihre Zahlen kleiner als Integer.MAX_VALUE sind .
Schreiben wir eine neue printFibonacciWithCondition- Methode, die diese Bedingung berücksichtigt. Und wir werden die neue korrigierte Methode in der Hauptmethode aufrufen.
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
// printFibonacci(0, 1);
printFibonacciWithCondition(0, 1);
}
private static void printFibonacci(long penultimate, long previous) {
long current = penultimate + previous;
System.out.println(current);
printFibonacci(previous, current);
}
private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
System.out.println(current);
printFibonacciWithCondition(previous, current);
}
}
Nachdem wir den Code ausgeführt haben, sehen wir, dass die Ausgabe mit der Zahl 1836311903 endet. Die Zahl davor ist 1134903170. Die Summe dieser Zahlen ist 2_971_215_073, was tatsächlich größer als Integer.MAX_VALUE (2_147_483_647) ist .
Durch diese Änderung wurde der Fehler beim langen Überlauf automatisch behoben . Wenn Sie einen größeren Teil der Reihe berechnen müssen, müssen Sie andere Datentypen verwenden, z. B. BigInteger .
Rekursiver Abstieg und Abwickeln
Lassen Sie uns Schritt für Schritt analysieren, wie unser Code ausgeführt wird. Dazu fügen wir eine echo- Methode hinzu und rufen sie vor und nach dem rekursiven Aufruf der printFibonacciWithCondition -Methode auf.
public class Fibonacci {
public static void main(String[] args) {
System.out.println(0);
System.out.println(1);
printFibonacciWithCondition(0, 1);
}
private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
echo(true, penultimate, previous);
System.out.println(current);
printFibonacciWithCondition(previous, current);
echo(false, penultimate, previous);
}
private static void echo(boolean isBeforeRecursiveCall, long penultimate, long previous) {
if (isBeforeRecursiveCall) {
System.out.printf("Before method call with args: %d, %d. Current number = ", penultimate, previous);
} else {
System.out.printf("After method call with args: %d, %d\n", penultimate, previous);
}
}
}
Das Programm gibt uns diese Ausgabe:
1
Vor Methodenaufruf mit Argumenten: 0, 1. Aktuelle Nummer = 1
Vor Methodenaufruf mit Argumenten: 1, 1. Aktuelle Nummer = 2
Vor Methodenaufruf mit Argumenten: 1, 2. Aktuelle Nummer = 3
Vor Methodenaufruf mit Argumenten: 2, 3. Aktuelle Nummer = 5
Vor Methodenaufruf mit Argumenten: 3, 5. Aktuelle Nummer = 8
Vor Methodenaufruf mit Argumenten: 5, 8. Aktuelle Nummer = 13
Vor Methodenaufruf mit Argumenten: 8, 13. Aktuelle Nummer = 21
Vor Methodenaufruf mit Argumenten: 13, 21. Aktuelle Nummer = 34
Vor Methodenaufruf mit Argumenten: 21, 34. Aktuelle Nummer = 55
Vor Methodenaufruf mit Argumenten: 34, 55. Aktuelle Nummer = 89
Vor Methodenaufruf mit Argumenten: 55, 89. Aktuelle Zahl = 144
Vor Methodenaufruf mit Argumenten: 89, 144. Aktuelle Nummer = 233
Vor Methodenaufruf mit Argumenten: 144, 233. Aktuelle Nummer = 377
Vor Methodenaufruf mit Argumenten: 233, 377. Aktuelle Nummer = 610
Vor Methodenaufruf mit Argumenten: 377, 610. Aktuelle Nummer = 987
Vor Methodenaufruf mit Argumenten: 610, 987. Aktuelle Nummer = 1597
Vor Methodenaufruf mit Argumenten: 987, 1597. Aktuelle Nummer = 2584
Vor Methodenaufruf mit Argumenten: 1597, 2584. Aktuelle Nummer = 4181
Vor Methode Aufruf mit Argumenten: 2584, 4181. Aktuelle Nummer = 6765
Vor Methodenaufruf mit Argumenten: 4181, 6765. Aktuelle Nummer = 10946
Vor Methodenaufruf mit Argumenten: 6765, 10946. Aktuelle Nummer = 17711
Vor Methodenaufruf mit Argumenten: 10946, 17711. Aktuelle Nummer = 28657
Vor Methodenaufruf mit Argumenten: 17711, 28657. Aktuelle Nummer = 46368
Vor Methodenaufruf mit Argumenten: 28657, 46368. Aktuelle Nummer = 75025
Vor Methodenaufruf mit Argumenten: 46368, 75025. Aktuelle Nummer = 121393
Vor Methodenaufruf mit Argumenten: 75025, 121393. Aktuelle Nummer = 196418
Vor Methodenaufruf mit Argumenten: 121393, 196418. Aktuelle Nummer = 317811
Vor Methodenaufruf mit Argumenten: 196418, 317811. Aktuelle Nummer = 514229
Vor Methodenaufruf mit Argumenten: 317811, 514229. Aktuelle Nummer = 832040
Vor Methode Aufruf mit Argumenten: 514229, 832040. Aktuelle Nummer = 1346269
Vor Methodenaufruf mit Argumenten: 832040, 1346269. Aktuelle Nummer = 2178309
Vor Methodenaufruf mit Argumenten: 1346269, 2178309. Aktuelle Nummer = 3524578
Vor Methodenaufruf mit Argumenten: 2178309, 3524578. Aktuelle Nummer = 5702887
Vor Methodenaufruf mit Argumenten: 3524578, 5702887. Aktuelle Nummer = 9227465
Vor Methodenaufruf mit Argumenten: 5702887, 9227465. Aktuelle Nummer = 14930352
Vor Methodenaufruf mit Argumenten: 92274 65, 14930352. Aktuelle Nummer = 24157817
Vor Methodenaufruf mit Argumenten: 14930352, 24157817. Aktuelle Nummer = 39088169
Vor Methodenaufruf mit Argumenten: 24157817, 39088169. Aktuelle Nummer = 63245986
Vor Methodenaufruf mit Argumenten: 39088169, 6324 5986. Aktuelle Nummer = 102334155
Vor der Methode Aufruf mit Argumenten: 63245986, 102334155. Aktuelle Nummer = 165580141
Vor Methodenaufruf mit Argumenten: 102334155, 165580141. Aktuelle Nummer = 267914296
Vor dem Methodenaufruf mit Argumenten: 165580141, 267914296. Aktuelle Nummer = 433494437
Vor dem Methodenaufruf mit Argumenten: 267914296, 433494437. Aktuelle Nummer = 701408733 Vor dem Methodenaufruf mit Argumenten: 433494437, 701408733. Aktuelle Nummer =
11349 03170
Vor Methodenaufruf mit Argumenten: 701408733, 1134903170. Aktuelle Nummer = 1836311903
Nach Methodenaufruf mit Argumenten: 701408733, 113490317
Nach Methodenaufruf mit Argumenten: 433494437, 701408733 Nach Methodenaufruf mit Argumenten: 267914296, 433494437 Nach
Methodenaufruf mit Argumenten
: 1655 80141, 267914296
Nach Methodenaufruf mit Argumenten: 102334155, 165580141
Nach Methodenaufruf mit Argumenten: 63245986, 102334155
Nach Methodenaufruf mit Argumenten: 39088169, 63245986
Nach Methodenaufruf mit Argumenten: 24157817, 39088169
Nach Methodenaufruf mit Argumenten: 14930352, 24157817
Nach Methodenaufruf mit Argumenten: 9227465, 14930352 Nach Methodenaufruf mit Argumenten: 5702887, 9227465
Nach Methodenaufruf
mit Argumenten: 3524578, 5702 887
Nach Methodenaufruf mit Argumenten : 2178309, 3524578
Nach Methodenaufruf mit Argumenten: 1346269, 2178309
Nach Methodenaufruf mit Argumenten: 832040, 1346269 Nach
Methodenaufruf mit Argumenten: 514229, 832040 Nach Methodenaufruf mit Argumenten: 317811
, 514229
Nach Methodenaufruf mit Argumenten: 1964 18, 317811
Nachher Methodenaufruf mit Argumenten: 121393, 196418
Nach Methodenaufruf mit Argumenten: 75025, 121393
Nach Methodenaufruf mit Argumenten: 46368, 75025
Nach Methodenaufruf mit Argumenten: 28657, 46368
Nach Methodenaufruf mit Argumenten: 17711, 28657
Nach Methodenaufruf mit Argumenten: 10946,
17711 Nach Methodenaufruf mit Argumenten: 6765, 10946
Nach Methodenaufruf mit Argumenten: 4181, 6765
Nach Methodenaufruf mit Argumenten : 2584, 4181
Nach Methodenaufruf mit Argumenten: 1597, 2584
Nach Methodenaufruf mit Argumenten: 987, 1597
Nach Methodenaufruf mit Argumenten: 610, 987
Nach Methodenaufruf mit Argumenten: 377, 610
Nach Methodenaufruf mit Argumenten: 233, 377
Nach Methodenaufruf mit Argumenten: 144, 233
Nach Methodenaufruf mit Argumenten: 89, 144
Nach Methodenaufruf mit Argumenten: 55, 89
Nach Methodenaufruf mit Argumenten: 34, 55
Nach Methodenaufruf mit Argumenten: 21, 34
Nach Methodenaufruf mit Argumenten: 13, 21
Nach Methodenaufruf mit Argumenten: 8, 13
Nach Methodenaufruf mit Argumenten: 5, 8
Nach Methodenaufruf mit Argumenten: 3, 5
Nach Methodenaufruf mit Argumenten: 2, 3
Nach Methodenaufruf mit Argumenten : 1, 2
Nach Methodenaufruf mit Argumenten: 1, 1
Nach Methodenaufruf mit Argumenten: 0, 1
Hier ist eine Visualisierung dessen, was passiert.
Sagen wir es noch einmal: Die Methode printFibonacciWithCondition wird aufgerufen. Es berechnet die aktuelle Zahl. Wenn es uns passt, dann zeigen wir es an und rufen die Methode printFibonacciWithCondition erneut mit neuen Argumenten auf.
Solange die rekursive Methode aufgerufen wird, spricht man von „rekursivem Abstieg“. Wenn rekursive Abschlüsse und Methodenaufrufe zurückkehren, sagen wir, dass der Aufrufstapel „abgewickelt“ wird.
Rekursion ist ein interessantes Thema in der Programmierung. Um den Stoff besser in den Griff zu bekommen, ändern wir unsere Aufgabe etwas. Die neue Aufgabe besteht darin, in absteigender Reihenfolge alle Zahlen der Fibonacci-Reihe auszugeben, die Integer.MAX_VALUE nicht überschreiten . Wir haben bereits den gesamten Code geschrieben, der für diese Aufgabe erforderlich ist. Es bleibt nur noch die Reihenfolge der Anzeige der aktuellen Zahl und des Aufrufs der rekursiven Methode zu vertauschen. Das heißt, im ersten Beispiel wurde die berechnete Zahl während des „Abstiegs“ angezeigt, aber jetzt müssen wir „ganz nach unten“ absteigen und dann „auf dem Weg zurück nach oben“ Zahlen anzeigen. Und natürlich vertauschen wir in der Hauptmethode die beiden Anfangszahlen der Sequenz (Null und Eins), nachdem wir sie nach dem Aufruf der rekursiven Methode angezeigt haben. Zur besseren LesbarkeitMethode.
public class Fibonacci {
public static void main(String[] args) {
printFibonacciWithCondition(0, 1);
System.out.println(1);
System.out.println(0);
}
private static void printFibonacciWithCondition(long penultimate, long previous) {
long current = penultimate + previous;
if (current > Integer.MAX_VALUE) {
return;
}
printFibonacciWithCondition(previous, current);
System.out.println(current);
}
}
Die Ausgabe wird sein:
1134903170
701408733
433494437
267914296
165580141
102334155
63245986
39088169
24157817
14930352
9227465
5702887
3524578
2178309
1346269
832040
514229
317811
196418
121393
75025
46368
28657
17711
10946
6765
4181
2584
1597
987
610
377
233
144
89
55
34
21
13
8
5
3
2
1
1
0
GO TO FULL VERSION