Udgangsbetingelser. StackOverflowError

Eksempel på rekursiv kode uden en udgangsbetingelse

Lad os se på et rekursivt problem igen. Som et eksempel kan du overveje at beregne Fibonacci-tal. Alle vil huske, at Fibonacci-sekvensen er en numerisk sekvens, hvor de første to tal er 0 og 1, og hvert efterfølgende tal er lig med summen af ​​de to foregående tal.

Lad os skrive kode for at beregne og vise disse tal:

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

Inden det første kald af den rekursive printFibonacci -metode skal du udskrive de første to tal i sekvensen: nul og et. Vi er nødt til at gøre dette, fordi den rekursive metode kun viser summen af ​​inputparametrene, ikke selve parametrene.

Koden ser ok ud: vi får to tal, beregner deres sum, udskriver den på konsollen og kalder printFibonacci -metoden rekursivt igen. Vi sender det forrige tal (forrige) og det nuværende tal (nuværende) som argumenter.

Faktisk har koden to fejl. Du kan se dem, hvis du kører koden.

Den første fejl flyder over den lange type. Det 104. tal i vores rækkefølge er negativt, hvilket indikerer, at den lange type løb over.

Den anden fejl er anderledes. Efter at have beregnet omkring 12.000 tal, får vi:

Nu er et passende tidspunkt at huske, hvad en metodekaldsstack er i Java. Java-maskinen registrerer alle funktionsopkald. For at gøre dette bruger den en særlig form for samling kaldet en stak. Når en funktion kalder en anden, skubber Java-maskinen et nyt StackTraceElement ind på stakken. Når funktionen slutter, fjernes dette element fra stakken. Følgelig gemmer stakken altid opdateret information om den aktuelle tilstand af funktionsopkaldsstakken. Dokumentationen til StackTraceElement siger, at det "kastes, når et stackoverløb opstår, fordi en applikation gentager sig for dybt." En kørende JVM har et særligt hukommelsesområde til lagring af metodekaldsstakken. Størrelsen af ​​dette hukommelsesområde afhænger af OS- og JVM-indstillingerne. Ud over selve metodekaldsstakken, primitive variabler (specifikke værdier af metodeparametre) og adresserne på referencevariabler (i et hukommelsesområde kaldet "heapen") er lagret i dette specielle hukommelsesområde. Adgang til opkaldsstakken følger LIFO-princippet.

Korrigeret eksempel med en udgangstilstand

Lad os starte med at løse det andet problem i koden.

Lad os prøve at løse problemet direkte: Hvis stakken er for lille, så lad os gøre den større. For at gøre dette skal du starte JVM med "-Xss" flaget og angive, hvor meget hukommelse der skal allokeres til stakken. Lad os prøve at tildele 5 megabyte. Sådan kommer det til at se ud i IDEA:

Det lykkedes os at øge længden af ​​output. Nu kan beregne mere end 49.000 numre af sekvensen i stedet for at være begrænset til omkring 12.000 numre. Men på et tidspunkt får vi stadig en StackOverflowError .

Du kan prøve at øge størrelsen af ​​stakken, men det løser ikke det grundlæggende problem. Så lad os se efter et problem i logikken. Der må være et tidspunkt, hvor rekursionen stopper. Med andre ord skal der være en betingelse, der bestemmer, hvornår den rekursive metode ikke længere vil blive kaldt, så opkaldsstakken kan afvikles. For at definere en sådan betingelse, lad os gøre vores mål eksplicit: Vis Fibonacci-serien, så længe dens tal er mindre end Integer.MAX_VALUE .

Lad os skrive en ny printFibonacciWithCondition -metode, der vil tage højde for denne betingelse. Og vi vil kalde den nye korrigerede metode i hovedmetoden.

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

Efter at have kørt koden, ser vi, at outputtet slutter med tallet 1836311903. Tallet før denne er 1134903170. Summen af ​​disse tal er 2_971_215_073, hvilket faktisk er større end Integer.MAX_VALUE (2_147_483_647 ) .

Denne ændring rettede automatisk den lange overløbsfejl. Hvis du skal beregne mere af serien, skal du bruge andre datatyper, såsom BigInteger .

Rekursiv nedstigning og afslapning

Lad os trin for trin analysere, hvordan vores kode udføres. For at gøre dette tilføjer vi en ekkometode og kalder den før og efter det rekursive kald af printFibonacciWithCondition -metoden.

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

Programmet giver os dette output:

Her er en visualisering af, hvad der sker.

Lad os sige det igen: metoden printFibonacciWithCondition kaldes. Den beregner det aktuelle antal. Hvis det passer os, så viser vi det og kalder printFibonacciWithCondition -metoden igen med nye argumenter.

Så længe den rekursive metode kaldes, kaldes denne "rekursiv afstamning". Når det rekursive afsluttes, og metodekaldene vender tilbage, siger vi, at opkaldsstakken "vinder af".

Rekursion er et interessant emne inden for programmering. For at få bedre styr på materialet, lad os ændre vores opgave lidt. Den nye opgave er at udlæse, i faldende rækkefølge, alle tal i Fibonacci-serien, der ikke overstiger Integer.MAX_VALUE . Vi har allerede skrevet al den nødvendige kode til denne opgave. Det eneste, der er tilbage, er at skifte rækkefølgen for at vise det aktuelle nummer og kalde den rekursive metode. Det vil sige, at i det første eksempel blev det beregnede tal vist under "nedstigningen", men nu skal vi "ned til bunden" og derefter vise tal "på vej op igen". Og selvfølgelig, i hovedmetoden , bytter vi de to indledende tal i sekvensen (nul og en) efter at have vist dem, efter at vi kalder den rekursive metode. For læsbarheden,metode.

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

Outputtet vil være: