Discussion :

[jokoss]

Bonjour,

J'ai une fonction récursive qui permet de créer un arbre. A l'intérieur de cette fonction, j'appele une méthode qui me renvoie une liste liée d'éléments choisi aléatoirement dans un plus grand ensemble.

L'exécution du programme se fait itérativement sur des valeurs d'arbres de plus en plus grande. Jusqu'a une certaine taille je n' ai aucun problème.

A un moment donné l'exécution s'arrete et j'ai un "StackOverflowError" avec un probleme a la ligne où on appele la fonction random. (random.nextInt(int)).

Je me suis dabord dis que le problème ne venait pas de là mais si j'enleve le coté aléatoire de la fonction en prenant par exemple les n premiers élément de l'ensemble, la je n ai plus aucun probleme et je peux construire mes arbres avec des tailles encore bien plus importantes.

Je n'ai pas trouvé réellement de problème similaire sur internet. J'espere que quelqu'un pourra m'aider.

merci.

[TIFéç]

Salut Jokoss,

Comme il est dit dans le thread suivant (assez approchant, un probleme de stackoverflow sur un arbre): http://www.developpez.net/forums/arc...p/t-20101.html
Le stackoverflow est généralement issu d'une récursivité infinie. Maintenant selon la version de JVM utilisée il est possible qu'il y est une limite plus ou moins atteignable d'objets (ça doit quand même être assez énorme, je mise plutot sur la boucle infinie).

Tu devrai essayer de vérifier ce que te renvoi ton random, il est assez probable qu'à un moment ou un autre il te forme une boucle qui provoque l'erreur.

J'espère que cela pourra t'aider, bon courage,
Cordialement,
Tif

[jokoss]

bonjour,

Je ne pense pas que celà vienne d'une récursion infinie. J'ai une fonction récursive qui appelle une fonction non récursive et selon que dans cette sous-fonction j'utilise l'aléatoire (ca ne marche que jusqu'une certaine taille d'arbre) ou le non-aléatoire (qui a l'air de marcher pour des tailles supérieur).

Voici les 2 versions de la sous fonction:

celle qui ne marche pas:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
 
private ListeNumAtribut choisirEtPlacerAtributsUtilise(int nbAtributs, int maxAttr) {
        ListeNumAtribut firslistnumatr = null; 
 
        ListeNumAtribut dernierAtr = null;
        ListeNumAtribut tmpAttr;
 
        Random random = new Random();
            int k = random.nextInt(maxAttr) + 1;
            firslistnumatr = new ListeNumAtribut(k);
            dernierAtr = firslistnumatr;
 
            int i = 1;
            while (i < nbAtributs) {
                k = random.nextInt(maxAttr) + 1;
                while (existeDeja(k, firslistnumatr)) {
                    k = random.nextInt(maxAttr) + 1;
                }
                tmpAttr = new ListeNumAtribut(k);
                dernierAtr.setChaineSuiv(tmpAttr);
                dernierAtr = dernierAtr.getChaineSuiv();
 
                i++;
            }
 
             return firslistnumatr;
}

et voici la version qui ne provoque pas de stackoverflow:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
private ListeNumAtribut choisirEtPlacerAtributsUtilise(int nbAtributs, int maxAttr) {
        ListeNumAtribut firslistnumatr = null; 
 
        ListeNumAtribut dernierAtr = null;
        ListeNumAtribut tmpAttr;
 
            int tmp = 1;
        while (tmp <= nbAtributs) {
            if (firslistnumatr == null) {
                firslistnumatr = new ListeNumAtribut(tmp);
                dernierAtr = firslistnumatr;
            }
            else {
                tmpAttr = new ListeNumAtribut(tmp);
                dernierAtr.setChaineSuiv(tmpAttr);
                dernierAtr = dernierAtr.getChaineSuiv();
            }
 
            tmp++;
        }
 
             return firslistnumatr;
}

L'argument nbAtributs correspond au nombre d'éléments a choisir et l'argument maxAtr correspond au nombre total d'élément.

merci pour votre aide.

[CyberChouan]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
while (existeDeja(k, firslistnumatr)) {
   k = random.nextInt(maxAttr) + 1;
}

Je pense que le problème vient de là...
Si tu as nbAtributs >= maxAttr, au bout d'un moment, tu as épuisé tous les entiers possibles, et tu veux continuer d'en mettre dans ton arbre.

Comme tu génères un entier, t'aperçois qu'il est déjà dans la liste (puisqu'ils y sont tous), régénère un entier, t'aperçois... etc... et celà te donne une jolie boucle infinie.

De manière générale, ce genre de boucle et de test pour l'insertion d'une valeur aléatoire est à proscrire! Il vaut mieux avoir une liste des possibilités restantes, choisir aléatoirement une valeur parmis celles-ci et la supprimer de la liste des valeurs disponibles.

Comme ça, quand ta liste est vide, tu lèves une exception ou tu quittes la méthode... mais tu ne tombes pas dans une boucle infinie

[TIFéç]

Salut,

Bien vu CyberChouan, effectivement tout s'explique comme ça.

Juste une petite chose qui m'intrigue, on parlait de récursivité dans les premiers posts, mais ici moi je ne vois que des boucles. Est ce que je me trompe?

Cordialement,
Tif

[CyberChouan]

Non, toi tu n'as que des boucles.

La récursivité, c'est quand une méthode s'appelle elle-même.
Voici l'exemple le plus classique d'une méthode factorielle, écrite récursivement et itérativement.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public static int fact_recursive(int i) {
   if(i < 0) { return -1; /* erreur */ }
   else if(i ==0 || i == 1) { return 1; }
   else { return i*fact_recursive(i-1); } /* ici on a l'appel recursif */
}
 
public static int fact_iterative(int i) {
   if(i < 0) { return -1; /* erreur */ }
   int resultat = 1;
   while(i > 1) {
      resultat *= i;
      i--;
   }
   return resultat;
}