Recursivité dans une méthode

**burak** · 17/04/2009, 21h54

Bonjour Tout le monde,

J'écris afin de sollicité votre aide. Quels sont les causes qui font qu'une méthode récursive s'arrête brusquement toute seule ? Parce que j'ai une méthode et elle s'arrête avant même d'avoir terminé.

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
bool Solitaire::solution() {
 
                        unsigned a,b,c;
                        cout<<" 0.0 ";
                        vector<position>::iterator it1;
                        cout<<" 0.1 ";
                        vector<position> temp = mouvementRestant.top();
                        cout<<" 0.2 ";
                        mouvementRestant.pop();
                        cout<<" 0.3 ";
 
                        if(nombrePion == 1) {
 
                            return true;
 
                        }else {
 
                            cout<<" 2 ";
                            for(it1=temp.begin();it1!=temp.end();it1++) {
 
                                        a = (*it1).depart;
                                        b = (*it1).milieu;
                                        c = (*it1).arrive;
 
                                        if( mouvement(a,b,c) ) {
                                            cout<<" 3 ";
                                            enleverPion(a,b,c);
                                            mouvementSucces.push(*it1);
                                            temp.erase(it1);
                                            mouvementRestant.push(temp);
                                            mouvementRestant.push(mouvementPossible);
                                            //cout<<"nombre de pion "<<nombrePion<<"   taille pileRestant:  "<<mouvementRestant.size()<<"  taille pileSucces : "<<mouvementSucces.size()<<endl;
                                            solution();
                                        }
 
                                }
                                cout<<" 4 ";
                                a = mouvementSucces.top().depart;
                                cout<<" 5 ";
                                b = mouvementSucces.top().milieu;
                                cout<<" 6 ";
                                c = mouvementSucces.top().arrive;
                                cout<<" 7 ";
                                annuler(a,b,c);
                                cout<<" 8 ";
                                //cout<<a<<" "<<b<<" "<<c<<endl;
                                mouvementSucces.pop();
                                cout<<" 9 ";
                                solution();
                        }
                        cout<<" 5 ";
                        return false;
                }
 
 
 
//partie pour comprendre le code
struct position {
 
                            unsigned depart;
                            unsigned milieu;
                            unsigned arrive;
                };
 
                unsigned nombrePion;
                vector<pair<unsigned, list<pair<unsigned, char> > > >matriceLien;
                vector<bool> pion;
                vector<position> mouvementPossible;
 
                stack<position> mouvementSucces;
                stack<vector<position> > mouvementRestant;
                stack<vector<bool> > pileEchiquier;

**remy72** · 18/04/2009, 12h51

stack overflow ?

**loufoque** · 18/04/2009, 13h39

Utilise un débogueur.

**burak** · 18/04/2009, 19h49

il n'y a aucun message. Pas de stack overflow etc.. Ça ne fonctionne pas. Y-t-il un problème avec ma méthode récursive?

**loufoque** · 19/04/2009, 17h39

Un débogueur te dira où ça boucle et tu pourrais vérifier l'état des variables.
Y'a pas un tutorial ou un truc qui apprend à déboguer ?

**burak** · 19/04/2009, 21h03

Le debbuger m'envoie un message

Child process PID: 3880
Program received signal SIGSEGV, Segmentation fault.
In ntdll!RtlRealPredecessor () (C:\WINDOWS\system32\ntdll.dll)

Il ne m'indique en aucun cas d'ou vient le problème. Tout ce que je sais, c'est qu'il s'arrête en plein milieu de la récursion.

**JulienDuSud** · 19/04/2009, 21h08

Envoyé par burak

Le debbuger m'envoie un message

Child process PID: 3880
Program received signal SIGSEGV, Segmentation fault.
In ntdll!RtlRealPredecessor () (C:\WINDOWS\system32\ntdll.dll)

Il ne m'indique en aucun cas d'ou vient le problème. Tout ce que je sais, c'est qu'il s'arrête en plein milieu de la récursion.

Il te dit plusieurs choses.

Qu'il y a eu une faute de segmentation, qui est survenue lors de l'appel de RtRealPredecessor.

Essai de faire un peu connaissance avec ton deboggeur, je suis sûr qu'il y a une pile d'appel avant ça ce qui te permettra de trouver exactement la ligne qui produit le bug.

**befalimpertinent** · 22/04/2009, 10h45

Code :

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

bool Solitaire::solution()

Une méthode récursive qui ne prend pas de paramètres c'est très douteux. Bonjour les effets de bord.
C'est peut être pas directement lié à ton problème mais tu devrais dérécusifier cette méthode.

**Ksempac** · 23/04/2009, 13h01

Outre la "recursivité" douteuse, je dirais que :

Code :

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

temp.erase(it1);

doit pas arranger la chose.

On attendrait plutot un

Code :

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

it1 = temp.erase(it1)

Il est fort possible que la seg fault vienne de la (manipuler une valeur qu'on a effacé = bobo).

Bon apres, pour comprendre ce que cette methode est sensé faire, il serait bon d'avoir quelques commentaires, parceque ce code ressemble a un bon gros plat de spaghetti moisi.

Invité · 30/04/2009, 23h55

Comme dit juste avant, ton problème n'est pas dans la récursivité, mais dans la boucle de ta fonction... En virant le code inutile, tu as...

Code :

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

1
2
3
4
5
6
7
for(it1=temp.begin();it1!=temp.end();it1++) {
 
   if( mouvement(a,b,c) ) {
         temp.erase(it1);
   }
 
}

Quand tu passes dans la condition : temp.erase(it1) efface l'élément sur lequel pointe it1, qui, du coup, ne pointe plus sur rien... A la fin de ta boucle, quand tu incrémentes le pointeur (it1++) tout peut arriver (ça peut marcher, remarque...)

La solution
it1=temp.erase(it1)
demande un peu d'aménagement de ton code : en fait, temp.erase(it1) renvoie le pointeur qui suit celui que tu viens d'effacer.

Du coup, quand tu feras it1++, tu sauteras un élément...

Il va donc te falloir un truc comme

Code :

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

1
2
3
4
5
6
7
8
for(it1=temp.begin();it1!=temp.end();) {
 
   if( mouvement(a,b,c) ) {
         it1=temp.erase(it1);
   }
   else it1++;
 
}

ou

Code :

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

1
2
3
4
5
6
7
8
9
it1=temp.begin();
do {
 
   if( mouvement(a,b,c) ) {
         it1=temp.erase(it1);
   }
   else it1++;
 
} while(it1!=temp.end());

Francois

**koala01** · 03/05/2009, 12h43

Salut,

Envoyé par fcharton

<snip>
Il va donc te falloir un truc comme

Code :

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

1
2
3
4
5
6
7
8
9
it1=temp.begin();
do {
 
   if( mouvement(a,b,c) ) {
         it1=temp.erase(it1);
   }
   else it1++;
 
} while(it1!=temp.end());

Francois

Personnellement, je préfèrerais la boucle while à la boucle do while, pour la simple et bonne raison que tu n'es, a priori, même pas sur que temp contient bel et bien au minimum un élément...

La modification est mineure, mais plus sécurisante encore:

Code :

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

1
2
3
4
5
6
7
8
9
it1=temp.begin();
while(it1!=temp.end())
{
 
   if( mouvement(a,b,c) )
       it1=temp.erase(it1);
   else
       ++it;
}

Recursivité dans une méthode

SL & STL C++

Discussions similaires

Partager

Partager