Utgangsbetingelser. StackOverflowError

Eksempel på rekursiv kode uten utgangsbetingelse

La oss ta en ny titt på et rekursivt problem. Som et eksempel kan du vurdere å beregne Fibonacci-tall. Alle vil huske at Fibonacci-sekvensen er en numerisk sekvens der de to første tallene er 0 og 1, og hvert påfølgende tall er lik summen av de to foregående tallene.

La oss skrive kode for å beregne og vise disse tallene:

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

Før det første kallet av den rekursive printFibonacci -metoden, skriv ut de to første tallene i sekvensen: null og én. Vi må gjøre dette fordi den rekursive metoden viser bare summen av inngangsparametrene, ikke selve parameterne.

Koden ser ok ut: vi får to tall, beregner summen deres, skriver den ut på konsollen og kaller printFibonacci -metoden rekursivt igjen. Vi sender det forrige tallet (forrige) og det nåværende tallet (nåværende) som argumenter.

Faktisk har koden to feil. Du kan se dem hvis du kjører koden.

Den første feilen flyter over den lange typen. Det 104. tallet i sekvensen vår er negativt, noe som indikerer at den lange typen fløt over.

Den andre feilen er annerledes. Etter å ha beregnet omtrent 12 000 tall, får vi:

Nå er et passende tidspunkt å huske hva en metodekallstack er i Java. Java-maskinen holder oversikt over alle funksjonsanrop. For å gjøre dette bruker den en spesiell type samling kalt en stack. Når en funksjon kaller en annen, skyver Java-maskinen et nytt StackTraceElement på stabelen. Når funksjonen avsluttes, fjernes dette elementet fra stabelen. Følgelig lagrer stabelen alltid oppdatert informasjon om den nåværende tilstanden til funksjonsanropsstakken. Dokumentasjonen for StackTraceElement sier at det "kastes når et stackoverflyt oppstår fordi en applikasjon kommer tilbake for dypt." En kjørende JVM har et spesielt minneområde for lagring av metodekallstabelen. Størrelsen på dette minneområdet avhenger av OS- og JVM-innstillingene. I tillegg til selve metodekallstabelen, primitive variabler (spesifikke verdier av metodeparametere) og adressene til referansevariabler (i et minneområde kalt "heapen") er lagret i dette spesielle minneområdet. Tilgang til anropsstakken følger LIFO-prinsippet.

Korrigert eksempel med en utgangstilstand

La oss starte med å fikse det andre problemet i koden.

La oss prøve å løse problemet direkte: hvis stabelen er for liten, så la oss gjøre den større. For å gjøre dette, start JVM med "-Xss"-flagget og spesifiser hvor mye minne som skal allokeres til stabelen. La oss prøve å tildele 5 megabyte. Slik vil det se ut i IDEA:

Vi klarte å øke lengden på utgangen. Nå kan beregne mer enn 49 000 tall av sekvensen i stedet for å være begrenset til omtrent 12 000 tall. Men på et tidspunkt får vi fortsatt en StackOverflowError .

Du kan prøve å øke størrelsen på stabelen, men det løser ikke det grunnleggende problemet. Så la oss se etter et problem i logikken. Det må være et punkt når rekursjonen stopper. Med andre ord må det være en tilstand som bestemmer når den rekursive metoden ikke lenger vil bli kalt, slik at anropsstakken kan slappe av. For å definere en slik betingelse, la oss gjøre målet vårt eksplisitt: vise Fibonacci-serien så lenge tallene er mindre enn heltall.MAX_VALUE .

La oss skrive en ny printFibonacciWithCondition -metode som vil ta hensyn til denne tilstanden. Og vi vil kalle den nye korrigerte metoden 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);
    }
}

Etter å ha kjørt koden ser vi at utdata slutter med tallet 1836311903. Tallet før denne er 1134903170. Summen av disse tallene er 2_971_215_073, som faktisk er større enn Integer.MAX_VALUE (2_147_483_647 ) .

Denne endringen løste automatisk den lange overløpsfeilen. Hvis du trenger å beregne mer av serien, må du bruke andre datatyper, for eksempel BigInteger .

Rekursiv nedstigning og avkobling

La oss analysere trinn for trinn hvordan koden vår utføres. For å gjøre dette, legger vi til en ekkometode og kaller den før og etter det rekursive kallet til 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 gir oss denne utgangen:

Her er en visualisering av hva som skjer.

La oss si det igjen: metoden printFibonacciWithCondition kalles. Den beregner gjeldende tall. Hvis det passer oss, viser vi det og kaller printFibonacciWithCondition -metoden igjen med nye argumenter.

Så lenge den rekursive metoden kalles, kalles dette "rekursiv nedstigning". Når rekursivt avsluttes og metodeanrop kommer tilbake, sier vi at anropsstakken "avvikles".

Rekursjon er et interessant tema innen programmering. For å få bedre grep om materialet, la oss endre oppgaven litt. Den nye oppgaven er å skrive ut, i synkende rekkefølge, alle tall i Fibonacci-serien som ikke overskrider Integer.MAX_VALUE . Vi har allerede skrevet all koden som trengs for denne oppgaven. Alt som gjenstår er å bytte rekkefølge for å vise gjeldende nummer og ringe den rekursive metoden. Det vil si at i det første eksemplet ble det beregnede tallet vist under "nedstigningen", men nå må vi "ned til bunnen" og deretter vise tall "på vei opp igjen". Og selvfølgelig, i hovedmetoden , bytter vi de to innledende tallene i sekvensen (null og en) etter å ha vist dem etter at vi kaller den rekursive metoden. For lesbarhet,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);
    }
}

Utgangen vil være: