la derecurcivation .

Voila je suis entrain de réviser l'algo et j'ai trouver un problème dans la derecurssivation j'ai chercher sur developpez.com et j'ai pas trouvée grande choses
Ou puis je trouver des exo ou du cours sur la derecurcivité

et merci ;)

Je ne sais pas si celà peut t'aider, mais en général, pour dérécursiver, on utilise une pile.

ou un while avec a l'interieur des conditions se modifiant a chaque tour...

Pour bien comprendre la récursion, cliquer ici. ;)


c'est quoi la dérecurcivation 8O ? ça a un rapport avec la récursion terminale ?

Citation:

---

Envoyé par pseudocode

c'est quoi la dérecurcivation 8O ? ça a un rapport avec la récursion terminale ?

---

Je pense pas, je dirais plutôt que c'est le fait de supprimer les appels récursifs de fonction en les remplaçant par des boucles et une pile pour stocker les variables d'environnement. Mais bon au final, on programme à la mimine l'effet des appels récursifs.

Citation:

---

Envoyé par ZZelle

Je pense pas, je dirais plutôt que c'est le fait de supprimer les appels récursifs de fonction en utilisant une pile et une boucle qui pioche/remplit la pile (au final, on programme à la mimine l'effet des appels récursifs).

---

Ah... ok. Dans ce cas, je suggere de trouver une documentation sur les appels de fonctions en C/C++ (heap, stack, function call,...)

Par contre, je ne sais pas ou trouver des cours (encore moins des exos) sur ce sujet. :koi:

comme je disais, a mon avis, sans passer jusqu'a des complications de heap, stack, et autres :P, juste des boucles avec reaffectations de variables et re-iterations....

puisque tout algo recursif peut se remplacer (ou remplacer) des series de boucles imbriquees...

Citation:

---

Envoyé par souviron34

comme je disais, a mon avis, sans passer jusqu'a des complications de heap, stack, et autres :P, juste des boucles avec reaffectations de variables et re-iterations....

puisque tout algo recursif peut se remplacer (ou remplacer) des series de boucles imbriquees...

---

Tu as dû être mal renseigné, dans sa forme la plus générale la récursion doit être simulé avec une pile, tout algorithme récursif ne peut pas être traduit en itératif aussi simplement qu'une récursion terminale. (ou alors tu veux dire des boucles imbriquées générés dynamiquement, mais c'est équivalent)

Bien sûr la récursion terminale est le cas trivial, aujourd'hui optimisé par pratiquement tous les compilateurs dignes de ce nom, il y a des cas plus complexes et plus intéressants.

--
Jedaï

je ne sais pas, mais la question posée par le PO m'apparaissait directement faire appel à "comment transformer une récursivité en non-récursif"..

Et, je suis pas vos subtilités sur terminal ou non, mais comme je le dit, des boucles imbriquées dont les indices varient dynamiquement me semblent , pou les cas que j'ai vu, être équivalentes... A la complexité près..

Mais si le but est de "dé-récursiver", ça me semble être l'approche par défaut à avoir, non ??

Citation:

---

Envoyé par pseudocode

Pour bien comprendre la récursion, cliquer ici. ;)

---

Ça m'énerve, je suis tombé dans le piège :zekill:

Citation:

---

Envoyé par pseudocode

Pour bien comprendre la récursion, cliquer ici. ;)

---

:king:

Citation:

---

Envoyé par souviron34

je ne sais pas, mais la question posée par le PO m'apparaissait directement faire appel à "comment transformer une récursivité en non-récursif"..

Et, je suis pas vos subtilités sur terminal ou non, mais comme je le dit, des boucles imbriquées dont les indices varient dynamiquement me semblent , pou les cas que j'ai vu, être équivalentes... A la complexité près..

---

C'est effectivement, je pense, ce qu'il veut faire. En revanche, pour remplacer des appels récursif, il faut, dans le cas général, remplacer la pile d'appel des fonctions par une autre structure de pile gérée "à la main" dans les boucles. Par exemples, si tu fais un parcours en profondeurs dans un arbre, s'il n'y a pas de lien d'un fils vers son père, il faudra à tout moment garder la pile des noeuds déjà visité pour pouvoir remonter dans l'arbre.

Et une récursion est dite terminale lorsque le résultat de l'appel récursif est directement renvoyé, sans être utilisé dans la fonction.

Par exemple

Code:

---

1 2 3

let rec fact n = if n = 0 then 1 else n*fact (n-1)

---

n'est pas récursif terminal car le résultat est réutilisé pour la multiplication alors que

Code:

---

1 2 3

let rec fact_bis n acc = if n = 0 then acc else fact_bis (n-1) (n*acc)

---

(appelle de la forme fact_bis n 1 pour calculer n!) est récursif terminal car on retourne directement le résultat de l'appel.

Un fonction récursive terminale est directement traduisible en une simple boucle, pas une récursive non-terminale.

Il faut voir que, dans le cas général, on ne peut pas rendre une fonction récursive non terminale terminale sans utiliser une structure de pile ad hoc.

je dois être un peu "épais", comme on dit ici, mais je vois pas de différence fondamentale entre les 2.... 8O

Par contre, je suis d'accord avec ce que tu disais au dessus, sauf que pour moi ce ne serait pas une pile mais un simple tableau....

Et donc totalement faisable (quoique compliqué) en boucles....

Si il n'y a pas de liens du fils vers le pere, il y en a quand meme du pere vers le fils....

Citation:

---

Envoyé par souviron34

je dois être un peu "épais", comme on dit ici, mais je vois pas de différence fondamentale entre les 2.... 8O

---

Cherche quelque chose sur la récursivité terminal sur le web alors :-)

Citation:

---

Par contre, je suis d'accord avec ce que tu disais au dessus, sauf que pour moi ce ne serait pas une pile mais un simple tableau....

---

Non, tu ne peux pas avoir un simple tableau car tu n'as aucune idée a priori du nombre d'appel que tu auras à faire, donc de la taille de ton tableau (après, si tu as un tableau de taille dynamique, c'est... une pile :-))

Citation:

---

Si il n'y a pas de liens du fils vers le pere, il y en a quand meme du pere vers le fils....

---

Euh... oui, sinon on aurait un peu de mal à parcourir l'arbre hein... mais je ne vois pas le rapport en l'occurence

Citation:

---

Envoyé par alex_pi

(après, si tu as un tableau de taille dynamique, c'est... une pile :-))

---

Ah bon ?

Je ne sais pas, pour moi c'est un tableau dynamique. Et c'est de ça dont je parlais....

(mais j'ai déjà dit que je n'ai jamais eu de formation en info)

Citation:

---

Envoyé par souviron34

Ah bon ?

Je ne sais pas, pour moi c'est un tableau dynamique. Et c'est de ça dont je parlais....

(mais j'ai déjà dit que je n'ai jamais eu de formation en info)

---

En réalité un tableau de taille dynamique est un moyen de simuler une pile, mais c'est plus "complexe". En ce qui concerne la suppression des appels récursif, une structure de pile (disons en gros comme un tableau de taille dynamique dans lequel on accède qu'au dernier élément ajouté) est suffisante

Je vois plusieurs methodes. Celles deja citees:
- la recursivite terminale est strictement equivalente a une boucle
- l'introduction d'accumulateur (la variable acc dans l'exemple d'alex_pi) permet de modifier certaines recursivites non terminales en recursivites terminales sous certaines hypotheses (associativite de l'operation faite -- notez que les multiplications sont faites dans un ordre different dans l'exemple d'alex_pi) ou avec des transformations additionnelles (essayer de remplacer la multiplication par une soustraction dans la factorielle et refaite l'exercice). Apres on revient au cas precedent.
- l'introduction de piles gerees explicitement

Et plus complexe et plus ad hoc: certains algorithmes peuvent etre modifies pour remplacer la pile par des modifications sur les donnees utilisees. Chercher par exemple comment un GC peut parcourir un graphe sans avoir besoin de place supplementaire.