Iteration VS recursivit� [D�bat]

Salut A tous,

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

Merci,a++;

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 :

S�lectionner tout - Visualiser dans une fen�tre � part

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 :

S�lectionner tout - Visualiser dans une fen�tre � part

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'

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 :

S�lectionner tout - Visualiser dans une fen�tre � part

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++;

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'

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++:

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.

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 :)

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??

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

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

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 :

S�lectionner tout - Visualiser dans une fen�tre � part

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 :

S�lectionner tout - Visualiser dans une fen�tre � part

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 :

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
//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...

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

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

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++;

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.

Envoy� par 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...
[...]
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.

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

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.

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

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.