Iteration VS recursivité

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:

---

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. :wink:

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:

---

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 ?

Citation:

---

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

Citation:

---

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é :twisted: ):
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...

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

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

Citation:

---

Envoyé par Musaran

Citation:

---

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.

Citation:

---

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 :idea: (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.

Bonsoir

Citation:

---

Envoyé par Choupi

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.

---

C'est un parcours préfixé ça ;)

De manière génerale, de très rares problèmes ne peuvent etre solutionnés de manière simple qu'avec un algo récursif... Je pense notament à un projet perso ou un fichier est parsé pour trouver une sorte de structure. Selon le contexte (C'est a dire ce qui a déjà été lu dans le fichier), la structure diffère. La fonction de parsage est donc une fonction récursive qui accepte en paramètre une expression rationelle pour la recherche du motif suivant.

L'avantage principal d'un traitement récursif est la sorte de sauvegarde de contexte qu'elle implique (pas besoin de faire une pile) et la possibilite de passer outre extrèmement simplement (en passant l'adresse des variables en paramètres).

L'itératif quand a lui doit permettre au compilateur de générer un code plus efficace (déroulage [partiel] de boucles et autres optimisations), mais la, ca depend de beacoup de paramètres (code, compilateur, options)

Bonsoir

Cher Smortex,

Pouvez-vous me donner une version de l' algorithme du "quick sort", qui ne soit pas "récursif" , mais "itérafif" ?

Si c'est possible !

Merçi par avance.

Cordialement.

qsort est un algo de type "diviser pour reigner", donc on pourrait presque dire que par définition, son implémentation naturelle est récursive. Après, pour ce qui est de le coder en itératif, ca n'est qu'une question d'aimer s'embéter pour pas grand chose. Ca implique la création de piles pour stocker les limites des limites des [sous]tableaux a trier :

Citation:

---

Envoyé par Smortex

L'avantage principal d'un traitement récursif est la sorte de sauvegarde de contexte qu'elle implique (pas besoin de faire une pile)

---

Bref, le code devient moins lisible, et si le lecteur connais qsort, il ne vas pas lui sauter aux yeux... Peu d'interet donc de coder ca... Mais si tu veux vraiement que je te le fasse, je te laisse me faire une proposition par MP :mrgreen:

Pourquoi peu d'intérêt, c'est un excellent exercice d'algo qui nécessite de savoir gérer une pile :
En pseudo code, ça donnerait ça :

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 47 48 49 50

variables tab entiers, de 1 à N min entier : plus petit indice de la partie du tableau à trier max entier : plus grand indice de la partie du tableau à trier pivot entier : le nombre par rapport auquel on compare seuil entier : indice du pivot, les nombres dont l'indice est inférieur à seuil sont assurés d'être plus petits que le pivot. les nombres dont l'indice est supérieur à seuil sont assurés d'être plus grands que le pivot   debut empiler(1, n) tant que pile non vide faire depiler(min, max)   // on prend comme pivot le premier élément du tableau seuil <- min pivot <- tab[seuil]   pour i de min + 1 à max par pas de 1 faire si tab[i] < pivot alors // l'element pointé par i est plus peit que le pivot // donc il prend la place du pivot tab[seuil] <- tab[i]   // maintenant, le pivot se déplace d'une case, donc seuil <- seuil + 1   // la valeur case où se retrouve le pivot est mémorisée // à l'endroit qui vient d'être "libéré" tab[i] <- tab[seuil]   // le pivot est mémorisé à sa nouvelle place tab[seuil] <- pivot fin si fin pour   // le pivot est bien place // on trie ce qui est en dessous si min < seuil - 1 alors empiler(min, seuil - 1) fin si   // on trie ce qui est au dessus si seuil + 1 < max alors empiler(seuil + 1, max) fin si fin tant que fin

---

Je te laisse écrire les fonctions d'empilage, dépilage et de test de la pile.

Je crois bien qu'il a été prouvé que TOUT algorithme récursif peut être traité de façon récursive.
Après, pourquoi s'emmerder à dérécursifier ? tout simplement parce que ca le rendra plsu rapide. Mais en échange, il est (beaucoup) moins lisible et (beaucoup) plus chiant à coder.
L'avantage de la récursivité ? tu te fais pas chier, tu codes comme tu penses. Et y a aussi le fait que tu tables (inconsciemment) sur le fait que tu descends pas trop loin dans la récursion et que donc tu fera pas déborder ta pile (ce qui aurait pour résultat immédiat de planter irrémédiablement ton système) et aussi que ton système d'exploitation gère tout ca a peu près bien (ie est capable de te dire que ton programme fait chier, qu'il va lui couper les pattes et que ca serait cool si tu pouvais lui demander de lacher un peu la pile...)

Citation:

---

Envoyé par MoLysS

Je crois bien qu'il a été prouvé que TOUT algorithme récursif peut être traité de façon récursive.

---

Je suppose que cette tautologie est due à une faute de frappe...


PS: Pour moi, un algorithme récursif qu'on peut traiter "en itératif avec une pile" est toujours un algorithme récursif... Une vraie conversion en itératif, ce serait réussir à le faire SANS pile...

Le problème avec la recursivité, c'est le temps nécessaire au micorprocesseur pour appeler une fonction. Il faut avoir programmé en assembleur, mais c'est plus lent qu'on le pense.

Utiliser un itération avec une pile peut peut-être être considéré comme un algorithme récursif, ou non. L'important, c'est qu'on évite des appels de fonctions inutiles.

D'un autre coté, l'algorithme récursif peut selon le cas aboutir à du code plus propre et donc plus facile à maintenir.

J'voulais juste rajouter que beaucoup des compilateurs savent dérécursifier les fonctions, notamment en OCaml, et je crois C++. C'est à dire que lorsque le résultat de la fonction n'est que la fonction elle-même, ben ya pas de problème de débordement de pile, parce qu'ils gèrent ça d'une manière différente. Itérativement si j'puis dire.

Citation:

---

Envoyé par 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

---

Il existe une version de Fibonacci plus rapide, récursive utilisant le principe "diviser pour régner", qui l'exécute en temps logarithmique...
J'avais un devoir dessus l'année dernière en Maths Sup... (j'ai pas fini le problème en tout cas :D)

Citation:

---

Envoyé par gl

Je ne vois pas l'interet d'un debat recursivite contre iterativte.
...
Apres le choix est fait au cas par cas en fonction de la facilite, de l'aisance du developpeur, etc.

---

Ouai, en entreprise, le principal (sauf cas extèmes), un code clair et facilement modifiable par un tier et debeugable (he oui)....

Citation:

---

Envoyé par HanLee

Il existe une version de Fibonacci plus rapide, récursive utilisant le principe "diviser pour régner", qui l'exécute en temps logarithmique...
J'avais un devoir dessus l'année dernière en Maths Sup... (j'ai pas fini le problème en tout cas :D)

---

euh sa méthode se fait aussi en temps logarithmique, mais je suis d'accord que la constante est pas optimale ^^

Il y'a aussi une histoire de pédagogie.

J'ai commencer à la fac à programmer en scheme donc pas d'itération 100% récursif apres ce fut tres dure de se mettre à l'iteratif (en pascal), tout ce que je pouvais coder en récursif je le faisait bétement. Maintenant je me sert en majorité de l'itératif (sauf sur les chaines de caractéres).

Je pense que l'inverse est plus dure quand on a commencer à penser en iteratif et que l'on passe au recursif.

Citation:

---

Envoyé par yacinechaouche

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.

---

Le langage LISP permet à peu près tous les types de programmation qui existent, fonctionnelle ou pas, récursive ou pas (il y a tellement de types de boucles itératives en LISP... do, dotimes, dolist, loop, la dernière étant un langage complexe et puissant à elle toute seule, etc), objet ou pas. Je crois que la seule chose dont je n'ai pas encore entendu parler les adeptes de LISP, c'est la programmation orienté aspect... et encore il est possible que je mes infos ne soient tout simplement pas à jour.

Citation:

---

Envoyé par HanLee

J'voulais juste rajouter que beaucoup des compilateurs savent dérécursifier les fonctions, notamment en OCaml, et je crois C++. C'est à dire que lorsque le résultat de la fonction n'est que la fonction elle-même, ben ya pas de problème de débordement de pile, parce qu'ils gèrent ça d'une manière différente. Itérativement si j'puis dire.

Citation:

---

Envoyé par 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

---

Il existe une version de Fibonacci plus rapide, récursive utilisant le principe "diviser pour régner", qui l'exécute en temps logarithmique...
J'avais un devoir dessus l'année dernière en Maths Sup... (j'ai pas fini le problème en tout cas :D)

---

Exact. Elle implique de pratiquer la multiplication alexandrine (ou la puissance alexandrine je ne me souviens pas), ou les deux, et ce sont bien des algorithmes logarithmiques, sur des matrices de taille 2x2. C'est un exo classique d'algorithmique, assez intéressant, qu'on donne aux étudiants en informatique, et sur lequel ils souffrent en général pas mal à cause de leurs lacunes en maths . :D

Une chose est sure, la recursivite est tres interessante a apprendre. C'est bon pour l'algorithmie.

Un traitement recursif permet souvent de simplifier une ecriture. C'est utile.
Mais il est vrai que c'est parfois moins judicieux.

Le parfait exemple est le calcul de puissance par recursivite. On peut vite faire sauter sa pile.

En revanche, et c'est sur ce point que j'aimerais un avis, la recursivite me semble tres interessante des lors qu'on travaille sur des arbres ou des listes chainees.

En effet un traitement de liste chainee pour vider la liste, ou pour l'inverser est bien sur beaucoup plus lisible en recursif, et il me semble egalememt qu'il est plus efficace.
Il y a un danger si la liste a une taille immense, mais dans la plupart des cas je trouve que c'est une bonne idee, alors qu'un traitement iteratif necessite des operations supplementaires (sauvegarde du maillon precedent, jeux de pointeurs...).

Votre avis ?

Citation:

---

Envoyé par Jack_serious

En effet un traitement de liste chainee pour vider la liste, ou pour l'inverser est bien sur beaucoup plus lisible en recursif, et il me semble egalememt qu'il est plus efficace.
Il y a un danger si la liste a une taille immense, mais dans la plupart des cas je trouve que c'est une bonne idee, alors qu'un traitement iteratif necessite des operations supplementaires (sauvegarde du maillon precedent, jeux de pointeurs...).

Votre avis ?

---

Je ne trouve pas que l'inversion d'une liste soit compliqué, et je discuterais sur l'efficacité:

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

sliste *inverse(sliste *liste) { sliste *res = NULL,*tmp; /* Tant que la liste est non vide */ while(liste) { /* On stocke le prochain élément */ tmp = liste->next;   /* On va déplacer premier élément */ liste->next = res; res = liste;   /* On passe au prochain */ liste = tmp; } /* On retourne le résultat */ return res; }

---

Jc

Bonjour,
je fais de l'imagerie numérique et j'ai du à moment donné lancer un longue récursivité sur une image (calcul de composantes connexe) en 1024*1024.
Et bien.... Boum la pile d'exécution.
Dans mon boulot nous nous méfions de la récursivité pour ce souci.
Sinon je suis partisant de son utilisation.

Quand une fonction ne s'appelle qu'une fois, remplacer le recursif par
l'itératif ne doit pas trop poser de problème

Mais quand elle s'appelle plusieurs fois, avec des paramètres différents, cela
devient vite un casse-tête

ex : les tours de Hanoi, où la fonction s'appelle 3 fois

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

#include <stdio.h> void Deplacer (int nombre_plateaux, int tour_origine, int tour_finale) { if (nombre_plateaux == 1) printf("deplacer %d vers %d\n",tour_origine,tour_finale); else { int tour_manoeuvre = 6 - tour_origine - tour_finale; Deplacer (nombre_plateaux - 1, tour_origine, tour_manoeuvre); Deplacer (1,tour_origine,tour_finale); Deplacer (nombre_plateaux - 1, tour_manoeuvre, tour_finale); } } int main () { Deplacer (4,1,2); getchar (); return 0; }

---

Citation:

---

Envoyé par Jack_serious

Le parfait exemple est le calcul de puissance par recursivite. On peut vite faire sauter sa pile.

---

Si tu utilises l'algorithme "diviser pour régner", tu ne fais pas sauter la pile, mais bon utiliser la récursivité pour un algorithme aussi simple, c'est de la paresse !

Citation:

---

Envoyé par Jack_serious

En revanche, et c'est sur ce point que j'aimerais un avis, la recursivite me semble tres interessante des lors qu'on travaille sur des arbres ou des listes chainees.

En effet un traitement de liste chainee pour vider la liste, ou pour l'inverser est bien sur beaucoup plus lisible en recursif, et il me semble egalememt qu'il est plus efficace.
Il y a un danger si la liste a une taille immense, mais dans la plupart des cas je trouve que c'est une bonne idee, alors qu'un traitement iteratif necessite des operations supplementaires (sauvegarde du maillon precedent, jeux de pointeurs...).

Votre avis ?

---

Si ta fonction récursive n'a pour seule valeur de retour que l'appel de fonction lui-même, tu es en situation de récursivité terminale, donc, le compilateur sait optimiser cette forme en la transformant en quelque chose d'itératif, et il ne surcharge donc pas la pile (sur un compilateur pas trop vieux quand même).
C'est utile de savoir ça :).

Citation:

---

Envoyé par ToTo13

Bonjour,
je fais de l'imagerie numérique et j'ai du à moment donné lancer un longue récursivité sur une image (calcul de composantes connexe) en 1024*1024.

---

Besoin de récursivité pour calculer les composantes d'une image? Votre algorithme doit ressembler aux algos de remplissage, non?

Pour calculer les composantes d'une image, il existe des algorithmes itératifs extrêmement performants.

Par exemple, avec l'algo suivant, il faut quelques dixièmes de seconde (moins?) pour calculer les composantes d'une image binaire de taille 5000x7000:

Code:

---

1 2 3 4 5 6

Pour L de 0 à Hauteur - 2: --Calculer les runs des lignes L et L+1; --Considérer chaque run comme une composante; --Parcourir les listes de runs des lignes L et L+1: ----A chaque fois que deux runs sont connectés, faire fusionner les composantes auxquells ils appartiennent

---

Pour mémoriser, à faible coût, quelles composantes ont été fusionnées entre elles, on maintient une structure union-find (dont chaque ensemble est constitué de composantes qui ont été fusionnées en une jusque-là).

A la fin de l'algo, on parcourt la liste des composantes:
- celles qui sont au somment d'un arbre inversé de la structure union-find sont des composantes (maximales) de l'image, car elles n'ont jamais été fusionnées avec d'autres (en revanche elles peuvent être le résultat de nombreuses fusions);

- les autres peuvent être détruires car elles ne sont que des "sous-composantes" résiduelles.


C'est la méthode d'extraction de composante la plus rapide que je connais, elle permet quand on la code dans le détail de nombreuses petites "optimisations", notamment la vitesse d'exécution est la même en 4-connexité et en 8-connexité (car on travaille sur des runs et non sur des pixels). Le parcours des deux listes de runs de deux lignes consécutives a aussi les avantages de l'algo de fusion de deux listes triées (on avance dans une des deux listes au moins à chaque itération). etc. etc.

On m'a cependant soufflé qu'il existait une méthode encore plus rapide qui serait une amélioration de celle-ci, mais je n'en ai jamais trouvé la trace nulle part...

Citation:

---

Envoyé par ToTo13

Bonjour,
je fais de l'imagerie numérique et j'ai du à moment donné lancer un longue récursivité sur une image (calcul de composantes connexe) en 1024*1024.
Et bien.... Boum la pile d'exécution.
Dans mon boulot nous nous méfions de la récursivité pour ce souci.
Sinon je suis partisant de son utilisation.

---

+1.

La récursivité ne donne du code "plus propre" que dans la mesure où les variables en jeu ont une faible empreinte mémoire. Dans le cas des traitements d'image, ce n'est pas le cas. Si on veut s'accrocher à un algo récursif, on doit alors se résoudre à rendre l'image visible "à travers" la fonction récursive (en déclarant l'image en variable globale par exemple". Le résultat est tout le contraire d'un code propre.

Comme Toto13, je travaille sur des algo qui traitent de grandes grilles rectangulaires. Dans ce contexte, ce qui est "propre", c'est d'utiliser une pile pour empiler le minimum d'information nécessaire et suffisant.

J'ajouterai un commentaire supplémentaire : en C++, depuis la STL (ça fait donc déjà un paquet d'années), gérer des piles, des files, et tout ce qu'on veut est devenu si facile à faire, avec du code compact et lisible, que la question du choix entre récursif ou non ne se pose plus tellement : au final, les versions récursives ont rarement un avantage significatif sur les versions à pile/file.