condizioni di uscita. errore di overflow dello stack

Esempio di codice ricorsivo senza condizione di uscita

Diamo un'altra occhiata a un problema ricorsivo. Ad esempio, considera il calcolo dei numeri di Fibonacci. Tutti ricorderanno che la sequenza di Fibonacci è una sequenza numerica in cui i primi due numeri sono 0 e 1, e ogni numero successivo è uguale alla somma dei due numeri precedenti.

Scriviamo il codice per calcolare e visualizzare questi numeri:

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

Prima della prima chiamata del metodo ricorsivo printFibonacci , stampa i primi due numeri della sequenza: zero e uno. Dobbiamo farlo perché il metodo ricorsivo visualizza solo la somma dei parametri di input, non i parametri stessi.

Il codice sembra a posto: otteniamo due numeri, ne calcoliamo la somma, lo stampiamo sulla console e chiamiamo nuovamente il metodo printFibonacci in modo ricorsivo. Passiamo il numero precedente (precedente) e il numero corrente (corrente) come argomenti.

In realtà, il codice ha due errori. Puoi vederli se esegui il codice.

Il primo errore è l'overflow del tipo lungo . Il 104° numero nella nostra sequenza è negativo, a indicare che il tipo lungo è andato in overflow.

Il secondo errore è diverso. Dopo aver calcolato circa 12.000 numeri, otteniamo:

Ora è il momento opportuno per ricordare cos'è uno stack di chiamate di metodo in Java. La macchina Java tiene un registro di tutte le chiamate di funzione. Per fare ciò, utilizza un tipo speciale di raccolta chiamato stack. Quando una funzione ne chiama un'altra, la macchina Java inserisce un nuovo StackTraceElement nello stack. Quando la funzione termina, questo elemento viene rimosso dallo stack. Di conseguenza, lo stack memorizza sempre informazioni aggiornate sullo stato corrente dello stack delle chiamate di funzione. La documentazione per StackTraceElement dice che è "Generato quando si verifica un overflow dello stack perché un'applicazione ricorre troppo profondamente". Una JVM in esecuzione dispone di un'area di memoria speciale per l'archiviazione dello stack di chiamate al metodo. La dimensione di questa area di memoria dipende dalle impostazioni del sistema operativo e della JVM. Oltre allo stack di chiamate al metodo stesso, le variabili primitive (valori specifici dei parametri del metodo) e gli indirizzi delle variabili di riferimento (in un'area di memoria chiamata "heap") sono memorizzati in questa speciale area di memoria. L'accesso allo stack di chiamate segue il principio LIFO.

Esempio corretto con una condizione di uscita

Iniziamo risolvendo il secondo problema nel codice.

Proviamo a risolvere il problema frontalmente: se lo stack è troppo piccolo, ingrandiamolo. Per fare ciò, avviare la JVM con il flag "-Xss" e specificare quanta memoria allocare per lo stack. Proviamo ad allocare 5 megabyte. Ecco come apparirà in IDEA:

Siamo riusciti ad aumentare la lunghezza dell'output. Ora può calcolare più di 49.000 numeri della sequenza invece di essere limitato a circa 12.000 numeri. Ma a un certo punto, otteniamo ancora un StackOverflowError .

Puoi provare ad aumentare la dimensione dello stack, ma ciò non risolve il problema fondamentale. Quindi, cerchiamo un problema di logica. Ci deve essere un punto in cui la ricorsione si ferma. In altre parole, deve esserci una condizione che determina quando il metodo ricorsivo non verrà più chiamato, consentendo lo svolgimento dello stack di chiamate. Per definire tale condizione, rendiamo esplicito il nostro obiettivo: visualizzare la serie di Fibonacci fintanto che i suoi numeri sono inferiori a Integer.MAX_VALUE .

Scriviamo un nuovo metodo printFibonacciWithCondition che terrà conto di questa condizione. E chiameremo il nuovo metodo corretto nel metodo principale.

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

Dopo aver eseguito il codice, vediamo che l'output termina con il numero 1836311903. Il numero prima di questo è 1134903170. La somma di questi numeri è 2_971_215_073, che è effettivamente maggiore di Integer.MAX_VALUE (2_147_483_647 ) .

Questa modifica ha risolto automaticamente il bug di overflow lungo . Se devi calcolare più serie, dovrai utilizzare altri tipi di dati, ad esempio BigInteger .

Discesa ricorsiva e srotolamento

Analizziamo passo dopo passo come viene eseguito il nostro codice. Per fare ciò, aggiungeremo un metodo echo e lo chiameremo prima e dopo la chiamata ricorsiva del metodo 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);
        }
    }
}

Il programma ci fornisce questo output:

Ecco una visualizzazione di ciò che sta accadendo.

Ripetiamolo: viene chiamato il metodo printFibonacciWithCondition . Calcola il numero corrente. Se ci va bene, lo visualizziamo e chiamiamo di nuovo il metodo printFibonacciWithCondition con nuovi argomenti.

Finché viene chiamato il metodo ricorsivo, questo si chiama "discesa ricorsiva". Quando la ricorsiva termina e le chiamate di metodo ritornano, diciamo che lo stack di chiamate si sta "srotolando".

La ricorsione è un argomento interessante nella programmazione. Per gestire meglio il materiale, cambiamo leggermente il nostro compito. La nuova attività consiste nell'emettere, in ordine decrescente, tutti i numeri della serie di Fibonacci che non superano Integer.MAX_VALUE . Abbiamo già scritto tutto il codice necessario per questa attività. Non resta che scambiare l'ordine di visualizzazione del numero corrente e chiamare il metodo ricorsivo. Cioè, nel primo esempio, il numero calcolato è stato visualizzato durante la "discesa", ma ora dobbiamo "scendere fino in fondo" e quindi visualizzare i numeri "sulla via del ritorno". E ovviamente, nel metodo principale , scambiamo i due numeri iniziali della sequenza (zero e uno) dopo averli visualizzati dopo aver chiamato il metodo ricorsivo. Per leggibilità,metodo.

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

L'output sarà: