Iteration VS recursivité [Débat]

[yacinechaouche]

Salut A tous,

Pourquoi certains n'aiment pas utiliser la recursivite dans leur programmes ? est-ce par rapport au temps d'execution ?

Merci,a++;

[Choupi]

Le choix entre recursivite ou iteration depend de la vision qu'on a du prog ...Et pas toujours de l'efficacite...
Par exemple le parcours infixe d'un arbre binaire est à mon avis tres clair d'un point de vue recursif ... Visiter la racine le sous arbre gauche, le sous arbre droit ... C'est limpide. Par contre pour la recherche d'un element dans un arbre ... les deux se valent :

Code :

1
2
3
RC (dans x,valeur k) si clef racine = k  alors retourner x sinon 
si k est < clef(x) 
alors RC(fils gauche(x),k) sinon RC(filsdroit(x),k)

Code :

1
2
3
IT(x,k) tant que x differ de la racine et k differ de clef(x) alors
faire si k < clef(x) alors x = FG(x) sinon x = FD(x)
retourner x

Je pense que l'iteration est plus eficace ... je me trompe ? mais le choix depend bien de la vision qu'on a du probleme... Ici je prend la recursivite.

C'est existanciel comme question ! Moi perso je prefere la recursivite car ca me semble simple et toujours clair.

Freif'

[yacinechaouche]

c'est clair que la recursivite est plus limpide comme tu dis,mais si tu dois rappeler une fonction en lui passant des paramétres,je pense que ca prends plus de temps qu'en faisant un iteration.En plus,si c'est une fonction qui renvoie une valeur,tu peux aussi avoir des problèmes au niveau de l'execution.C'est a dire si tu fais

Code :

1
2
3
4
5
6
7
8
9
10
11
 
int fonction(parametres){
   if(che pas quoi) 
      return valeur;
   for(une boucle){
     blablabla;
     fonction(parametres_modifies);//recursivite
   }
   //gros bloc de code
   blablablabla;
}

Tu pense que si le test if marche,alors la fonction renvoi la valeur et puis basta,c'est censé s'arreté,en fait non,car il y a les precedents appeles a la fonction qui sont toujours en attente,et elles vont poursuivre le reste de la porcedure,le gros bloc de code qui a en bas...Il faut fair attention a ce genre de boullette.

Salut,a++;

[Choupi]

Euh :

L'efficacite c'est relatif ... Ca depend du type de calcul ...
Dans ton exemple, dés que le test est vrai on retourne la valeur, on execute pas le blablabla ... de la fonction en cours... mais des autres...
Pourquoi place ce blablabla dans la fonction si on en a pas besoin ?

Envoyé par freifelder

Le choix entre recursivite ou iteration depend de la vision qu'on a du prog ....

En fait j'ai pas trop compris ton probleme ...
Et ca s'applique a quoi ?

Freif'

[yacinechaouche]

Salut,

Si si,on fait le blabla a tous les coups,puisque le if ne contient qu'une seul instruction(c'est pourquoi je n'ai pas mis d'accolades).en fait c'est le test d'arret.tout comme le gors bloc de code qui est tout en bas,il sera execute par l'appele courant.

La question n'est pas posé pour un programme precis,c'est just une question de methodologie et de choix algorithmique.Mais si tu veux savoir,j'ai posé cette question parceque je veux gagner en temps d'execution.

Salut,a++:

[Musaran]

La récursivité...
-Plus dur à appréhender si l'appel récursif n'est pas simplement en début/fin de fonction.
-Plus lent. Le mécansime d'appel de fonction est lourd.
-Plus encombrant. Une forte imbrication peut saturer la pile.
-Plus puissant. Peut imbriquer un nombre indéterminé de boucles par exemple.

[vic]

C'est parfois la facilité qui conduit à utiliser la récursivité alors qu'un peu de réflexion permet de trouver une solution plus simple.
Exemple le suite de fibonacci : méthode récursive lourde et lente ou bien formule directe très rapide (une dizaine d'opérations) qui fait intervenir le nombre d'or.
C'est juste un exemple :)

[Zero]

On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??

Et est-ce vraiment utile de supprimer la recursité pour parcourir un arbre dont la profondeur est en génrale égale à 20??

[yacinechaouche]

Tu fais comment pour le fibonachi sans recursivite si ce n'est d'une maniere iterative ?

[vic]

Je pose le nombre d'or Phi = ( 1+sqrt(5) ) / 2

Alors F(n) = ( Phi^n - (-Phi)^-n ) / sqrt(5)
Qu'on peut simplifier en F(n) = round( Phi^n / sqrt(5) )

Comme on pouvait s'en douter ca se démontre facilement par récurence en remarquant que Phi est racine de x^2=x+1 et donc Phi^n = Phi^(n-1) + Phi^(n-2) ce qui revient à la définition de la suite de Fibonacci.

vic

[Musaran]

Envoyé par Zero

On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??

Peut-être...
-Un tableau pour contenir tous les futurs pointeurs de noeud, ainsi qu'un indice du traitement en cours pour celui-ci.
-Une boucle infinie pour parcourir le tableau, dans laquelle:
--Faire les traitements dans l'ordre, avec un switch pour les séparer.
--Avancer l'indice en descendant dans l'arbre, le reculer en remontant.
--Sortir si le bon noeud est atteint/tous les noeuds sont traités.

Donc, il serait possible de reconstituer le fonctionnement d'un nombre indéterminé de boucles imbriquées...
Le tableau devrait être dynamique, ou d'une taille arbitrairement suffisante.

Exemple (non testé ):
La structure

Code :

1
2
3
4
5
6
#define NAry 3
 
struct node{
	struct node* sub[NAry]; //noeuds descendants
};
typedef struct node node;

Le parcours récursif

Code :

1
2
3
4
5
void WalkTree(node* root){
	printf("%p\n",root);
	for(int i=0 ; i!=NAry ; ++i)
		WalkTree(root->sub[i]);
}

Le parcours itératif

Code :

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
//permet de donner des noms aux étapes de traitement.
//trucage: le n° d'étape est aussi l'indice du pointeur à suivre.
enum steps {first=-1, display=first, /*n°s 0 à NAry-1 réservés*/ back=NAry+1};
typedef enum steps steps;
 
struct NodeAndStep{
	node* nd; //noeud à opérer
	int step; //étape de l'opération
};
typedef struct NodeAndStep NodeAndStep;
 
void WalkTree(node* root){
	int depth=0; //profondeur atteinte dans l'arbre (et le tableau)
	struct NodeAndStep nas[512]; //arbitrairement suffisant
	nas[0].nd  = root ; //noeud de départ
	nas[0].step= first; //étape de départ
 
	do{
		node       * currnode=  nas[depth  ].nd  ;
		steps      * pstep   = &nas[depth  ].step;
		NodeAndStep* nextnas = &nas[depth+1]     ;
 
		switch(*pstep)
		{
		case display:
			++(*pstep); //passer à l'étape suivante
			printf("%p\n",currnode);
			continue; //repartir de do
 
		default: //descendre le sous-noeud de même n°: 0,1 et 2 dans cet exemple
			++(*pstep);
			nextnas->nd  = currnode->sub[*pstep]; //node à 'suivre'
			nextnas->step= -1; //à traiter depuis le début
			++depth; //descendre dans l'arbre
 
			continue;
		case back: //tous les sous-noeuds parcourus, remonter
			if(depth==0) //si rien à remonter
				break; //quitter le switch, et la boucle
			else{
				--depth; //remonter
				continue;
			}
		}// switch
	}while(0);
}

Je vous laisse juge de l'intérêt...

[ken_survivant]

Salut,

La récursivité est bien pour de petits exemples (ex : calculer la factorielle d'un nombre plus ou moins petit).
De même pour de petits arbres ça va bien

Si vous avez un arbre de 20000 noeuds et que celui-ci n'est pas équilibré (cf : arbre AVL), dans le pire des cas, vous pourriez avoir une "liste". Pour faire une recherche, insertion ou suppression ca risque de prendre du temps...

En plus avec la récursivité, il faut bien concevoir l'algo pour être certain qu'il s'arrête. Avec des boucles du type : for, while() {...} ou do { ... }while(); il est assez facile de vérifier !

De plus, il est évident que tout ce que l'on peut faire en récursivité est possible sous forme itérative (sauf si les profs interdisent l'itération )...

Donc voilà, à vous de trancher !

++

Ken

[gl]

Je ne vois pas l'interet d'un debat recursivite contre iterativte.
A part les problemes deja evoque de saturation de pile et de temps d'execution, la recursivite ne pose de gros probleme et peut donc etre employe dans tout les autres cas.
Apres le choix est fait au cas par cas en fonction de la facilite, de l'aisance du developpeur, etc.
En bref il n'y a pas de regle generale pour l'utilisation ou non de la recursivite

[yacinechaouche]

Salut,

Merci a tous pour vos precieuses interventions.

Connaissez vous le langage LISP ?(Emacs est fait avec lisp).C'est un langage ou la majortié des alogorithmes(je crois) sont recursifs,c'est un langage qui introduit la programmation fonctionelle(humm...je crois ).Pensez vous que certains langages soient plus appropriés à l'utilisation de la recursivité que d'autres ? genre le traitement se fait differament ou je ne sais pas moi...



salut,a++;

[gl]

Effectivement le LISP emploie beaucoup la recursivite, ca vient en grande partie de la structure et de l'esprit du langage ou on travaille essentiellement sur les listes (LISP pour LISt Processing), du coup l'emploi de la recursivite est plus nturel.

[Zero]

Envoyé par Musaran

Peut-être...
[...]
Je vous laisse juge de l'intérêt...

Merci, c'est vrai que dans mon cas ça ne sert peut-être pas, vu que le niveau de recursivité est rarement important. Mais il doit pouvoir être très adapté à d'autres modèles de données.

[evercool]

Envoyé par Zero

On parle d'utiliser la récursivité ou non. Je me suis toujours posé cette question : peux-tu parcourir un arbre N-aire sans utiliser la récursivité??

Et est-ce vraiment utile de supprimer la recursité pour parcourir un arbre dont la profondeur est en génrale égale à 20??

je pense qu'on peut utilser la récursivité mais indirectement
en faite en n'utilse que la partie interessant de la recusrsivité c'est ça pile
alors on va pas faire des sauvgarde de contaxte, ni des jmp!ni des apelles recursive

mais une petite pile (très inferieurs a la pile originale), ou on arrangera les adresses des noues restant a parcourer ;-)

d'une façon générale, je pense que n'importe quelle fonction récursive simple (non double ou autre chose ) peut ce ramener a une foction itérative avec une pile

[Musaran]

Ce que fait mon exemple (sauf que je gère pas sa taille dynamiquement).

Pour une fonction récursive double, il faudrait simplement y créer une étape supplémentaire et éventuellement un tableau supplémentaire pour stocker une valeur intermédiaire.

C'est un problème se langage très intéressant.

[Newgaia]

slt
Pour repondre au pseudo dilem entre itération vs récursivité, je dirais que cela dépend de ton programme, enfin ton algorithme. Si tu calcules sa complexité, tu verras ce qu'il convient de choisir, mais cela dépend aussi de la représentation de tes données.

Et n'oublies pas Java bien et C tant mieux

[dj.motte]

Bonsoir,

Je pense que le problème de la récursivité dans le domaine de l' algorithmique, ne sait vraimment posé, qu' à l' époque du MS-DOS.

La programmation 32 bits permet l' usage d' une "pile" ou encore "stack", à de nombreuses applications, de tourner selon les principes de la récursivité.

Le véritable problème reste "comment convertir un algorithme récursif en algorithme itératif" , et comment convertir "un algorithme itératif en algorithme récursif".

Mais il ne s' agit là que d' un problème théorique, dont la plupart des développeurs se moquent.

Cordialement.