Création de modèles pour convertir des algorithmes récursifs en algorithmes itératifs

Question

Y a-t-il des heuristiques générales, des astuces, des astuces ou des paradigmes de conception communs qui peuvent être utilisés pour convertir un algorithme récursif en algorithme itératif? Je sais que cela peut être fait, je me demande s'il y a des pratiques qui valent la peine d'être gardées à l'esprit.

Answer 1

Vous pouvez souvent conserver entièrement la structure originale d'un algorithme récursif, mais il faut éviter la pile, en utilisant la queue appelle et passe à continuation-passing, comme suggéré par this blog entry. (Je devrais vraiment cuire un meilleur exemple autonome.)

Answer 2

Un modèle est Tail Recursion:

Un appel de fonction est dite queue récursive s'il n'y a rien à faire après le retour de la fonction, sauf retourner sa valeur.

Wiki.

Answer 3

Jetez un oeil à ces liens pour des exemples de performance

Recursion VS Iteration (Looping) : Speed & Memory Comparison

et

Replace Recursion with Iteration

et

Recursion vs Iteration

Q: La version récursive est-elle généralement plus rapide? A: Non - il est généralement plus lent (en raison de la charge de maintenir 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 devons attendre jusqu'à ce que nous avons discuté arbres pour voir de très bons exemples ...)

Answer 4

une pratique courante est pour gérer une pile LIFO qui maintient une liste courante de ce « reste à faire » et de gérer tout le processus dans une boucle while qui continue jusqu'à ce que la liste est vide.
Avec ce modèle, ce qui serait un appel récursion dans le vrai modèle de récursion est remplacé par
- une poussée de « contexte » de la tâche en cours (en partie finie) sur la pile,
- une poussée de la nouvelle tâche (la un qui a incité la récursion) sur la pile
- et de "continuer" (ie sauter au début de) la boucle while. Près de la tête de la boucle, la logique affiche le dernier contexte inséré et commence à travailler sur cette base.

Effectivement cela "déplace" simplement les informations qui auraient autrement été conservées dans des empilements imbriqués dans la pile "système", dans un conteneur de pile géré par l'application. C'est une amélioration cependant, car ce conteneur de pile peut être alloué n'importe où (la limite de récursivité est typiquement liée aux limites de la pile "système"). Donc essentiellement le même travail est fait, mais la gestion explicite d'une "pile" permet que cela se fasse dans une construction de boucle unique plutôt que dans des appels récursifs.

Answer 5

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.

Vérifiez les articles suivants:

• Replacing Recursion With a Stack
• Stacks and Recursion Elimination (pdf)

Answer 6

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

Par exemple, la définition récursive norme générale de factoriel

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écursive de la queue. Il est le même que

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

Answer 7

Je commence généralement à partir du cas de base (chaque fonction récursive a un) et me frayer un chemin vers l'arrière, le stockage des résultats dans un cache (tableau ou Hashtable) si nécessaire.

Votre fonction récursive résout un problème en résolvant des sous-problèmes plus petits et en les utilisant pour résoudre l'instance du problème. Chaque sous-problème est également décomposé plus avant et ainsi de suite jusqu'à ce que le sous-problème soit si petit que la solution soit triviale (c'est-à-dire le cas de base). L'idée est de commencer par le cas de base (ou les cas de base) et de l'utiliser pour construire la solution pour des cas plus grands, puis les utiliser pour construire des cas encore plus gros et ainsi de suite, jusqu'à ce que tout le problème soit résolu. Cela ne nécessite pas de pile, et peut être fait avec des boucles.

Un exemple simple (en Python):

#recursive version 
def fib(n): 
    if n==0 or n==1: 
      return n 
    else: 
      return fib(n-1)+fib(n-2) 

#iterative version 
def fib2(n): 
    if n==0 or n==1: 
      return n 
    prev1,prev2=0,1 # start from the base case 
    for i in xrange(n): 
      cur=prev1+prev2 #build the solution for the next case using the previous solutions 
      prev1,prev2=cur,prev1 
    return cur