Discussion :

[DjDavOnline]

Bonjour,

Je me demande si la récursivité est possible sous environnement windows ?

J'ai pour ainsi dire, une structure de donnée de type map de triangles d'un maillage (myTriangle)

Définit par :

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
 
class myTriangle
{
	public:
		int id;
		int state;
		Vector3 colors;
		Vector3 normal;
		int vxIndice1;
		int vxIndice2;
		int vxIndice3;
 
		myTriangle * nface1;
		myTriangle * nface2;
		myTriangle * nface3;
}

Le but est d'à partir 1 triangle donné, de pouvoir naviguer chez les voisins, c'est pour cela que chaque triangle stock ses voisins.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
void etendreSelection(myTriangle * t)
{
	printf("Voi: Id %d !!\n",t->id);
	if(t->nface2 != NULL && t->nface2->state!=1)
	{
		t->nface2->state=1;
		etendreSelection(t->nface2);
	}
 
}

Est-ce que ce genre de code est possible sous windows ? (j'ai un doute concernant la possibilité de la récursivité, mais cela était du aux limitations de MS-DOS... maintenant, ce n'est pas plus le cas, je crois...)

Merci de m'éclairer

Cordialement

David

[ram-0000]

Je me demande si la récursivité est possible sous environnement windows ?

Oui

Le but est d'à partir 1 triangle donné, de pouvoir naviguer chez les voisins, c'est pour cela que chaque triangle stock ses voisins.

Ce n'est pas de la récursivité. La récursivité, c'est quand une fonction s'appelle elle même.
Ce que tu fais pourrait s'appeler une liste chainée. Chaque élément de la liste possède entre 0 et 3 voisins. En tout cas, ce que tu veux faire est possible.

j'ai un doute concernant la possibilité de la récursivité, mais cela était du aux limitations de MS-DOS... maintenant, ce n'est pas plus le cas, je crois...

Sous DOS aussi, c'était possible

[DjDavOnline]

Oui

Ce n'est pas de la récursivité. La récursivité, c'est quand une fonction s'appelle elle même.
Ce que tu fais pourrait s'appeler une liste chainée. Chaque élément de la liste possède entre 0 et 3 voisins. En tout cas, ce que tu veux faire est possible.


Sous DOS aussi, c'était possible

Merci

Je pense que j'ai subit les dires d'un prof pro-linux...

Bon et bien y'a plus qu'à

Merci à toi

[koala01]

Salut,

En fait, c'est le langage de programmation qui autorise ou non la récursivité.

Et le C comme le C++ l'autorisent sans aucun problème.

Là où le système d'exploitation intervient dans le jeu, c'est lorsqu'il s'agit de prévoir le nombre d'appels récursifs d'une fonction qui seront admis.

En effet, chaque fois que tu fais un appel de fonction non "inlinée" (et une fonction récursive ne peut, par définition, pas être inline), il y a un certain nombre d'informations qui sont mises "sur la pile" d'appel, de manière à être en mesure de les récupérer une fois que la fonction appelée est quittée et qu'il est question de reprendre l'exécution de la fonction appelante.

Cette pile d'appel n'est pas extensible et est, entre autres, déterminée par le système d'exploitation.

Et il est vrai que, sous DOS, la limitation de la pile était telle qu'il était facile d'obtenir un "stack overflow"...

Mais cette limitation se retrouve avec tous les systèmes d'exploitation (qu'il s'agisse de linux ou de windows ou de n'importe quel autre système), et je dirais presque que la question n'est pas de savoir "si" on va atteindre cette limite, mais "quand" on va l'atteindre

Et il faut avouer que, à l'époque, il était beaucoup plus fréquent de l'atteindre sous DOS que sous linux...

Mais bon, entre le bon vieux DOS et ne serait-ce que windows XP, il y a quand même eu plus de dix ans de progrès, et on considère généralement qu'un an d'évolution en informatique correspond lui-même à 10 d'évolution dans "la vie de tous les jours" (du moins, c'était le cas au départ)...

Cela revient à peu près à vouloir comparer les voitures actuelles à celles qui existaient avant la première guerre mondiale... Tu avoueras, que ce n'est en rien comparable

[DjDavOnline]

Oui...

Mais c'est surtout que cela fait 4 ans que je n'ai pas programmé pour un environnement windows... et du coup, je me suis posée cette question... bête.

En tout cas, merci pour ses précisions

[koala01]

Oui...

Mais c'est surtout que cela fait 4 ans que je n'ai pas programmé pour un environnement windows... et du coup, je me suis posée cette question... bête.

Il n'y a, à la base, aucune question idiote ou bête...

Seules la manière de l'exprimer et / ou la réponse le sont peut être

[DjDavOnline]

Entièrement d'accord

[Médinoc]

Il existe un cas qui, avec les bonnes optimisations, supporte une récursivité infinie, c'est la récursivité terminale. Parce qu'elle peut être optimisée de manière à se comporter comme une boucle itérative.

[JulienDuSud]

Il existe un cas qui, avec les bonnes optimisations, supporte une récursivité infini, c'est la récursivité terminale. Parce qu'elle peut être optimisée de manière à se comporter comme une boucle itérative.

Tiens d'ailleurs en parlant de récursivité terminale, est-ce que GCC est capable d'optimiser ça de manière à ce que les performances soient aussi bien qu'une boucle itérative ?

exemple:

Code :

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

1
2
3
4
5
6
7
8
9
 
int add_up( int n, int a )
{
   if( a <= 0 ) { 
      return n;
   } else {
      return add_up( n+1, a-1 );
   }
}

vs

Code :

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

1
2
3
4
5
6
7
8
9
 
int add_up( int n, int a )
{
   while ( a > 0 ) {
      ++n;
      --a;
   }
   return n;
}

[koala01]

Ce qu'il faut bien comprendre, c'est que la récursivité fait partie de ces possibilités qu'il est important de connaitre mais dont l'utilisation doit être murement réfléchie...

Dans une grande majorité des cas (hors du cas de la programmation générique, pour lesquels il y a effectivement possibilité de "déroulage" de la logique au moment de la compilation ou celui de la récursivité finale), il est fort probable que, si tu peux créer une boucle "normale" sans avoir à trop te "casser la tête", il soit préférable d'utiliser la boucle plutôt que la récursivité.

Pour l'exemple que tu présente, je choisirais, à titre personnel d'office la version utilisant la boucle

Par contre, s'il s'agit de parcourir un arbre en profondeur, je n'hésiterai pas une seconde et j'utiliserai la récursivité

[JulienDuSud]

Je ne dis pas le contraire, ma question consistait juste à ce qu'en faisait le compilateur

Si il arrivait à optimiser la fonction récursive de manière à ce que ses performances soient égales à une itération