Exception in thread “main” java.lang.StackOverflowError

J'ai un bout de code et je ne pouvais pas comprendre pourquoi il me donne de l'Exception in thread "main" java.lang.StackOverflowError.

C'est la question: 

Given a positive integer n, prints out the sum of the lengths of the Syracuse 
sequence starting in the range of 1 to n inclusive. So, for example, the call:
lengths(3)
will return the the combined length of the sequences:
1
2 1
3 10 5 16 8 4 2 1 
which is the value: 11. lengths must throw an IllegalArgumentException if 
its input value is less than one.

Mon Code: 

import java.util.HashMap;

public class Test {

HashMap<Integer,Integer> syraSumHashTable = new HashMap<Integer,Integer>();

public Test(){

}

public int lengths(int n)throws IllegalArgumentException{

    int sum =0;

    if(n < 1){
        throw new IllegalArgumentException("Error!! Invalid Input!");
    }   

    else{


        for(int i =1; i<=n;i++){

            if(syraSumHashTable.get(i)==null)
            {
                syraSumHashTable.put(i, printSyra(i,1));
                sum += (Integer)syraSumHashTable.get(i);

            }

            else{

                sum += (Integer)syraSumHashTable.get(i);
            }



        }

        return sum;

    }



}

private int printSyra(int num, int count){

    int n = num;

    if(n == 1){

        return count;
    }

    else{   
            if(n%2==0){

                return printSyra(n/2, ++count);
            }

            else{

                return printSyra((n*3)+1, ++count) ;

            }

    }


}
}

Code de pilote: 

public static void main(String[] args) {
    //TODO Auto-generated method stub
    Test s1 = new Test();
    System.out.println(s1.lengths(90090249));
    //System.out.println(s1.lengths(5));
}

.
Je sais que le problème se trouve avec la récursivité. L'erreur ne se produit pas si l'entrée est une petite valeur, exemple: 5. Mais quand le nombre est énorme, comme 90090249, je suis l'Exception dans le thread "main" java.lang.StackOverflowError. Merci à tous pour votre aide. 🙂

J'ai presque oublié le msg d'erreur:

Exception in thread "main" java.lang.StackOverflowError
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:65)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:65)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
at Test.printSyra(Test.java:60)
Les plus susceptibles de dépassement d'entier. L'utilisation à long à la place. (Et il n'est pas nécessaire d'utiliser la récursivité ici, même si mettre en œuvre correctement, il ne devrait pas être StackOverflow d'erreur pour une certaine gamme de nombre).
Je n'ai pas vraiment voir une récursion?? Vous vous cachez quelque chose?? où est votre printSyra(i,1) méthode?
printSyra appelle printSyra
Comment pouvez-vous supposer que?? Son pas là..
vérifier les retours de printSyra méthode.

OriginalL'auteur Ray.R.Chua | 2012-10-07

  1. 7

    Votre algorithme est très bien. Cependant int est trop petit pour vos calculs, il échoue pour cette entrée:

    printSyra(113383, 1);

    À un certain point, des débordements d'entiers à valeur négative et votre mise en œuvre est fou, recursing à l'infini. Changement int num à long num et vous serez amende - pour un certain temps. Plus tard, vous aurez besoin BigInteger.

    Noter que selon Wikipedia sur Conjecture de Collatz (en gras le mien):

    La plus longue progression pour le premier numéro de départ de moins de 100 millions de dollars est 63,728,127, qui a 949 étapes. Pour les numéros de départ de moins de 1 milliard de dollars, il est 670,617,279, avec 986 étapes, et pour les nombres inférieurs à 10 milliards de dollars qu'il est 9,780,657,630, avec 1132 étapes.

    Le nombre total d'étapes est équivalent à un maximum de niveau d'imbrication (pile de profondeur), vous pouvez vous attendre. Donc, même pour un nombre relativement grand nombre StackOverflowError ne devrait pas se produire. Jetez un oeil à cette mise en œuvre à l'aide de BigInteger:

    private static int printSyra(BigInteger num, int count) {
    if (num.equals(BigInteger.ONE)) {
        return count;
    }
    if (num.mod(BigInteger.valueOf(2)).equals(BigInteger.ZERO)) {
        return printSyra(num.divide(BigInteger.valueOf(2)), count + 1);
    } else {
        return printSyra(num.multiply(BigInteger.valueOf(3)).add(BigInteger.ONE), count + 1);
    }
}

    Il fonctionne même pour les très grandes valeurs:

    printSyra(new BigInteger("9780657630"), 0)  //1132
printSyra(new BigInteger("104899295810901231"), 0)  //2254
    voir ma mise à jour sur la pile de profondeur.
    Je suppose que je suis un peu perdu moi-même, ici - j'ai pensé que les débordements de pile se produit généralement lorsque le relativement faible de la pile (où la fonction de l'etat est stockée) est à court de mémoire après un trop grand nombre d'appels récursifs, non pas à cause de certaines entier étant trop grand. Si je ne suis malentendu votre réponse? Je suis d'accord que l'utilisation d'int au lieu de long est probablement la cause réelle de l'OP du problème, mais il est toujours possible de répéter assez profondément pour provoquer un débordement de pile indépendamment de la façon dont grand vous pouvez faire le nombre d'entrée.
    Merci. J'ai changé int num de longue num et maintenant je les visages autre erreur: Exception in thread "main" java.lang.OutOfMemoryError: Java heap space à java.util.HashMap.redimensionner(HashMap.java:462) at java.util.HashMap.addEntry(HashMap.java:755) à java.util.HashMap.mettre(HashMap.java:385) à Tester.longueurs(de Test.java:26) à TestApp.principale(TestApp.java:10)
    J'ai écrit: "[...]des débordements d'entiers [...] et la mise en œuvre est fou, recursing infiniment" - la raison de cette mise en échec n'est pas à cause de la trop grande profondeur de récursivité (il n'est jamais que profonde, comme dit Wikipedia), mais à cause de débordement d'entier - qui provoque anormalement profonde de la récursivité. Lors de la mise en œuvre est correcte, StackOverflowError n'est pas un problème. Mais vous avez raison, sans récursion sur la queue d'optimisation de cette mise en œuvre est encore un peu inefficace, mais très clairement de lisibilité point de vue.
    Près de la fin, votre table de hachage va stocker environ 100 m éléments. Avez-vous encore besoin? Comme pour excès de vitesse, vous pouvez retourner la valeur de début de printSyra si vous avez rencontré un élément que vous avez calculé avant d'utiliser la table de hachage.

    OriginalL'auteur Tomasz Nurkiewicz

  2. 1

    C'est un problème inhérent avec des algorithmes récursifs. Faire le nombre de récurrences assez grand et on ne peut pas vraiment éviter un débordement de la pile, à moins que la langue peut garantir la queue-appel d'optimisation (Java et la plupart des C-comme les langues n'en ont pas). Le seul moyen de corriger cela est de "dérouler" la récursivité, la réécriture de l'algorithme de manière itérative ou avec une fonction d'assistance pour simuler l'état-le passage de l'appel récursif sans réellement l'imbrication des appels.

    Je ne sais pas pourquoi downvote.. suis-je raté quelque chose? S'il vous plaît commentaire si vous downvote.
    La récursivité est bien ici. Réel problème est avec dépassement d'entier.
    Hmm, êtes-vous sûr? Documentation de java.lang.StackOverflowError: Levée lorsqu'un débordement de pile se produit parce qu'une application se répète trop profondément.
    J'en suis sûr, parce que je sais ce que l'OP est en train de faire dans printSyra. Il devrait y avoir assez de pile pour quelques centaines de niveaux.
    La meilleure solution serait de la mettre en œuvre sans récursivité (de cette façon vous vous débarrasser de StackOverflow d'erreur). Aussi, puisque tu ne peux pas savoir nombre Maximum qui sera généré lors du dépouillement 3x+1 éviter entier et d'utiliser quelque chose de plus grand long ou peut-être BigInteger.

    OriginalL'auteur jrajav

  3. 1

    Une solution est de permettre à la JVM de prendre plus d'espace pour la pile de récursion, en utilisant le java -script de site à site de paramètre. Sa valeur par défaut est de moins d'un mégaoctet, IIRC, ce qui pourrait limiter à un couple de centaines de récurrences max.

    Une meilleure solution consiste à réécrire l'exercice sans récursivité:

    private int printSyra(int num){
    int count = 1;    
    int n = num;    
    while(n != 1){

            if(n%2==0){    
                n = n/2;
                ++count;
            }    
            else{    
                n=(n*3)+1;
                ++count;    
            }    
    }
    return count;
}
    Ma mise en œuvre avec la récursivité peut fonctionner avec N = 104899295810901231 qui a une longueur de 2254 (ericr.nl/wondrous/delrecs.html). Alors que je suis d'accord que la récursivité peut être un problème, par l'intermédiaire de numéros qui peuvent dépassement de la plage de entier avant le problème de récursivité des coups de pied dans.
    Votre version ne parvient toujours pas à calculer pour un nombre aussi petit que 113383 - mais au lieu de les jeter StackOverflowException, entre dans une boucle infinie. En outre, l'augmentation de la taille de la pile ne va pas aider pour les brisures de l'algorithme (problème de type de variable).

    OriginalL'auteur Geert Pante