algorithme récursif/itératif
Jaap de Haan
faut qu'il y ait une condition d'arrêt de la récursion (sinon la mémoire de
l'ordi va diminuer et tu va te retrouver avec des erreurs). Un algorithme
itératif ne s'appelle pas lui même, il utilise une boucle pour remplacer la
récursion.
Un exemple typique est le calcul de la factorielle
RECURSIF:
FONCTION factorielle (ENTIER n)
SI n EGALE 1 RETOURNER 1 /* arret de la recursivité */
SINON RETOURNER n*factorielle (n-1)
FIN FONCTION
ITERATIF:
FONCTION factorielle (ENTIER n)
ENTIER resultat = 1;
POUR i ALLANT DE 2 à n
resultat = resultat * i
FIN POUR
RETOURNER resultat
FIN FONCTION
La solution recursive est plus elegante mais consomme bcp de temps et de
mémoire (appels récursifs de fonctions dont il faut mémoriser les paramètres
et les adresses mémoire, en général dans la pile) comparée à la solution
moins jolie mais plus efficace itérative.
J'espère que ca t'aura aidé
mit freundlichen grüßen,
Jaap de Haan
<roma...@fairesuivre.fr> schrieb im Newsbeitrag
news:z7yA6.1703$FY5.1...@www.newsranger.com...
> Bonjour,
> je suis étudiant en prépa HEC et le programme de mathématiques inclut du
turbo
> pascal :
> on me demande dans un exercice de transformer un algorithme récursif en
algo
> itératif : qu'est-ce que cela veut dire ?
>
>
Jean-Loup GUILLAUME
> Bonjour,
> je suis étudiant en prépa HEC et le programme de mathématiques inclut du turbo
> pascal :
> on me demande dans un exercice de transformer un algorithme récursif en algo
> itératif : qu'est-ce que cela veut dire ?
Une fonction recursive est du type
fonction rec (entier n)
{
....
...rec(n-k)...
...
}
En clair c'est une fonction qui s'appelle elle meme
Une fonction iterative ne s'appelle pas.
Un "exemple" :
definition recursive de la factorielle : n!=n*(n-1)!
iteratif : n!=prod_{i=1}^{i=n} i
Vincent Lascaux
"Jaap de Haan" <j.de...@ids-imaging.de> a écrit dans le message news:
7dfua9...@news.ids-imaging.de...
> RECURSIF:
>
> FONCTION factorielle (ENTIER n)
> SI n EGALE 1 RETOURNER 1 /* arret de la recursivité */
> SINON RETOURNER n*factorielle (n-1)
> FIN FONCTION
>
> ITERATIF:
>
> FONCTION factorielle (ENTIER n)
> ENTIER resultat = 1;
> POUR i ALLANT DE 2 à n
> resultat = resultat * i
> FIN POUR
> RETOURNER resultat
> FIN FONCTION
>
> La solution recursive est plus elegante mais consomme bcp de temps et de
> mémoire (appels récursifs de fonctions dont il faut mémoriser les
paramètres
> et les adresses mémoire, en général dans la pile) comparée à la solution
> moins jolie mais plus efficace itérative.
Pas d'accord : si on demande à quelqu'un la definition intuitive qu'il a de
la factorielle, il ne te diras pas
0!=1
n!=n*(n-1)!
Mais n!=1*2*3*........*n (faudrai faire un sondage, mais je crois que je ne
m'engage pas beaucoup)
Donc le programme le plus simple à comprendre est à mon gout le programme
iteratif, celui qui suit au plus proche la "vision" que l'on a de la
factorielle
Jean-Loup GUILLAUME
Il n'a parle que d'aspect esthetique, pas d'intuition. Meme si je suis
d'accord sur le principe.
> Mais n!=1*2*3*........*n (faudrai faire un sondage, mais je crois que je ne
> m'engage pas beaucoup)
>
> Donc le programme le plus simple à comprendre est à mon gout le programme
> iteratif, celui qui suit au plus proche la "vision" que l'on a de la
> factorielle
Comme pour la fonction d'Ackermann :)
Vincent Lascaux
"Jean-Loup GUILLAUME" <guil...@liafa.jussieu.fr> a écrit dans le message
news: 3AD3046D...@liafa.jussieu.fr...
> > Donc le programme le plus simple à comprendre est à mon gout le
programme
> > iteratif, celui qui suit au plus proche la "vision" que l'on a de la
> > factorielle
>
> Comme pour la fonction d'Ackermann :)
J'aimerais bien rencontrer quelqu'un qui a une vision "intuitive" de la
fonction d'Ackerman !
Yann Villessuzanne
> La solution recursive est plus elegante mais consomme bcp de temps et de
> mémoire (appels récursifs de fonctions dont il faut mémoriser les paramètres
> et les adresses mémoire, en général dans la pile) comparée à la solution
> moins jolie mais plus efficace itérative.
La récursion dite terminale n'est pas plus lente que les itérations ; le
contexte n'est pas empilé à chaque appel, mais écrasé.
En caml, la factorielle variante 'récusion terminale' s'écrit :
# let fact =
let rec f x = function 1 -> x | k -> f (k*x) (k-1)
in f 1;;
val fact : int -> int = <fun>
Vincent Lascaux
"Yann Villessuzanne" <vill...@clipper.ens.fr> a écrit dans le message news:
9av50s$55h$1...@nef.ens.fr...
> "Jaap de Haan" , dans le message (fr.sci.maths:54857), a écrit :
> contexte n'est pas empilé à chaque appel, mais écrasé.
>
> En caml, la factorielle variante 'récusion terminale' s'écrit :
>
> # let fact =
> let rec f x = function 1 -> x | k -> f (k*x) (k-1)
> in f 1;;
> val fact : int -> int = <fun>
Il faut se prendre la tête en moyenne combien de fois plus de temps que pour
un algorithme recursif sur ce genre de truc ?
Je pense que le principal interet de la recursivité, c'est d'utiliser une
pile (la pile d'appel) déjà programmée, et donc de s'epargner du travail. Le
second interet est sans aucun doute la clarté de la fonction recursive.
Dans cet exemple, on voit qu'on n'a pas besoin de la pile pour calculer une
factorielle (en effet, avec cette "astuce" on parvient à s'en passer). De
plus cet fonction est tres peu claire par rapport à l'iterative. Pourquoi
alors s'entêter à faire du recursif ??
(Ceci dit, je trouve l'astuce remarquable)
Julien BERNET
> > En caml, la factorielle variante 'récusion terminale' s'écrit :
> >
> > # let fact =
> > let rec f x = function 1 -> x | k -> f (k*x) (k-1)
> > in f 1;;
> > val fact : int -> int = <fun>
>
> Il faut se prendre la tête en moyenne combien de fois plus de temps que pour
> un algorithme recursif sur ce genre de truc ?
Ça dépend comment tu penses ... je peux admettre que dans le cadre
d'un langage impératif pur et dur, l'emploi d'une méthode itérative
est souvent plus naturel (cela dit, les versions itératives d'un certain
nombre d'algorithmes sont parfaitement incompréhensibles, penses aux
parcours d'arbres ...). Si par contre tu exprimes tes algorithmes dans
un paradigme fonctionnel (a la lisp), tout devient plus facile en récursif.
> Je pense que le principal interet de la recursivité, c'est d'utiliser une
> pile (la pile d'appel) déjà programmée, et donc de s'epargner du travail. Le
> second interet est sans aucun doute la clarté de la fonction recursive.
> Dans cet exemple, on voit qu'on n'a pas besoin de la pile pour calculer une
> factorielle (en effet, avec cette "astuce" on parvient à s'en passer). De
> plus cet fonction est tres peu claire par rapport à l'iterative. Pourquoi
> alors s'entêter à faire du recursif ??
Parce que qui dit itérations dit effets de bord (i.e. modification
physique du contenu d'une variable), et qui dit effets de bord dit en
général embrouilles (opinion personnelle que je partage avec
moi-même). Je maintiens qu'une fonction qui modifie une structure de
données pour exprimer son résultat est beaucoup plus dure à concevoir
correctement (et à utiliser sans problèmes) qu'une fonction qui
retourne une nouvelle structure. Cela dit, dans le cas de la
factorielle, les structures de données sont simplissimes.
> (Ceci dit, je trouve l'astuce remarquable)
Elle est utilisable dans la majorité des cas (il suffit de coller un
accumulateur dans les paramètres de la fonction).
Et le plus beau, c'est qu'il existe des algorithmes qui étant donné un
algorithme récursif en donnent une version itérative
(incompréhensible, ça va de soit).
Julien Bernet.
Julien BERNET
> Pas d'accord : si on demande à quelqu'un la definition intuitive qu'il a de
> la factorielle, il ne te diras pas
> 0!=1
> n!=n*(n-1)!
>
> Mais n!=1*2*3*........*n (faudrai faire un sondage, mais je crois que je ne
> m'engage pas beaucoup)
D'un autre côté, un certain nombre de personnes seront génées par les
points de suspension qu'implique la définition impérative. Une
définition par induction s'impose si on veut être parfaitement
rigoureux. En conclusion, si la version récursive défie l'intuition,
la version itérative défie la rigueur ...
Julien Bernet.
Vincent Lascaux
"Julien BERNET" <ber...@deathly.labri.u-bordeaux.fr> a écrit dans le message
news: wn7eluy...@deathly.labri.u-bordeaux.fr...
> "Vincent Lascaux" <vincent...@free.fr> writes:
>
> > > En caml, la factorielle variante 'récusion terminale' s'écrit :
> > >
> > > # let fact =
> > > let rec f x = function 1 -> x | k -> f (k*x) (k-1)
> > > in f 1;;
> > > val fact : int -> int = <fun>
> >
> > Il faut se prendre la tête en moyenne combien de fois plus de temps que
pour
> > un algorithme recursif sur ce genre de truc ?
>
> Ça dépend comment tu penses ... je peux admettre que dans le cadre
> d'un langage impératif pur et dur, l'emploi d'une méthode itérative
> est souvent plus naturel (cela dit, les versions itératives d'un certain
> nombre d'algorithmes sont parfaitement incompréhensibles, penses aux
> parcours d'arbres ...). Si par contre tu exprimes tes algorithmes dans
> un paradigme fonctionnel (a la lisp), tout devient plus facile en
récursif.
Tout à fait d'accord pour le parcours d'arbre, mais je pense que c'est du au
fait qu'il faut necessairement utiliser une pile pour le faire de facon
iterative (ou existe-t-il un autre moyen sans pile ? j'en doute).
L'utilisation d'un algorithme recursif permet de s'affranchir de
l'implementation de cette pile (qui l'est déjà par le langage). D'où la
simplicité.
>
> > Je pense que le principal interet de la recursivité, c'est d'utiliser
une
> > pile (la pile d'appel) déjà programmée, et donc de s'epargner du
travail. Le
> > second interet est sans aucun doute la clarté de la fonction recursive.
> > Dans cet exemple, on voit qu'on n'a pas besoin de la pile pour calculer
une
> > factorielle (en effet, avec cette "astuce" on parvient à s'en passer).
De
> > plus cet fonction est tres peu claire par rapport à l'iterative.
Pourquoi
> > alors s'entêter à faire du recursif ??
>
> Parce que qui dit itérations dit effets de bord (i.e. modification
> physique du contenu d'une variable), et qui dit effets de bord dit en
> général embrouilles (opinion personnelle que je partage avec
> moi-même). Je maintiens qu'une fonction qui modifie une structure de
> données pour exprimer son résultat est beaucoup plus dure à concevoir
> correctement (et à utiliser sans problèmes) qu'une fonction qui
> retourne une nouvelle structure. Cela dit, dans le cas de la
> factorielle, les structures de données sont simplissimes.
La reflexion sur un probleme m'ammene souvent à me dire "Pour chacun des
trucs je fais ca..." plutot que "J'applique l'algo pour les trucs d'avant et
je le fais ensuite pour celui ci". J'avoue que pour des algorithmes ou une
pile s'imposerai dans l'implementation iterative, je trouve plus vite
l'algorithme recursif, mais pour les autres, c'est l'algorithme iteratif qui
me vient à l'idée. Pour la factorielle, je me dis "pour chaque entier de
1->n, je les multiplie" (en gros) et je ne me dis pas "je multiplie le
resultat de (n-1)! par n".
Je pense qu'on ne doit pas avoir la même facon de penser...
Autre exemple : si tu dois trouver le maximum d'un ensemble d'element,
vas-tu faire un algorithme recursif (basé sur le fait qu'on connais le
maximum de deux entiers) ou iteratif ?
>
> > (Ceci dit, je trouve l'astuce remarquable)
>
> Elle est utilisable dans la majorité des cas (il suffit de coller un
> accumulateur dans les paramètres de la fonction).
> Et le plus beau, c'est qu'il existe des algorithmes qui étant donné un
> algorithme récursif en donnent une version itérative
> (incompréhensible, ça va de soit).
Il suffit de rajouter la pile et tout va bien (en tout cas pour tous les
algorithmes recursifs que j'ai vu)
>
> Julien Bernet.
Jean-Loup GUILLAUME
> La reflexion sur un probleme m'ammene souvent à me dire "Pour chacun des
> trucs je fais ca..." plutot que "J'applique l'algo pour les trucs d'avant et
> je le fais ensuite pour celui ci". J'avoue que pour des algorithmes ou une
> pile s'imposerai dans l'implementation iterative, je trouve plus vite
> l'algorithme recursif, mais pour les autres, c'est l'algorithme iteratif qui
> me vient à l'idée. Pour la factorielle, je me dis "pour chaque entier de
> 1->n, je les multiplie" (en gros) et je ne me dis pas "je multiplie le
> resultat de (n-1)! par n".
> Je pense qu'on ne doit pas avoir la même facon de penser...
> Autre exemple : si tu dois trouver le maximum d'un ensemble d'element,
> vas-tu faire un algorithme recursif (basé sur le fait qu'on connais le
> maximum de deux entiers) ou iteratif ?
En fait pour moi, ca depend du langage que j'utilise. En C je ferais un algo
iteratif pour le max, par contre en Caml, je passe immediatement au recursif
(bien que l'on puisse de l'iteratif avec).
Vincent Lascaux
"Gilles Robert" <rob...@math.u-bordeaux.fr> a écrit dans le message news:
slrn9dbbk1...@nicolette.math.u-bordeaux.fr...
> Vincent Lascaux disait :
> >La reflexion sur un probleme m'ammene souvent à me dire "Pour chacun des
> >trucs je fais ca..." plutot que "J'applique l'algo pour les trucs d'avant
et
> >je le fais ensuite pour celui ci".
>
> intervenir.
>
> >J'avoue que pour des algorithmes ou une pile s'imposerai dans
> >l'implementation iterative, je trouve plus vite l'algorithme recursif,
> >mais pour les autres, c'est l'algorithme iteratif qui me vient à l'idée.
>
> a autant que tu veux) ne se prètera pas forcément à un traitement
itératif.
>
> >Pour la factorielle, je me dis "pour chaque entier de 1->n, je les
> >multiplie" (en gros) et je ne me dis pas "je multiplie le resultat de
> >(n-1)! par n".
>
> tu préfères celle qui te semble plus "parlante".
>
> Si tu dois compter (par exemple, j'en ai eu besoin récemment) le nombre
> d'arbres dirigés à n feuilles numérotées de 1 à n. Penseras-tu d'emblée
> à un programme itératif ou à un programme récursif ?
> --
Je penserais probablement d'emblé à me documenter sur ce qu'est un arbre
dirigé ;)
Vincent Lascaux
> Vincent Lascaux disait :
> >> Si tu dois compter (par exemple, j'en ai eu besoin récemment) le nombre
> >> d'arbres dirigés à n feuilles numérotées de 1 à n. Penseras-tu d'emblée
> >> à un programme itératif ou à un programme récursif ?
> >> --
> >Je penserais probablement d'emblé à me documenter sur ce qu'est un arbre
> >dirigé ;)
>
> sauf que les arètes ont une direction. Ca revient à choisir une "racine"
> à l'arbre vers laquelle "convergent" les arètes.
>
> Alors, récursif ou itératif ?
En effet, recursif (evidemment). Mais je pense à un algo recursif parceque
je veux utiliser une pile, parceque je me dis qu'indeniablement je vais etre
oblige de faire le travail pour de plus petits arbres, et *apres*, je
concluerais. Il ne me viendrais pas (je pense, mais je sens que tu vas
encore trouver un contre exemple ;)) à l'idée d'implementer un algorithme de
facon recursive si son implementation iterative ne demande pas de pile
(comme c'est le cas pour factorielle, max ou d'autres).
J'emets quand même une petite limitation à mes propos : tous ceci depend
bien evidemment de la structure de donnée et du langage (il est generalement
scuicidaire d'ecrire un algorithme utilisant des listes en Caml de facon
iterative !)
Vincent Lascaux
> Vincent Lascaux disait :
> >à l'idée d'implementer un algorithme de facon recursive si son
> >implementation iterative ne demande pas de pile
> >(comme c'est le cas pour factorielle, max ou d'autres).
>
> d'utiliser un algorithme récursif sur un problème résoluble de manière
> itérative". Nous sommes encore d'accord, encore faut-il connaitre cette
> solution itérative.
Je crois que le probleme vient des termes employés : il n'y a pas
d'algorithme iteratif ou recursifs, mais seulement une implementation
iterative ou recursive d'un algorithme.
L'algorithme du calcul du Cnk par le triangle de Pascal (par exemple) peut
aussi bien etre implementé recursivement (beurk) qu'iterativement (bien !
:))
Le fait est que c'est la version iterative qui me saute à l'esprit, parceque
l'algorithme ne necessite pas de pile. On peut parcourir le triangle de
facon lineaire (si ce que je dis a un sens) contrairement à un arbre. On n'a
pas besoin d'avoir un memo à porté de la main sur lequel ecrire "Ne pas
oublier de calculer la ligne 12" vu que l'ordre de calcul des lignes est
tres simple. Avec un arbre, on est pratiquement obligé d'avoir un memo pour
ecrire "Aller regarder sur la branche de droite de l'arbre".
Michel Bovani
> Si je paraphrase, cela veut dire "il ne me viendrait pas à l'esprit
> d'utiliser un algorithme récursif sur un problème résoluble de manière
> itérative". Nous sommes encore d'accord, encore faut-il connaitre cette
> solution itérative.
Oui, exactement. Un bon exemple est le problème des tours de Hanoi (je
suppose que tout le monde connait). Conceptuellement, c'est récursif.
Je le traite tous les ans en td Maple.
Et j'ai une tour de hanoi en bois chez moi. L'autre jour quelqu'un m'a
demandé comment ça marchait. J'ai expliqué, puis j'ai voulu faire une démo.
Je me suis lamentablement planté. Je sais le programmer mais je ne sais pas
le résoudre (enfin, je sais en appliquant mon algo récursif mais c'est pas
très commode si on veut aller vite !).
Ceci dit ce problème possède une solution itérative élégante, mais faut
vraiment le triturer complètement et finir par le prendre complètement à
l'envers, et ça c'est pas le boulot du programmeur.
En gros pour programmer récursif, on n'a pas besoin de savoir résoudre le
problème, seulement de savoir comment on peut le résoudre...
Vincent Lascaux
"Michel Bovani" <michel...@wanadoo.fr> a écrit dans le message news:
B6FBC85B.115D1%michel...@wanadoo.fr...
Vincent Lascaux
"Michel Bovani" <michel...@wanadoo.fr> a écrit dans le message news:
B6FBC85B.115D1%michel...@wanadoo.fr...
algorithme ne peut pas etre intrinsequement recursif ou iteratif. Tout au
plus, il suggere une implementation recursive ou iterative. Pour moi les
programmes recursif et iteratif du calcul de la factorielle sont basés sur
le même algorithme (faire le produit des nombres).
Dans ton exemple, je pense que les deux versions recursives et
iteratives que tu evoques sont basés sur deux algorithmes differents.
L'implementation iterative de l'algorithme "connu" est : (en
(tres)pseudo-code)
Hanoy(n_,debut_,milieu_,fin_)
Stack CallStack;
CallStack.push(n_,debut_,milieu_,fin_);
while (not CallStack.isEmpty())
(n,debut,milieu,fin)=CallStack.pop();
if(n=1)
debut->fin
else
CallStack.push(n-1,debut,fin,milieu);
CallStack.push(1,debut,milieu,fin);
CallStack.push(n-1,milieu,debut,fin);
endif
endwhile
Qui est pratiquement le même que celui recursif :
Hanoy(n,debut,milieu,fin)
if(n=1)
debut->fin
else
Hanoy(n-1,debut,fin,milieu);
Hanoy(1,debut,milieu,fin);
Hanoy(n-1,milieu,debut,fin);
endif
endwhile
Michel Bovani
> La aussi je pense qu'il y a confusion dans les termes : je crois qu'un
> algorithme ne peut pas etre intrinsequement recursif ou iteratif. Tout au
> plus, il suggere une implementation recursive ou iterative. Pour moi les
> programmes recursif et iteratif du calcul de la factorielle sont basés sur
> le même algorithme (faire le produit des nombres).
> Dans ton exemple, je pense que les deux versions recursives et
> iteratives que tu evoques sont basés sur deux algorithmes differents.
> L'implementation iterative de l'algorithme "connu" est : (en
> (tres)pseudo-code)
Je suis pas trop d'accord. Pour moi si tu as besoin d'implémenter une pile
pour réaliser ton algorithme, il est conceptuellement récursif.
Tu implémentes itérativement un algo récursif, c'est tout.
Vincent Lascaux
> Le 12/04/01 21:42, Vincent Lascaux a écrit :
>
> > La aussi je pense qu'il y a confusion dans les termes : je crois qu'un
> > algorithme ne peut pas etre intrinsequement recursif ou iteratif. Tout
au
> > plus, il suggere une implementation recursive ou iterative. Pour moi les
> > programmes recursif et iteratif du calcul de la factorielle sont basés
sur
> > le même algorithme (faire le produit des nombres).
> > Dans ton exemple, je pense que les deux versions recursives et
> > iteratives que tu evoques sont basés sur deux algorithmes differents.
> > L'implementation iterative de l'algorithme "connu" est : (en
> > (tres)pseudo-code)
>
> Je suis pas trop d'accord. Pour moi si tu as besoin d'implémenter une pile
> pour réaliser ton algorithme, il est conceptuellement récursif.
> Tu implémentes itérativement un algo récursif, c'est tout.
Bon, alors dans ce cas l'algorithme de calcul de la factorielle est
conceptuellement iteratif (il n'y a pas besoin de pile). Nous sommes tous
d'accord qu'un algorithme dit "recursif" ne doit pas etre programmé de facon
iterative (sauf pour des raison d'efficacité ?), en tout cas pas pour des
raisons pedagogiques. Alors pourquoi choisir le calcul de la factorielle
facon recursive comme exemple pedagogique (c'est ce qui est enseigné dans
tous les cours d'info).
Antoine Chambert-Loir
Vincent Lascaux <vincent...@free.fr> wrote:
>Bon, alors dans ce cas l'algorithme de calcul de la factorielle est
>conceptuellement iteratif (il n'y a pas besoin de pile). Nous sommes tous
>d'accord qu'un algorithme dit "recursif" ne doit pas etre programmé de facon
>iterative (sauf pour des raison d'efficacité ?), en tout cas pas pour des
>raisons pedagogiques. Alors pourquoi choisir le calcul de la factorielle
>facon recursive comme exemple pedagogique (c'est ce qui est enseigné dans
>tous les cours d'info).
Mes souvenirs d'informatique sont un peu faibles, mais il
me semble qu'il y a une notion d'algorithme 'récursif terminal'
(en gros, l'auto-appel est en dernier) qui est équivalent
à un algorithme itératif (cf. le calcul de la factorielle)
mais aussi des algorithmes réellement récursifs qui ne sont
pas codables de manière itérative (je veux dire y compris
sans émuler une récursion via une pile, par exemple).
Dans un algo itératif, la mémoire utilisée par le programme
est uniformément bornée. Dans un algo récursif, on ne peut
pas prévoir ce qu'il utilisera.
(Y a-t-il un informaticien dans la salle ?)
--
Antoine Chambert-Loir o-o Institut de Mathématiques de Jussieu (Chevaleret)
Tel: 01 44 27 75 20 | Université Pierre et Marie Curie
Fax: 01 44 27 48 44 - Boite 247, 4 place Jussieu, F-75252 Paris Cedex 05
http://www.math.jussieu.fr/~chambert
Michel Bovani
> des algorithmes réellement récursifs qui ne sont
> pas codables de manière itérative (je veux dire y compris
> sans émuler une récursion via une pile, par exemple).
C'est un peu curieux parce que si on les implémente avec un langage qui
supporte la récustivité, on obtient bien après compilation du dit programme
un code binaire qui représente un algo itératif avec une pile, non ?
>
> (Y a-t-il un informaticien dans la salle ?)
C'est vrai que ça s'rait bien...
Vincent Lascaux
"Antoine Chambert-Loir" <cham...@borel1.institut.math.jussieu.fr> a écrit
dans le message news: 9b6bq0$hjv$1...@borel1.institut.math.jussieu.fr...
> In article <xApB6.474$KI4.9...@nnrp1.proxad.net>,
> Vincent Lascaux <vincent...@free.fr> wrote:
>
> Mes souvenirs d'informatique sont un peu faibles, mais il
> me semble qu'il y a une notion d'algorithme 'récursif terminal'
> (en gros, l'auto-appel est en dernier) qui est équivalent
> à un algorithme itératif (cf. le calcul de la factorielle)
> mais aussi des algorithmes réellement récursifs qui ne sont
> pas codables de manière itérative (je veux dire y compris
> sans émuler une récursion via une pile, par exemple).
Je suis presque sur qu'il est demontré que tout implementation recursive
peut l'être de facon iterative.
Pascal Bouvier
Itératif avec ou sans pile >:->
Plus sérieusement, l'itératif "intéressant" est celui qui se contente
d'un nombre fixe (et souvent petit) de cellules mémoires, déterminé
indépendament des données d'entrée de l'algo.
Dans ce cadre, certaines récursions ne sont pas "itérativables".
Tiens, il me revient (enfin, je ne suis pas sûr), qu'il a été déterminé
relativement récemment (<30 ans) que la suite de fibonacci est "itérativable"
Pour mémoire, la suite de fibonacci :
U0, U1 étant donnés
Un = Un-1 + Un-2 (n>=2)
Si je dis des c*nneries et/ou si quelqu'un a la version itérative de l'algo,
peut-être pourra-t-il nous le poster ici ? je lui en serait très content
d'avance.
--
Pascal
Jean-Loup GUILLAUME
> relativement récemment (<30 ans) que la suite de fibonacci est "itérativable"
> Pour mémoire, la suite de fibonacci :
> U0, U1 étant donnés
> Un = Un-1 + Un-2 (n>=2)
>
> Si je dis des c*nneries et/ou si quelqu'un a la version itérative de l'algo,
> peut-être pourra-t-il nous le poster ici ? je lui en serait très content
> d'avance.
A froid, un algo en pseudo-rien du tout :
fiboiter(n, U0, U1) {
var ui, ui+1 et ui+2,
Initialement ui=Uo ; ui+1=U1
Si n<=2 exit(JOKE);
repeter n-1 fois
ui+2=ui+ui+1;
ui=ui+1;
ui+1=ui+2;
fin
retourner ui+1
}
Pascal Bouvier
Effectivement j'ai bien dit une c*nnerie :-) .
J'ai du confondre avec une autre suite/série, mais ça ne me revient
plus du tout... Peut-être faut il qu'il y ait plusieurs récursivites,
du style Ackermann ?
--
Pascal
Olivier Miakinen
>
> Tiens, il me revient (enfin, je ne suis pas sûr), qu'il a été déterminé
> relativement récemment (<30 ans) que la suite de fibonacci est "itérativable"
> Pour mémoire, la suite de fibonacci :
> U0, U1 étant donnés
> Un = Un-1 + Un-2 (n>=2)
Je crois que dans ce cas on a même un résultat plus fort: on peut
calculer Un directement, en passant par les réels (la formule fait
intervenir la puissance n-ième du nombre d'or sijeun'mabuz).
--
Halte aux abus du mail : <http://marc.herbert.free.fr/mail/>
Mais aussi: <http://www.cict.fr/net/ErreursMel.html>
Au fait, merci de ne pas doubler par mail une réponse faite dans les
news, et evitez de m'envoyer des fichiers en formats propriétaires.
Michel Bovani
>>
>> fiboiter(n, U0, U1) {
>> var ui, ui+1 et ui+2,
>> Initialement ui=Uo ; ui+1=U1
>> Si n<=2 exit(JOKE);
>> repeter n-1 fois
>> ui+2=ui+ui+1;
>> ui=ui+1;
>> ui+1=ui+2;
>> fin
>> retourner ui+1
>> }
>
> Effectivement j'ai bien dit une c*nnerie :-) .
Si j'ai le droit de remuer un peu le fer... :))
Pour toutes les suites récurrentes linéaires, on sait exprimer Un en
fonction de n : il y a donc un algotithme qui n'est même pas itéraitf du
tout...
Gabriel Dos Reis
| Pas d'accord : si on demande à quelqu'un la definition intuitive qu'il a de
As-tu une définition de « définition intuitive » ?
-- Gaby
Gabriel Dos Reis
| "Yann Villessuzanne" <vill...@clipper.ens.fr> a écrit dans le message news:
| 9av50s$55h$1...@nef.ens.fr...
| > "Jaap de Haan" , dans le message (fr.sci.maths:54857), a écrit :
| > La récursion dite terminale n'est pas plus lente que les itérations ; le
| > contexte n'est pas empilé à chaque appel, mais écrasé.
| >
| > En caml, la factorielle variante 'récusion terminale' s'écrit :
| >
| > # let fact =
| > let rec f x = function 1 -> x | k -> f (k*x) (k-1)
| > in f 1;;
| > val fact : int -> int = <fun>
|
| Il faut se prendre la tête en moyenne combien de fois plus de temps que pour
| un algorithme recursif sur ce genre de truc ?
| Je pense que le principal interet de la recursivité, c'est d'utiliser une
| pile (la pile d'appel) déjà programmée, et donc de s'epargner du travail.
Son principale intérêt, c'est de conduire à des algorithmes
vérifiables par des moyens « élémentaires » (raisonnement par
récurrence) au lieu de faire intervenir des artilleries lourdes comme
la logique d'Hoare. Pourquoi faire simple si l'on peut faire compliqué
?
-- Gaby
Gabriel Dos Reis
| "Yann Villessuzanne" <vill...@clipper.ens.fr> a écrit dans le message news:
| 9av50s$55h$1...@nef.ens.fr...
| > "Jaap de Haan" , dans le message (fr.sci.maths:54857), a écrit :
| > La récursion dite terminale n'est pas plus lente que les itérations ; le
| > contexte n'est pas empilé à chaque appel, mais écrasé.
| >
| > En caml, la factorielle variante 'récusion terminale' s'écrit :
| >
| > # let fact =
| > let rec f x = function 1 -> x | k -> f (k*x) (k-1)
| > in f 1;;
| > val fact : int -> int = <fun>
|
| Il faut se prendre la tête en moyenne combien de fois plus de temps que pour
| un algorithme recursif sur ce genre de truc ?
| Je pense que le principal interet de la recursivité, c'est d'utiliser une
| pile (la pile d'appel) déjà programmée, et donc de s'epargner du travail.
Son principal intérêt, c'est de conduire à des algorithmes
Garulfo
particulierement laborieux a trouver par soit meme.
Disons qu'on ne s'interesse pas a la compilation ici mais a la maniere
d'exprimer un calcul le plus facilement possibles.
Avec un peu d'habitude et de connaissances mathematiques et des langages
fonctionnelles, il devient plus simple la plupart du temps de les
conceptualises en algo recursif plutot qu'iteratif. Du moins c'est ce
que je penses.
Michel Bovani a écrit :
Vincent Lascaux
"Michel Bovani" <michel...@wanadoo.fr> a écrit dans le message news:
B6FCFB74.11911%michel...@wanadoo.fr...
Et non... raté :)
On sait exprimer Un en fonction de n, mais il n'y a pas d'algorithme en
temps constant pour calculer Un (se serait trop beau). En effet,
l'expression de Un (en tout cas pour Fibonnacci) comporte des termes à la
puissance n, qu'on ne sait exprimer qu'au mieux en log(n) (si je ne m'abuse)
Vincent Lascaux
"Gabriel Dos Reis" <dos...@cmla.ens-cachan.fr> a écrit dans le message
news: flpuef7...@sel.cmla.ens-cachan.fr...
Quand je dis definition intuitive, je veux parler de "la definition que les
gens ont en tête"; je veux parler de la facon dont une personne expliquerais
ce qu'est la factorielle à une autre de la facon la plus comprehensible
possible...
Gabriel Dos Reis
Et qu'est-ce qui te faire croire que la définition récursive n'est ni
compréhensible, ni ce que des gens ont en tête (la communauté
fonctionnelle est certainement disposée à penser spontanément en
récursif) ?
-- Gaby
Vincent Lascaux
Je m'appuie (à tord je le sais) sur un seul exemple, mais qui represente
beaucoup pour moi : moi ;)
Je n'ai pas dis que la definition intuitive n'était pas comprehensible, mais
seulement qu'elle etait à un niveau d'abstraction au dessus, qu'elle etait
*moins* comprehensible. Pour ma part, si on me donne une fonction recursive
telle que la factorielle, je fais toujours un petit exercice de "conversion"
pour aboutir (dans ma tete) à une vision iterative de la fonction (par
iterative, j'entends avec des sommes, des produits....)
Julien BERNET
> Tout à fait d'accord pour le parcours d'arbre, mais je pense que c'est du au
> fait qu'il faut necessairement utiliser une pile pour le faire de facon
> iterative (ou existe-t-il un autre moyen sans pile ? j'en doute).
Sisisi, ça existe. Exemple de parcours en profondeur infixe sur un
arbre binaire :
p <- raçine
dir <- gauche
Tant que VRAI
Si dir == gauche
alors Si p a un fils gauche
alors p <- fils_gauche(p)
sinon TRAITEMENT(p)
dir <- haut
Si dir == haut
alors Si p est différent de la raçine
alors q <- père(p)
Si p == fils_gauche(q)
alors TRAITEMENT(q)
dir <- droite
p <- q
sinon FIN
Si dir == droite
alors Si p a un fils droit
alors p <- fils_droit(p)
dir <- gauche
sinon TRAITEMENT(p)
dir <- haut
Voila, il y a peut-etre plus simple, mais je ne vois pas. En tout cas,
je préfère la version récursive. Tout ça pour dire que le paradigme à
employer dépend à mon sens beaucoup du type de problème, et un peu des
goùts de chacun.
Julien
Jean-Loup GUILLAUME
Et une version sans un pointeur sur le pere d'un sommet ? C'est plus dur non.
Thomas Thiriez
> "Vincent Lascaux" <vincent...@free.fr> writes:
>
>
>> Tout à fait d'accord pour le parcours d'arbre, mais je pense que
> c'est du au
>> fait qu'il faut necessairement utiliser une pile pour le faire de
> facon
>> iterative (ou existe-t-il un autre moyen sans pile ? j'en doute).
>
> Sisisi, ça existe. Exemple de parcours en profondeur infixe sur un
> arbre binaire :
Mais dans ce cas, il est nécessaire que tu puisse remonter dans l'arbre.
Chaque feuille doit pointer vers son parent.
Dans la version récursive, la pile sert justement à remonter.
Thomas
Julien BERNET
Oups, effectivement, on a besoin de trop d'information, ce qui revient
à émuler une pile (en conservant la liste des sommets parcourus en
descendant). Il me semblait pourtant qu'on pouvait faire ça en
stockant une information de taille constante entre chaque itération
?...
Avis aux amateurs.
Crodialement.
Julien Bernet
Mathieu
hehehe tu ferais mieux de travailler pour les mines msieur Vincent !
allez à pluche
Mathieu (le crétin de MP1)
"Vincent Lascaux" <vincent...@free.fr> a écrit des bétises dans le
message news: MwIC6.882$qM3.1...@nnrp6.proxad.net...
Jean Rouquette
> *moins* comprehensible. Pour ma part, si on me donne une fonction
recursive
> telle que la factorielle, je fais toujours un petit exercice de
"conversion"
> pour aboutir (dans ma tete) à une vision iterative de la fonction (par
> iterative, j'entends avec des sommes, des produits....)
Comment définis- tu correctement simplement et sans récursivité : "un
ancêtre"
Récursivement : le père ou la mère ou un ancêtre du père ou un ancêtre de
la mère.
Jean Rouquette
Vincent Lascaux
"Jean Rouquette" <jd...@lycee-la-fontaine.org> a écrit dans le message news:
9dbe0t$2vr8$1...@news5.isdnet.net...
>
>
>
>
> > *moins* comprehensible. Pour ma part, si on me donne une fonction
> recursive
> > telle que la factorielle, je fais toujours un petit exercice de
> "conversion"
> > pour aboutir (dans ma tete) à une vision iterative de la fonction (par
> > iterative, j'entends avec des sommes, des produits....)
>
>
> Comment définis- tu correctement simplement et sans récursivité : "un
> ancêtre"
>
> Récursivement : le père ou la mère ou un ancêtre du père ou un ancêtre de
> la mère.
Franchement, la notion que j'ai n'est toujours pas recursive. Même si pour
formaliser, je suis d'accord qu'il faut en passer par là, si tu me dis : on
defini la relation être un ancetre par "etre le pere ou la mere ou un
ancetre du pere ou un ancetre du pere", je pense tout de suite "humm, donc
etre au dessus dans l'arbre généalogique" (je pense que cette definition
correspond à une viosion plus iterative, plus global aussi). J'avoue aussi
que pour des definitions plus abstraites (genre probleme de maths) je laisse
rapidement tomber et me debrouille sans avoir une veritable idée "iterative"
de la notion, mais dans ce cas je n'ai pas vraiment bien saisi tout le
concept.
Vincent Lascaux
"Mathieu" <to...@toto.fr> a écrit dans le message news:
9c3kg6$qhg$1...@wanadoo.fr...
Chat lu, chat va ?
D'abord je fais ce que je veux möa
Vincent (crétin peut etre, mais en MP * lui !)