Uitstapvoorwaarden. StackOverflowError

Voorbeeld van recursieve code zonder exit-voorwaarde

Laten we nog eens kijken naar een recursief probleem. Overweeg bijvoorbeeld om Fibonacci-getallen te berekenen. Iedereen zal zich herinneren dat de Fibonacci-reeks een numerieke reeks is waarin de eerste twee getallen 0 en 1 zijn, en elk volgend getal is gelijk aan de som van de twee voorgaande getallen.

Laten we code schrijven om deze getallen te berekenen en weer te geven:

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);
    }
}

Druk vóór de eerste aanroep van de recursieve printFibonacci -methode de eerste twee getallen van de reeks af: nul en één. We moeten dit doen omdat de recursieve methode alleen de som van de invoerparameters weergeeft, niet de parameters zelf.

De code ziet er goed uit: we krijgen twee getallen, berekenen hun som, drukken het af op de console en roepen de printFibonacci -methode opnieuw recursief aan. We geven het vorige nummer (vorige) en het huidige nummer (current) door als argumenten.

Eigenlijk bevat de code twee fouten. Je kunt ze zien als je de code uitvoert.

De eerste fout is het overlopen van het lange type. Het 104e getal in onze reeks is negatief, wat aangeeft dat het lange type overstroomde.

De tweede fout is anders. Na het berekenen van ongeveer 12.000 getallen krijgen we:

Dit is een geschikt moment om te onthouden wat een methodeaanroepstack is in Java. De Java-machine houdt alle functieaanroepen bij. Om dit te doen, gebruikt het een speciaal soort verzameling, een stapel genaamd. Wanneer een functie een andere aanroept, duwt de Java-machine een nieuw StackTraceElement op de stapel. Wanneer de functie eindigt, wordt dit element van de stapel verwijderd. Dienovereenkomstig slaat de stapel altijd up-to-date informatie op over de huidige status van de functieaanroepstapel. De documentatie voor StackTraceElement zegt dat het wordt "gegooid wanneer een stackoverloop optreedt omdat een toepassing te diep terugkeert." Een draaiende JVM heeft een speciaal geheugengebied voor het opslaan van de method call stack. De grootte van dit geheugengebied is afhankelijk van de OS- en JVM-instellingen. Naast de methodeaanroepstack zelf, primitieve variabelen (specifieke waarden van methodeparameters) en de adressen van referentievariabelen (in een geheugengebied genaamd de "heap") worden opgeslagen in dit speciale geheugengebied. Toegang tot de call-stack volgt het LIFO-principe.

Gecorrigeerd voorbeeld met een exit-voorwaarde

Laten we beginnen met het oplossen van het tweede probleem in de code.

Laten we proberen het probleem frontaal op te lossen: als de stapel te klein is, laten we hem dan groter maken. Om dit te doen, start u de JVM met de vlag "-Xss" en geeft u op hoeveel geheugen u wilt toewijzen aan de stapel. Laten we proberen 5 megabyte toe te wijzen. Zo ziet het eruit in IDEA:

We zijn erin geslaagd om de lengte van de uitvoer te vergroten. Kan nu meer dan 49.000 nummers van de reeks berekenen in plaats van beperkt te zijn tot ongeveer 12.000 nummers. Maar op een gegeven moment krijgen we nog steeds een StackOverflowError .

Je kunt proberen de stapel te vergroten, maar dat lost het fundamentele probleem niet op. Laten we dus eens kijken naar een probleem in de logica. Er moet een punt zijn waarop de recursie stopt. Met andere woorden, er moet een voorwaarde zijn die bepaalt wanneer de recursieve methode niet langer wordt aangeroepen, waardoor de call-stack kan ontspannen. Om een ​​dergelijke voorwaarde te definiëren, laten we ons doel expliciet maken: de Fibonacci-reeks weergeven zolang de getallen kleiner zijn dan Integer.MAX_VALUE .

Laten we een nieuwe printFibonacciWithCondition -methode schrijven die rekening houdt met deze voorwaarde. En we zullen de nieuwe gecorrigeerde methode in de hoofdmethode noemen.

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);
    }
}

Na het uitvoeren van de code zien we dat de uitvoer eindigt met het getal 1836311903. Het getal ervoor is 1134903170. De som van deze getallen is 2_971_215_073, wat inderdaad groter is dan Integer.MAX_VALUE (2_147_483_647 ) .

Deze wijziging loste automatisch de lange overflow-bug op. Als u meer van de reeksen moet berekenen, moet u andere gegevenstypen gebruiken, zoals BigInteger .

Recursieve afdaling en ontspanning

Laten we stap voor stap analyseren hoe onze code wordt uitgevoerd. Om dit te doen, voegen we een echo -methode toe en roepen deze aan voor en na de recursieve aanroep van de printFibonacciWithCondition -methode.

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);
        }
    }
}

Het programma geeft ons deze output:

Hier is een visualisatie van wat er gebeurt.

Laten we het nog een keer zeggen: de methode printFibonacciWithCondition wordt aangeroepen. Het berekent het huidige aantal. Als het ons uitkomt, geven we het weer en roepen we de methode printFibonacciWithCondition opnieuw aan met nieuwe argumenten.

Zolang de recursieve methode wordt aangeroepen, wordt dit "recursieve afdaling" genoemd. Wanneer recursief eindigt en methode-aanroepen terugkeren, zeggen we dat de call-stack aan het "afwikkelen" is.

Recursie is een interessant onderwerp in programmeren. Laten we onze taak een beetje veranderen om het materiaal beter onder de knie te krijgen. De nieuwe taak is om in aflopende volgorde alle getallen in de Fibonacci-reeks uit te voeren die niet groter zijn dan Integer.MAX_VALUE . We hebben al alle code geschreven die nodig is voor deze taak. Het enige dat overblijft is om de volgorde van het weergeven van het huidige nummer en het aanroepen van de recursieve methode om te wisselen. Dat wil zeggen, in het eerste voorbeeld werd het berekende aantal weergegeven tijdens de "afdaling", maar nu moeten we "helemaal naar beneden afdalen" en vervolgens nummers weergeven "op de terugweg naar boven". En natuurlijk wisselen we in de hoofdmethode de twee beginnummers van de reeks (nul en één) om nadat we ze hebben weergegeven nadat we de recursieve methode hebben aangeroepen. Voor de leesbaarheid,methode.

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);
    }
}

De uitvoer zal zijn: