Récursivité et dépassement de pile...

**MasterOfChakhaL** · 28/04/2006, 15h47

Bonjour,

J'ai un peu de mal à trouver des infos là dessus, alors je m'en remets à vous...

j'ai une fonction récursive qui me parcours un tableau un peu dans tous les sens.
pour l'instant, je ne poste pas le code car l'algo me semble correcte.

Le tableau à parcourir est déclaré en tant que variable globale (et n'apparait pas dans la liste des paramètres de la fonction) histoire d'éviter les recopies.

Firefox me sors : too much recursion
Opera me sors : ECMAScript interpreter stack overflow

je ne pense pas que mon tableau soit recopié à chaque appel alors je me dis que javascript est limité en nombre "d'appels en attente"

le tableau à parcourir fait 7 par 7 et pour chaque élement je regarde dans 4 directions au maximum...
le test qui me pose problème ne doit provoquer que 8 appels...

En gros, je ne sais pas trop quoi en penser...
Connaissez vous les restrictions liées aux appels récursifs?

**SpaceFrog** · 28/04/2006, 15h54

ça ne m'est jamais arrivé, mais c'est sans doute parceque je n'ai jamais eu de trop grandes boucles à faire ...
j'ai déja eu des message du genre un script ralentit ....
essaye d'intercaller des setTimeout de façon à lui laisser le temps de respirer ...

**supermanu** · 28/04/2006, 15h54

A première vue il existe bien une limitation et malheureusement tu dois l'atteindre : http://w3log.server-wg.de/000055.html

**MasterOfChakhaL** · 28/04/2006, 16h02

je pense que 'le laisser respirer' fera qu'il mettra plus de temps àme jeter non?
par contre, je vais revoir l'algo (que je pensais bon) car pour l'instant je table sur 8 passages dans ma fonction...

Donc ce serait dommage...
Merci de vos réponses

**FMaz** · 28/04/2006, 16h02

Il faudra alors repenser à la facon de faire ton script.
Sur ce point, je dois t'avouer ne pas comprendre quelque chose.

Tu as un tableau de 7x7 (soit 49 cases)
Pour chaques cases, tu dois vérifier celle qui sont adjacente

Exemple d'utilisation: un jeu avec un perso qui se promène sur un terrain, il ne peux pas marcher dans l'eau.

Dans le cas d'un jeu, il suffit de vérifier au déplacement si le déplacement demandé est possible. Dans ton cas tu dois vérifier tout les "déplacements" possible avant.

Donc, tu fais une double boucle pour passer tout les champs du tableau:
for (i=0;i<7;i++)
for (ii=0;ii<7;ii++)

et pour chaque cases, tu vérifie les 4 (ou 8 si les diagonales comptes) qui sont adjacente. (Ne pas oublier de s'assurer qu'il existe une case adjacente. la case supérieure à la 1:5 existe pas par exemple)

Tout ceci pour en venir au fait que je ne vois aucune récursivité jusqu'ici. J'ai mal compris ?

**SpaceFrog** · 28/04/2006, 16h07

Code :

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

je pense que 'le laisser respirer' fera qu'il mettra plus de temps àme jeter non?

si c'est le principe de la baignoire percée que l'on remplit, tout dépend de si le debit de remplissage est plus important que celui ai fuite ...

**FMaz** · 28/04/2006, 16h18

Le problème donné en exemple (le lien externe) c'est un peu différent du principe de la baignoire... Pour le code suivant:

Code :

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

1
2
3
4
 
function test(){
   return test();
}

Le navigateur, même s'il respire et prend une pause après le 500ieme appel doit quand même garder les valeur de chaque fonction car chaque fonction demande de faire un retour de la valeur dela fonction suivante.

Donc tant qu'il ne cesse pas d'y avoir des appels une fonction, aucun "return" ne se fera car chaqu'un dépend du suivant.

Dans un tel cas, la pause est innutile je crois :-\

**denisC** · 28/04/2006, 16h21

Envoyé par MasterOfChakhaL

Firefox me sors : too much recursion
Opera me sors : ECMAScript interpreter stack overflow

Généralement, c'est à cause d'une récursion infinie, surtout si tu n'as prévu que 8 passages dans la fonction.

On peux voir le fameux algorithme?

**MasterOfChakhaL** · 28/04/2006, 16h26

bon, comme je vois que j'ai suscité la curiosité de certains, je m'explique un peu mieux sur le pourquoi du comment...

pour ceux qui connaissent, j'essaie de refaire le jeu naturalchimie...
pour ceux qui connaissent pas et qui veulent savoir: http://www.naturalchimie.com

j'appelle une piece l'ensemble des elements de meme valeur adjacent (pas de diagonale)

Code :

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

les deux "zones de 1" dans les coins en bas sont deux pieces distinctes
A partir du tableau représenté ci dessus,
je regarde chaque élément dans les quatre directions autorisées et si c'est la meme valeur alors, j'ajoute les coordonnées à un objet piece (c'est la que se trouve la récursivité)
Les éléments déjà parcourus sont mis à zero avant de continuer l'exploration afin de ne pas repasser plusieurs fois dessus.
Je pense que même si j'oubliais cette étape, j'aurais des résultats faux mais pas un bouclage infini

**FMaz** · 28/04/2006, 16h29

Envoyé par MasterOfChakhaL

[...] et si c'est la meme valeur alors, j'ajoute les coordonnées à un objet piece (c'est la que se trouve la récursivité)

Comprend pas ce bout. (en plus, il parrait que c'est celui qui pose problème

)

**MasterOfChakhaL** · 28/04/2006, 16h46

La méthode qui me construit ma collection de pieces:
(tmpPlateau est une variable globale)

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
	natChakhal.buildAllPiece = function() {
		tmpPlateau = this.plateau.slice(0, this.plateau.length );
		// parcours des lignes d'abord, des colonnes ensuite
		this.allPiece = new Array();
		for ( ligne = 1; ligne <= 7; ligne ++ ) {
			for ( colonne = 1; colonne <= 9; colonne++ ) {
				if ( myPiece = this.buildPiece( ligne, colonne ) ) {
					this.allPiece[this.allPiece.length] = myPiece;
				}							
			}
		}
 
	}

La méthode qui me construit une piece (on commence à rentrer dans le vif du sujet)

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
 
	// permet de construire une piece récursivement à partir d'un
	// élément du plateau
	natChakhal.buildPiece = function( L, C ) {
		if ( tmpPlateau[L][C] != 0 ) {
			var myPiece = new clNatPiece( tmpPlateau[L][C] );
			tmpPlateau[L][C] = 0;
			natChakhal.auxBuildPiece( myPiece, L, C );
			return myPiece;
		} else {
			return false;
		}
	}
 
        //piecePropagDir contient les quatre directions à vérifier
	natChakhal.auxBuildPiece = function( myPiece, L, C ) {
		for ( i = 0; i < this.piecePropagDir.length; i++ ) {
			var newL = parseInt( this.piecePropagDir[i][0] + L );
			var newC = parseInt( this.piecePropagDir[i][1] + C ); 
			if ( tmpPlateau[newL][newC] == myPiece.value ){
				myPiece.addItem( newL, newC );
				//l'élément a été géré, on le passe à 0
				tmpPlateau[newL][newC] = 0;
				this.auxBuildPiece( myPiece, newL, newC );
			}
		}
	}

Voilà, effectivement, je boucle indéfiniment, mais je ne vois pas pourquoi...

pour info, le code de ma classe clNatPiece

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
 
/* ********************************* *
 *  C L A S S E   N A T   P I E C E  *
 * ********************************* */
function clNatPiece( value ) {
	this.value = value;
	this.allLC = new Array();
}
 
clNatPiece.prototype.maxValue = 12;
 
clNatPiece.prototype.addItem = function( L, C ) {
	var newLC = true;
	// on vérifie d'abord que cet item n'existe pas déjà
	for ( i = 0; i< this.allLC.length && newLC; i++ ) {
		if ( this.allLC[i][0] == L && this.allLC[i][1] == C ) {
			newLC = false;
		}
	}
	if ( newLC ) {
		this.allLC[this.allLC.length] = new Array( L, C );
	}
}
 
clNatPiece.prototype.transform = function() {
	// on ne transforme que si la piece est constituée de 3 items au moins
	// et qu'elle n'a pas déjà la valeur max
	if ( this.allLC.length >= 3 && this.value < this.maxValue ) {
		// on recherche l'item de la piece le plus "en bas" puis le plus "à gauche"
		var myLC = this.allLC[0];
		for ( i = 1; i < this.allLC.length; i++ ) {
			if ( this.allLC[i][0] <= myLC[0] ) {
				if ( this.allLC[i][1] < myLC[1] ) {
					myLC = this.allLC[i];
				}
			}
		}
		this.value++;
		this.allLC = myLC; 
	}		
}

**FMaz** · 28/04/2006, 16h57

Je dois etre con parceque je comprend pas la base.
Construire une piece ??
--> La piece est une cellule du tableau, et le tableau est DÉJÀ construit au départ.

Ajouter à la collection ?
--> Quelle collection ?

**MasterOfChakhaL** · 28/04/2006, 17h02

Non, non,
t'inquietes tu n'es pas con, enfin pas pour ca, après, je te connais pas...

Avec ma sémantique, une cellule de tableau correspond à un item
Une piece est un ensemble d'item adjacent (pas de diagonales)
Ma collection, est l'ensemble des pieces...

avec le tableau représenté quelques message plus haut
j'aurai eu 2 pièces (1 avec quatre item, 1 autre avec 1 seul item)

C'est vrai que la précision avait son importance!!!
toutes mes désols de t'avoir fait douter de ton intégrité intellectuelle

**FMaz** · 28/04/2006, 17h53

Ok, donc, tu cherche à faire une fonction qui va:
- Créer un tableau de toutes les "pieces"
- Pour chaques "pieces", créer un tableau des unités/cases qu'il contient

(ou alors faire un méga tableau)

Bon, je planche sur ton code...

EDIT:
ok, comment fonctionne ta variable tmpPlateau , quel est son but ?
tmpPlateau[L][C] = ?

**FMaz** · 28/04/2006, 19h05

En prennant le problème à l'envers, je crois qu'il est possible d'éviter une récursivité infinie

Edit: sauf que deux pieces pourraient alors se relier, ce qui veux dire qu'il faudrait changer toute l'appartenance d'une des collections... hum... mauvaise idée. Je continue mes recherche (c'est un problème vraiment intéressant je trouve)

**FMaz** · 28/04/2006, 20h18

VOILÀ !!

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
 
 
<head>
 
<script type="text/javascript">
    var couleurs=new Array();
    couleurs[1]="#FF0000";
    couleurs[2]="#00FF00";
    couleurs[3]="#0000FF";
    couleurs[4]="#FFFF00";
    couleurs[5]="#00FFFF";
    couleurs[6]="#FF00FF";
    couleurs[7]="#660000";
    couleurs[8]="#006600";
    couleurs[9]="#000066";
    couleurs[10]="#666600";
    couleurs[11]="#006666";
    couleurs[12]="#660066";
    prochaine_piece=0;
    piece_adjacente=0;
    var lettre=new Array('','A','B','C','D','E');
    var unite = new Array();
 
 
    function CreerLaCollection(){
        var src;
        var resH,resG;
        for (L=1;L<6;L++){ unite[L]=Array();
        for (C=1;C<6;C++){ unite[L][C]="#000000"; //Couleur par défaut
 
            src=document.getElementById(lettre[L]+""+C);
            if (SiUn(src)){ //Détecter si cet unité est un 1
                piece_adjacente=0;
                //Vérifier si elle est adjacente à une piece
 
                resH=PieceAdjacenteHAUT(L,C);//Piece en haut
                resG=PieceAdjacenteGAUCHE(L,C);//Piece à Gauche
                if(resH!=0 && resG==0){ piece_adjacente=resH; }
                if(resH==0 && resG!=0){ piece_adjacente=resG; }
                if(resH!=0 && resG!=0){
                    if(resH==resG){
                        piece_adjacente=resH;
                    }else{
                        //A FAIRE: Deux connexions, il faut joindre les pieces ensemble
 
                    }
                }
 
 
                if(piece_adjacente!=0){
                    //Joindre l'unité à une piece
                    unite[L][C]=couleurs[piece_adjacente];
                }else{
                    //L'unité fait partie d'une nouvelle piece
                    prochaine_piece++;
                    unite[L][C]=couleurs[prochaine_piece];
                }
                src.style.color=unite[L][C];
            }
        }
        }
    }
 
 
 
    function PieceAdjacenteHAUT(L,C){ //Détecter s'il y a une Piece en haut
        if(L==1) //S'il n'y a aucune ligne en haut
            return 0;
 
        var src;
        src=document.getElementById(lettre[L-1]+""+C);
        if (SiUn(src)){ //Détecter si cet unité est un 1
            return UniteDansPiece(L-1,C);
        }
        return 0;
    }
 
    function PieceAdjacenteGAUCHE(L,C){ //Détecter s'il y a une Piece à Gauche
        if(C==1) //S'il n'y a aucune colone à gauche
            return 0;
 
        var src;
        src=document.getElementById(lettre[L]+""+(C-1));
        if (SiUn(src)){ //Détecter si cet unité est un 1
            return UniteDansPiece(L,C-1);
        }
        return 0;
    }
 
 
 
    function UniteDansPiece(L,C){ //Trouve dans quel piece fait partie une unité
        var i;
        for(i=1;i<13;i++){
            if(unite[L][C]==couleurs[i]){
                return i;
            }
        }
        return 0; //Erreur
    }
 
    function SiUn(elem){ //Détecte si une unité est un 1 (true) ou un 0 (false)
        if (elem.innerHTML==1)
            return true;
        else
            return false;
    }
 
</script>
</head>
 
<body>
<div id="A1" style="float:left;margin-left:5px;">0</div>
<div id="A2" style="float:left;margin-left:5px;">1</div>
<div id="A3" style="float:left;margin-left:5px;">0</div>
<div id="A4" style="float:left;margin-left:5px;">0</div>
<div id="A5" style="float:left;margin-left:5px;">0</div><br />
<div id="B1" style="float:left;margin-left:5px;">1</div>
<div id="B2" style="float:left;margin-left:5px;">0</div>
<div id="B3" style="float:left;margin-left:5px;">1</div>
<div id="B4" style="float:left;margin-left:5px;">0</div>
<div id="B5" style="float:left;margin-left:5px;">0</div><br />
<div id="C1" style="float:left;margin-left:5px;">1</div>
<div id="C2" style="float:left;margin-left:5px;">0</div>
<div id="C3" style="float:left;margin-left:5px;">1</div>
<div id="C4" style="float:left;margin-left:5px;">1</div>
<div id="C5" style="float:left;margin-left:5px;">1</div><br />
<div id="D1" style="float:left;margin-left:5px;">1</div>
<div id="D2" style="float:left;margin-left:5px;">0</div>
<div id="D3" style="float:left;margin-left:5px;">0</div>
<div id="D4" style="float:left;margin-left:5px;">1</div>
<div id="D5" style="float:left;margin-left:5px;">1</div><br />
<div id="E1" style="float:left;margin-left:5px;">1</div>
<div id="E2" style="float:left;margin-left:5px;">1</div>
<div id="E3" style="float:left;margin-left:5px;">0</div>
<div id="E4" style="float:left;margin-left:5px;">0</div>
<div id="E5" style="float:left;margin-left:5px;">1</div><br />
<script>CreerLaCollection();</script>
</body>
</html>

Edit: Sauf que j'ai encore un bug qui promet de BEAUCOUP compliquer les choses.

Je pense recommencer l'idée en y allant "passe par passe"

**FMaz** · 28/04/2006, 21h50

Bon, j'ai abandonnée l'idée de faire un script SANS récurcivité pour ca, mais en créant un script récursif je me suis rendu compte que j'étais (peut-etre) aussi con que toi (enfin, si ta fais le meme truc que moi)

Tu as bien dit que tu vérifiait les QUATRES directions ?

Donc, Exemple de matrice:
0000
0100
0100
0000

Quand le script arrive au premier 1, il vérifie dans les 4 directions: HAUT, GAUCHE, DROITE, BAS... HAHA !! un autre 1 en bas, alors il va en bas et fait la meme chose:

Voyons voir s'il y a un 1 près de moi: GAUCHE, DROITE, BAS, HAUT... HAHA! il y a un 1 en haut de mois

Alors il va au 1 d'en haut et recommence, GAUCHE, DROITE, HAUT, BAS.. HAHA! il y a un 1 en bas de moi

Je continue ?

**FMaz** · 28/04/2006, 21h59

Fini la rigolade, voici un script récursif qui explose pas et qui fonctionne

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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
 
 
<head>
 
<script type="text/javascript">
    var couleurs=new Array();
    couleurs[1]="#FF0000";
    couleurs[2]="#00FF00";
    couleurs[3]="#0000FF";
    couleurs[4]="#FFFF00";
    couleurs[5]="#00FFFF";
    couleurs[6]="#FF00FF";
    couleurs[7]="#660000";
    couleurs[8]="#006600";
    couleurs[9]="#000066";
    couleurs[10]="#666600";
    couleurs[11]="#006666";
    couleurs[12]="#660066";
    prochaine_piece=0;
    var lettre=new Array('','A','B','C','D','E');
    var unite = new Array();
 
 
    function CreerLaCollection(){
        var src;
        var resH,resG;
 
        //Innitialiser tout le tableau
        for (L=1;L<6;L++){
            unite[L]=Array();
            for (C=1;C<6;C++){
                unite[L][C]="#000000";
            }
        }
 
 
        for (L=1;L<6;L++){
        for (C=1;C<6;C++){
            if (SiUn(L,C)){ //Détecter si cette unité est un 1
                if(NonTag(L,C)){
                    prochaine_piece++;
                    Tag(L,C);
                    Etendre(L,C);
                }
            }
        }
        }
    }
 
    function Etendre(L,C){
        if(L>1 && SiUn(L-1,C) && NonTag(L-1,C)){
            Tag(L-1,C);
            Etendre(L-1,C);
        }
        if(C>1 && SiUn(L,C-1) && NonTag(L,C-1)){
            Tag(L,C-1);
            Etendre(C-1);
        }
        if(L<5 && SiUn(L+1,C) && NonTag(L+1,C)){
            Tag(L+1,C);
            Etendre(L+1,C);
        }
        if(C<5 && SiUn(L,C+1) && NonTag(L,C+1)){
            Tag(L,C+1);
            Etendre(L,C+1);
        }
    }
 
    function NonTag(L,C){
        var src=document.getElementById(lettre[L]+""+C);
        if (unite[L][C]=="#000000")
            return true;
        else
            return false;
    }
 
    function Tag(L,C){
        var src=document.getElementById(lettre[L]+""+C);
        src.style.color=couleurs[prochaine_piece];
        unite[L][C]=couleurs[prochaine_piece];
    }
 
 
    function SiUn(L,C){ //Détecte si une unité est un 1 (true) ou un 0 (false)
        var src=document.getElementById(lettre[L]+""+C);
        if (src.innerHTML==1)
            return true;
        else
            return false;
    }
 
</script>
</head>
 
<body>
<div id="A1" style="float:left;margin-left:5px;">0</div>
<div id="A2" style="float:left;margin-left:5px;">1</div>
<div id="A3" style="float:left;margin-left:5px;">0</div>
<div id="A4" style="float:left;margin-left:5px;">0</div>
<div id="A5" style="float:left;margin-left:5px;">0</div><br />
<div id="B1" style="float:left;margin-left:5px;">1</div>
<div id="B2" style="float:left;margin-left:5px;">0</div>
<div id="B3" style="float:left;margin-left:5px;">1</div>
<div id="B4" style="float:left;margin-left:5px;">0</div>
<div id="B5" style="float:left;margin-left:5px;">0</div><br />
<div id="C1" style="float:left;margin-left:5px;">1</div>
<div id="C2" style="float:left;margin-left:5px;">1</div>
<div id="C3" style="float:left;margin-left:5px;">1</div>
<div id="C4" style="float:left;margin-left:5px;">1</div>
<div id="C5" style="float:left;margin-left:5px;">1</div><br />
<div id="D1" style="float:left;margin-left:5px;">1</div>
<div id="D2" style="float:left;margin-left:5px;">0</div>
<div id="D3" style="float:left;margin-left:5px;">0</div>
<div id="D4" style="float:left;margin-left:5px;">1</div>
<div id="D5" style="float:left;margin-left:5px;">1</div><br />
<div id="E1" style="float:left;margin-left:5px;">1</div>
<div id="E2" style="float:left;margin-left:5px;">1</div>
<div id="E3" style="float:left;margin-left:5px;">0</div>
<div id="E4" style="float:left;margin-left:5px;">0</div>
<div id="E5" style="float:left;margin-left:5px;">1</div><br />
<script>CreerLaCollection();</script>
</body>
</html>

**MasterOfChakhaL** · 29/04/2006, 09h36

Salut,

je suis content de voir que mon problème interesse...

ok, comment fonctionne ta variable tmpPlateau , quel est son but ?

alors en fait, cette variable est un tableau a deux dimensions contenant l'état du jeu.
0 pour l'absence de piece
1,2,3... pour un item de valeur 1,2,3... (jusqu'à 12, ca c'est les règles du jeu)

Je passe par une variable temporaire car quand je parcours mon tableau, je passe chaque élément déjà géré à 0 pour évter le probleme que tu soulevais:

Tu as bien dit que tu vérifiait les QUATRES directions ?

Donc, Exemple de matrice:
0000
0100
0100
0000

Quand le script arrive au premier 1, il vérifie dans les 4 directions: HAUT, GAUCHE, DROITE, BAS... HAHA !! un autre 1 en bas, alors il va en bas et fait la meme chose:

Voyons voir s'il y a un 1 près de moi: GAUCHE, DROITE, BAS, HAUT... HAHA! il y a un 1 en haut de mois

Alors il va au 1 d'en haut et recommence, GAUCHE, DROITE, HAUT, BAS.. HAHA! il y a un 1 en bas de moi

Je peux également préciser que mon tableau est indexé de 0 à n et que je m'interesse au indices 1 à n-1 pour éviter de devoir tester les débordements...

je regarde ton code attentivement et j'en reparle ensuite...

Merci bien

**FMaz** · 30/04/2006, 03h44

Mon dernier code fonctionne bien selon mes test rapides.
Essaie-le...

Récursivité et dépassement de pile...

JavaScript

Discussions similaires

Partager

Partager