Discussion :

[Smortex]

Bonsoir

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)

[dj.motte]

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.

[Smortex]

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 :

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

[Trap D]

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 :

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

[MoLysS]

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

[Médinoc]

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

[BugFactory]

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.

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

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 )

[akoril]

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

[Tellmarch]

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 )

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

[ronan99999]

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.

[Jorganiz]

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.

[Jorganiz]

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.

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 )

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 .

[Jack_serious]

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 ?

[fearyourself]

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 :

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

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

[HRS]

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 :

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
 
#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;
}

[HanLee]

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 !

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 .

[Jorganiz]

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 :

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

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

[ol9245]

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.