Ausstiegsbedingungen. Stapelüberlauffehler

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:

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: