Utgångsvillkor. StackOverflowError

Exempel på rekursiv kod utan utgångsvillkor

Låt oss ta en ny titt på ett rekursivt problem. Som ett exempel, överväg att beräkna Fibonacci-tal. Alla kommer ihåg att Fibonacci-sekvensen är en numerisk sekvens där de två första talen är 0 och 1, och varje efterföljande tal är lika med summan av de två föregående talen.

Låt oss skriva kod för att beräkna och visa dessa siffror:

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öre det första anropet av den rekursiva printFibonacci- metoden, skriv ut de två första siffrorna i sekvensen: noll och ett. Vi måste göra detta eftersom den rekursiva metoden endast visar summan av ingångsparametrarna, inte själva parametrarna.

Koden ser okej ut: vi får två siffror, beräknar deras summa, skriver ut den på konsolen och anropar printFibonacci -metoden rekursivt igen. Vi skickar det föregående numret (föregående) och det nuvarande numret (nuvarande) som argument.

Faktum är att koden har två fel. Du kan se dem om du kör koden.

Det första felet svämmar över den långa typen. Det 104:e talet i vår sekvens är negativt, vilket indikerar att den långa typen svämmade över.

Det andra felet är annorlunda. Efter att ha beräknat ungefär 12 000 tal får vi:

Nu är en lämplig tidpunkt att komma ihåg vad en metodanropsstack är i Java. Java-maskinen registrerar alla funktionsanrop. För att göra detta använder den en speciell sorts samling som kallas en stack. När en funktion anropar en annan, skjuter Java-maskinen ett nytt StackTraceElement till stacken. När funktionen avslutas tas detta element bort från stacken. Följaktligen lagrar stacken alltid aktuell information om det aktuella tillståndet för funktionsanropsstacken. Dokumentationen för StackTraceElement säger att det är "Kasta när ett stackspill inträffar eftersom en applikation återkommer för djupt." En körande JVM har ett speciellt minnesområde för lagring av metodanropsstacken. Storleken på detta minnesområde beror på OS- och JVM-inställningarna. Förutom själva metodanropsstacken, primitiva variabler (specifika värden på metodparametrar) och adresserna till referensvariabler (i ett minnesområde som kallas "högen") lagras i detta speciella minnesområde. Tillgång till samtalsstacken följer LIFO-principen.

Korrigerat exempel med utgångsvillkor

Låt oss börja med att fixa det andra problemet i koden.

Låt oss försöka lösa problemet direkt: om stapeln är för liten, låt oss göra den större. För att göra detta, starta JVM med flaggan "-Xss" och ange hur mycket minne som ska allokeras för stacken. Låt oss försöka allokera 5 megabyte. Så här kommer det att se ut i IDEA:

Vi lyckades öka längden på produktionen. Nu kan beräkna mer än 49 000 nummer av sekvensen istället för att vara begränsad till cirka 12 000 nummer. Men någon gång får vi fortfarande en StackOverflowError .

Du kan försöka öka storleken på stacken, men det löser inte det grundläggande problemet. Så låt oss leta efter ett problem i logiken. Det måste finnas en punkt när rekursionen upphör. Med andra ord måste det finnas något tillstånd som bestämmer när den rekursiva metoden inte längre kommer att anropas, vilket gör att anropsstacken kan varva ner. För att definiera ett sådant villkor, låt oss göra vårt mål explicit: visa Fibonacci-serien så länge som dess tal är mindre än Integer.MAX_VALUE .

Låt oss skriva en ny printFibonacciWithCondition -metod som tar hänsyn till detta villkor. Och vi kommer att kalla den nya korrigerade metoden i huvudmetoden.

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 att ha kört koden ser vi att utdatan slutar med talet 1836311903. Siffran före denna är 1134903170. Summan av dessa tal är 2_971_215_073, vilket verkligen är större än Integer.MAX_VALUE (2_147_483_647 ) .

Denna ändring åtgärdade automatiskt buggen för långa spill. Om du behöver beräkna mer av serien måste du använda andra datatyper, till exempel BigInteger .

Rekursiv nedstigning och avkoppling

Låt oss analysera steg för steg hur vår kod exekveras. För att göra detta lägger vi till en ekometod och anropar den före och efter det rekursiva anropet av metoden printFibonacciWithCondition .

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 ger oss denna utdata:

Här är en visualisering av vad som händer.

Låt oss säga det igen: metoden printFibonacciWithCondition kallas. Den beräknar det aktuella antalet. Om det passar oss visar vi det och anropar metoden printFibonacciWithCondition igen med nya argument.

Så länge den rekursiva metoden anropas kallas detta för "rekursiv härkomst". När rekursivt avslutas och metodanrop återkommer, säger vi att anropsstacken "vindas av".

Rekursion är ett intressant ämne inom programmering. För att få bättre koll på materialet, låt oss ändra vår uppgift något. Den nya uppgiften är att mata ut, i fallande ordning, alla tal i Fibonacci-serien som inte överstiger heltal.MAX_VALUE . Vi har redan skrivit all kod som behövs för denna uppgift. Allt som återstår är att byta ordning för att visa det aktuella numret och anropa den rekursiva metoden. Det vill säga, i det första exemplet visades det beräknade siffran under "nedstigningen", men nu måste vi "sjunka till botten" och sedan visa siffror "på vägen upp igen". Och naturligtvis, i huvudmetoden , byter vi de två initiala talen i sekvensen (noll och ett) efter att ha visat dem efter att vi anropat den rekursiva metoden. För läsbarheten,metod.

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

Utgången blir: