Condiții de ieșire. StackOverflowError

Exemplu de cod recursiv fără o condiție de ieșire

Să aruncăm o altă privire asupra unei probleme recursive. Ca exemplu, luați în considerare calcularea numerelor Fibonacci. Toată lumea își va aminti că șirul Fibonacci este o succesiune numerică în care primele două numere sunt 0 și 1, iar fiecare număr următor este egal cu suma celor două numere anterioare.

Să scriem cod pentru a calcula și afișa aceste numere:

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

Înainte de primul apel al metodei recursive printFibonacci , imprimați primele două numere ale secvenței: zero și unu. Trebuie să facem acest lucru deoarece metoda recursivă afișează doar suma parametrilor de intrare, nu parametrii înșiși.

Codul arată în regulă: obținem două numere, calculăm suma lor, o imprimăm pe consolă și apelăm recursiv metoda printFibonacci din nou. Trecem ca argumente numărul anterior (anterior) și numărul curent (actual).

De fapt, codul are două erori. Le puteți vedea dacă rulați codul.

Prima eroare este debordarea tipului lung . Al 104-lea număr din secvența noastră este negativ, ceea ce indică faptul că tipul lung a debordat.

A doua eroare este diferită. După calcularea a aproximativ 12.000 de numere, obținem:

Acum este un moment potrivit pentru a ne aminti ce este o stivă de apeluri de metodă în Java. Mașina Java păstrează o evidență a tuturor apelurilor de funcții. Pentru a face acest lucru, folosește un tip special de colecție numită stivă. Când o funcție o apelează pe alta, mașina Java împinge un nou StackTraceElement în stivă. Când funcția se termină, acest element este eliminat din stivă. În consecință, stiva stochează întotdeauna informații actualizate despre starea curentă a stivei de apeluri de funcție. Documentația pentru StackTraceElement spune că este „Aruncat atunci când are loc o depășire a stivei, deoarece o aplicație recurge prea profund”. Un JVM care rulează are o zonă specială de memorie pentru stocarea stivei de apeluri de metodă. Mărimea acestei zone de memorie depinde de setările sistemului de operare și JVM. În plus față de stiva de apeluri de metodă în sine, variabilele primitive (valori specifice ale parametrilor metodei) și adresele variabilelor de referință (într-o zonă de memorie numită „heap”) sunt stocate în această zonă de memorie specială. Accesul la stiva de apeluri urmează principiul LIFO.

Exemplu corectat cu o condiție de ieșire

Să începem prin a remedia a doua problemă din cod.

Să încercăm să rezolvăm problema direct: dacă stiva este prea mică, atunci hai să o facem mai mare. Pentru a face acest lucru, porniți JVM-ul cu indicatorul „-Xss” și specificați câtă memorie să alocați pentru stivă. Să încercăm să alocăm 5 megaocteți. Iată cum va arăta în IDEA:

Am reușit să creștem lungimea ieșirii. Acum se pot calcula mai mult de 49.000 de numere ale secvenței, în loc să fie limitat la aproximativ 12.000 de numere. Dar, la un moment dat, încă primim o StackOverflowError .

Puteți încerca să măriți dimensiunea stivei, dar asta nu rezolvă problema fundamentală. Deci, să căutăm o problemă de logică. Trebuie să existe un moment în care recursiunea se oprește. Cu alte cuvinte, trebuie să existe o condiție care să determine când metoda recursivă nu va mai fi apelată, permițând stivei de apeluri să se deruleze. Pentru a defini o astfel de condiție, să explicăm obiectivul nostru: afișați seria Fibonacci atâta timp cât numerele sale sunt mai mici decât Integer.MAX_VALUE .

Să scriem o nouă metodă printFibonacciWithCondition care va ține cont de această condiție. Și vom numi noua metodă corectată în metoda principală.

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

După rularea codului, vedem că rezultatul se termină cu numărul 1836311903. Numărul înainte de acesta este 1134903170. Suma acestor numere este 2_971_215_073, care este într-adevăr mai mare decât Integer.MAX_VALUE (2_147_483_647 ) .

Această modificare a remediat automat bug-ul de overflow lung . Dacă trebuie să calculați mai mult din serie, va trebui să utilizați alte tipuri de date, cum ar fi BigInteger .

Coborâre recursive și relaxare

Să analizăm pas cu pas cum este executat codul nostru. Pentru a face acest lucru, vom adăuga o metodă echo și o vom apela înainte și după apelul recursiv al metodei 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);
        }
    }
}

Programul ne oferă această ieșire:

Iată o vizualizare a ceea ce se întâmplă.

Să o spunem din nou: se numește metoda printFibonacciWithCondition . Acesta calculează numărul curent. Dacă ni se potrivește, atunci îl afișăm și apelăm din nou metoda printFibonacciWithCondition cu argumente noi.

Atâta timp cât este apelată metoda recursivă, aceasta se numește „coborâre recursivă”. Când recursiv se termină și apelurile de metodă revin, spunem că stiva de apeluri se „desface”.

Recursiunea este un subiect interesant în programare. Pentru a înțelege mai bine materialul, să ne schimbăm ușor sarcina. Noua sarcină este de a scoate, în ordine descrescătoare, toate numerele din seria Fibonacci care nu depășesc Integer.MAX_VALUE . Am scris deja tot codul necesar pentru această sarcină. Tot ce rămâne este să schimbați ordinea de afișare a numărului curent și apelarea metodei recursive. Adică, în primul exemplu, numărul calculat a fost afișat în timpul „coborârii”, dar acum trebuie să „coborâm până la fund” și apoi să afișăm numerele „pe drumul înapoi în sus”. Și bineînțeles, în metoda principală , schimbăm cele două numere inițiale ale secvenței (zero și unu) după ce le afișăm după ce numim metoda recursivă. Pentru lizibilitate,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);
    }
}

Ieșirea va fi: