Modèles de conception pour convertir les algorithmes récursifs en algorithmes itératifs.

Question

Existe-t-il des heuristiques générales, des conseils, des astuces ou des paradigmes de conception communs qui peuvent être utilisés pour convertir un algorithme récursif en un algorithme itératif ? Je sais que c'est possible, mais je me demande s'il y a des pratiques à garder à l'esprit lors de cette opération.

Answer 1

Il est souvent possible de préserver entièrement la structure originale d'un algorithme récursif, tout en évitant la pile, en utilisant des appels de queue et en changeant pour continuation-passing comme le suggère cet article de blog . (Je devrais vraiment préparer un meilleur exemple autonome).

Answer 2

Une technique courante que j'utilise lorsque je suis en train de remplacer un algorithme récursif par un algorithme itératif est généralement d'utiliser une pile, en poussant les paramètres qui sont passés à la fonction récursive.

Consultez les articles suivants :

• Remplacer la récursion par une pile
• Piles et élimination des récursions (pdf)

Answer 3

Une pratique courante est pour gérer une pile LIFO qui garde une liste courante de ce qui "reste à faire". et de traiter l'ensemble du processus dans une boucle while qui se poursuit jusqu'à ce que la liste soit vide.
Avec ce modèle, ce qui serait un appel de récursion dans le vrai modèle de récursion est remplacé par
- une poussée du "contexte" de la tâche actuelle (partiellement terminée) sur la pile,
- une poussée de la nouvelle tâche (celle qui a provoqué la récursion) sur la pile
- et pour "continuer" (c'est-à-dire sauter au début de) la boucle while. Près de la tête de la boucle, la logique extrait le contexte le plus récemment inséré et commence à travailler sur cette base.

Effectivement cela ne fait que "déplacer" l'information qui auraient autrement été conservés dans des cadres de pile imbriqués sur la pile "système", vers un conteneur de pile géré par l'application. Il s'agit toutefois d'une amélioration, car ce conteneur de pile peut être alloué n'importe où (la limite de récursion est généralement liée aux limites de la pile "système"). Par conséquent, le travail effectué est essentiellement le même, mais la gestion explicite d'une "pile" permet de l'effectuer dans une seule construction de boucle plutôt que dans des appels récursifs.

Answer 4

Souvent, la récursion générale peut être remplacée par une récursion de queue, en collectant les résultats partiels dans un accumulateur et en le transmettant avec l'appel récursif. La récursion de queue est essentiellement itérative, l'appel récursif peut être implémenté comme un saut.

Par exemple, la définition générale récursive standard de la factorielle

factorial(n) = if n = 0 then 1 else n * factorial(n - 1)

peut être remplacé par

 factorial(n) = f_iter(n, 1)

et

 f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)

qui est récursif à la queue. C'est la même chose que

a = 1;
while (n != 0) {
    a = n * a;
    n = n - 1;
}
return a;

Answer 5

Jetez un coup d'œil à ces liens pour des exemples de performance

Récursion VS Itération (Looping) : Comparaison de la vitesse et de la mémoire

et

Remplacer la récursion par l'itération

et

Récursion et itération

Q : La version récursive est-elle généralement plus rapide ? R : Non, elle est généralement plus lente (en raison de la surcharge liée au maintien de la la pile)

  Q: Does the recursive version usually use less memory?
  A: No -- it usually uses more memory (for the stack).

  Q: Then why use recursion??
  A: Sometimes it is much simpler to write the recursive version (but

nous devrons attendre jusqu'à ce que nous ayons discuter des arbres pour voir de vrais bons exemples...)