Kilépési feltételek. StackOverflowError

Példa rekurzív kódra kilépési feltétel nélkül

Nézzünk még egy pillantást egy rekurzív problémára. Példaként tekintsük a Fibonacci-számok kiszámítását. Mindenki emlékszik rá, hogy a Fibonacci-sorozat egy olyan numerikus sorozat, amelyben az első két szám 0 és 1, és minden további szám egyenlő az előző két szám összegével.

Írjunk kódot a következő számok kiszámításához és megjelenítéséhez:

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

A rekurzív printFibonacci metódus első hívása előtt nyomtassa ki a sorozat első két számát: nullát és egyet. Ezt azért kell megtennünk, mert a rekurzív metódus csak a bemeneti paraméterek összegét jeleníti meg, magukat a paramétereket nem.

A kód rendben van: kapunk két számot, kiszámoljuk az összegüket, kinyomtatjuk a konzolra, és újra meghívjuk a printFibonacci metódust rekurzívan. Az előző számot (előző) és az aktuális számot (jelenlegi) adjuk át argumentumként.

Valójában a kódnak két hibája van. Megtekintheti őket, ha futtatja a kódot.

Az első hiba a hosszú típus túlcsordulása . A sorozatunkban a 104. szám negatív, ami azt jelzi, hogy a hosszú típus túlcsordult.

A második hiba más. Nagyjából 12 000 szám kiszámítása után kapjuk:

Itt az alkalom, hogy felidézzük, mi az a módszerhívási verem a Java-ban. A Java gép minden függvényhívást rögzít. Ehhez egy speciális gyűjteményt használ, amelyet veremnek neveznek. Amikor egy függvény meghív egy másikat, a Java gép egy új StackTraceElement elemet helyez a verembe. Amikor a függvény véget ér, ez az elem eltávolításra kerül a veremből. Ennek megfelelően a verem mindig naprakész információkat tárol a függvényhívási verem aktuális állapotáról. A StackTraceElement dokumentációja azt írja, hogy "eldobják, ha veremtúlcsordulás történik, mert egy alkalmazás túl mélyen ismétlődik." A futó JVM-nek van egy speciális memóriaterülete a metódushívási verem tárolására. A memóriaterület mérete az operációs rendszer és a JVM beállításaitól függ. A metódushívási verem mellett A primitív változók (a metódusparaméterek specifikus értékei) és a referenciaváltozók címei (a "kupacnak" nevezett memóriaterületen) ebben a speciális memóriaterületen tárolódnak. A hívásveremhez való hozzáférés a LIFO elvet követi.

Javított példa egy kilépési feltétellel

Kezdjük a kód második problémájának kijavításával.

Próbáljuk meg megoldani a problémát: ha túl kicsi a verem, akkor növeljük meg. Ehhez indítsa el a JVM-et az "-Xss" jelzővel, és adja meg, hogy mennyi memóriát kell lefoglalni a verem számára. Próbáljunk 5 megabájtot lefoglalni. Így fog kinézni az IDEA-ban:

Sikerült megnövelni a kimenet hosszát. Most már több mint 49 000 számot tud kiszámolni a sorozatból, ahelyett, hogy körülbelül 12 000 számra korlátozódna. De egy ponton továbbra is StackOverflowError üzenetet kapunk .

Megpróbálhatja növelni a verem méretét, de ez nem oldja meg az alapvető problémát. Tehát keressünk egy problémát a logikában. Kell lennie egy pontnak, amikor a rekurzió leáll. Más szavakkal, léteznie kell valamilyen feltételnek, amely meghatározza, hogy a rekurzív metódus mikor nem hívódik többé, lehetővé téve a hívási verem feloldását. Egy ilyen feltétel meghatározásához tegyük explicitté a célunkat: jelenítsük meg a Fibonacci-sort, amíg a száma kisebb, mint Integer.MAX_VALUE .

Írjunk egy új printFibonacciWithCondition metódust, amely figyelembe veszi ezt a feltételt. Az új korrigált metódust pedig a főmetódusban fogjuk meghívni.

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

A kód futtatása után azt látjuk, hogy a kimenet a 1836311903 számmal végződik. Az előtte lévő szám 1134903170. Ezeknek a számoknak az összege 2_971_215_073, ami valóban nagyobb, mint Integer.MAX_VALUE (2_147_483_647 ) .

Ez a változtatás automatikusan kijavította a hosszú túlcsordulási hibát. Ha többet kell kiszámítania a sorozatból, akkor más adattípusokat kell használnia, például a BigIntegert .

Rekurzív leereszkedés és feloldás

Lépésről lépésre elemezzük a kódunk végrehajtását. Ehhez hozzáadunk egy echo metódust, és meghívjuk a printFibonacciWithCondition metódus rekurzív hívása előtt és után.

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

A program ezt a kimenetet adja:

Íme egy vizualizáció, hogy mi történik.

Mondjuk el még egyszer: a printFibonacciWithCondition metódust hívják. Kiszámolja az aktuális számot. Ha megfelel nekünk, akkor megjelenítjük, és új argumentumokkal újra meghívjuk a printFibonacciWithCondition metódust.

Amíg a rekurzív metódus hívva van, addig ezt "rekurzív leszállásnak" nevezik. Amikor a rekurzív befejeződik, és a metódushívások visszatérnek, azt mondjuk, hogy a hívásverem „letekerődik”.

A rekurzió érdekes téma a programozásban. Ahhoz, hogy jobban kezeljük az anyagot, változtassunk kissé a feladatunkon. Az új feladat az, hogy csökkenő sorrendben kiadja a Fibonacci sorozat összes olyan számát, amely nem haladja meg az Integer.MAX_VALUE értéket . Már megírtuk az ehhez a feladathoz szükséges összes kódot. Már csak az aktuális szám megjelenítési sorrendjét és a rekurzív metódus hívását kell felcserélni. Ez azt jelenti, hogy az első példában a kiszámított szám a „leereszkedés” során jelent meg, most viszont „le kell ereszkednünk” és utána „visszafelé menet” ki kell mutatnunk a számokat. És természetesen a fő metódusban felcseréljük a sorozat két kezdőszámát (nulla és egy), miután megjelenítettük őket, miután meghívtuk a rekurzív metódust. Az olvashatóság érdekébenmódszer.

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

A kimenet a következő lesz: