conditions de sortie. erreur de débordement de pile

Exemple de code récursif sans condition de sortie

Revenons sur un problème récursif. Par exemple, considérons le calcul des nombres de Fibonacci. Tout le monde se souviendra que la suite de Fibonacci est une suite numérique dans laquelle les deux premiers nombres sont 0 et 1, et chaque nombre suivant est égal à la somme des deux nombres précédents.

Écrivons du code pour calculer et afficher ces nombres :

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

Avant le premier appel de la méthode récursive printFibonacci , imprimez les deux premiers nombres de la séquence : zéro et un. Nous devons le faire car la méthode récursive affiche uniquement la somme des paramètres d'entrée, pas les paramètres eux-mêmes.

Le code semble correct : nous obtenons deux nombres, calculons leur somme, l'affichons sur la console et appelons à nouveau la méthode printFibonacci de manière récursive. Nous passons le numéro précédent (previous) et le numéro actuel (current) comme arguments.

En fait, le code comporte deux erreurs. Vous pouvez les voir si vous exécutez le code.

La première erreur dépasse le type long . Le 104ème nombre de notre séquence est négatif, indiquant que le type long a débordé.

La deuxième erreur est différente. Après avoir calculé environ 12 000 nombres, nous obtenons :

Le moment est venu de rappeler ce qu'est une pile d'appels de méthode en Java. La machine Java conserve un enregistrement de tous les appels de fonction. Pour ce faire, il utilise un type spécial de collection appelé pile. Lorsqu'une fonction en appelle une autre, la machine Java place un nouveau StackTraceElement sur la pile. Lorsque la fonction se termine, cet élément est supprimé de la pile. En conséquence, la pile stocke toujours des informations à jour sur l'état actuel de la pile d'appels de fonction. La documentation de StackTraceElement indique qu'il est "lancé lorsqu'un débordement de pile se produit parce qu'une application se répète trop profondément". Une JVM en cours d'exécution dispose d'une zone de mémoire spéciale pour stocker la pile d'appels de méthode. La taille de cette zone mémoire dépend des paramètres du système d'exploitation et de la JVM. En plus de la pile d'appel de méthode elle-même, les variables primitives (valeurs spécifiques des paramètres de la méthode) et les adresses des variables de référence (dans une zone mémoire appelée "heap") sont stockées dans cette zone mémoire spéciale. L'accès à la pile d'appels suit le principe LIFO.

Exemple corrigé avec une condition de sortie

Commençons par résoudre le deuxième problème dans le code.

Essayons de résoudre le problème de front : si la pile est trop petite, agrandissons-la. Pour ce faire, démarrez la JVM avec le drapeau "-Xss" et spécifiez la quantité de mémoire à allouer à la pile. Essayons d'allouer 5 mégaoctets. Voici à quoi cela ressemblera dans IDEA :

Nous avons réussi à augmenter la longueur de la sortie. Peut maintenant calculer plus de 49 000 numéros de la séquence plutôt que d'être limité à environ 12 000 numéros. Mais à un moment donné, nous obtenons toujours un StackOverflowError .

Vous pouvez essayer d'augmenter la taille de la pile, mais cela ne résout pas le problème fondamental. Alors, cherchons un problème de logique. Il doit y avoir un moment où la récursivité s'arrête. En d'autres termes, il doit y avoir une condition qui détermine quand la méthode récursive ne sera plus appelée, permettant à la pile d'appels de se dérouler. Pour définir une telle condition, explicitons notre objectif : afficher la suite de Fibonacci tant que ses nombres sont inférieurs à Integer.MAX_VALUE .

Écrivons une nouvelle méthode printFibonacciWithCondition qui tiendra compte de cette condition. Et nous appellerons la nouvelle méthode corrigée dans la méthode 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);
    }
}
    

Après avoir exécuté le code, nous voyons que la sortie se termine par le nombre 1836311903. Le nombre avant celui-ci est 1134903170. La somme de ces nombres est 2_971_215_073, qui est en effet supérieure à Integer.MAX_VALUE (2_147_483_647 ) .

Cette modification a automatiquement corrigé le long bogue de débordement. Si vous devez calculer davantage de séries, vous devrez utiliser d'autres types de données, tels que BigInteger .

Descente et déroulement récursifs

Analysons étape par étape comment notre code est exécuté. Pour ce faire, nous allons ajouter une méthode echo et l'appeler avant et après l'appel récursif de la méthode 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);
        }
    }
}
    

Le programme nous donne cette sortie :

Voici une visualisation de ce qui se passe.

Répétons-le : la méthode printFibonacciWithCondition est appelée. Il calcule le nombre actuel. Si cela nous convient, nous l'affichons et appelons à nouveau la méthode printFibonacciWithCondition avec de nouveaux arguments.

Tant que la méthode récursive est appelée, cela s'appelle "descente récursive". Lorsque la récursivité se termine et que les appels de méthode reviennent, nous disons que la pile d'appels se "déroule".

La récursivité est un sujet intéressant en programmation. Pour mieux maîtriser le matériel, modifions légèrement notre tâche. La nouvelle tâche consiste à afficher, dans l'ordre décroissant, tous les nombres de la série de Fibonacci qui ne dépassent pas Integer.MAX_VALUE . Nous avons déjà écrit tout le code nécessaire pour cette tâche. Il ne reste plus qu'à échanger l'ordre d'affichage du nombre courant et d'appel de la méthode récursive. C'est-à-dire que dans le premier exemple, le nombre calculé était affiché pendant la "descente", mais maintenant nous devons "descendre tout en bas" puis afficher les chiffres "sur le chemin du retour". Et bien sûr, dans la méthode principale , nous échangeons les deux nombres initiaux de la séquence (zéro et un) après les avoir affichés après avoir appelé la méthode récursive. Pour la lisibilité,méthode.

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

La sortie sera :