Chemin à parcourir de récursivité pour itération

Question

J'ai utilisé la récursivité beaucoup de mes nombreuses années de programmation pour résoudre des problèmes simples, mais je suis pleinement conscient que, parfois, vous avez besoin d'itération en raison de la mémoire/des problèmes de vitesse.

Donc, quelque part dans le très lointain passé, je suis allé l'essayer et de trouver si il n'existait aucun "modèle" ou de texte-livre moyen de transformer une commune de la récursivité à l'approche de l'itération et n'a rien trouvé. Ou du moins rien que je me souvienne, il pourrait l'aider.

• Existe-il des règles générales?
• Est-il un "modèle"?

Answer 1

Habituellement, je l'ai remplacer un algorithme récursif par un algorithme itératif en poussant les paramètres qui devraient normalement être transmis à la fonction récursive sur une pile. En fait, vous êtes le remplacement de la pile du programme par l'un de vos propres.

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

Remarque: si vous avez plus d'un appel récursif à l'intérieur et que vous souhaitez préserver l'ordre des appels, vous devez les ajouter dans l'ordre inverse de la pile:

foo(first);
foo(second);

doit être remplacé par

stack.push(second);
stack.push(first);

Edit: L'article de Piles et de la Récursivité Élimination va plus de détails à ce sujet.

Answer 2

Vraiment, la façon la plus courante de le faire est de garder votre propre tapis. Voici une fonction de quicksort récursif dans C:

Voici comment nous pourrions rendre itérative en gardant notre propre pile :

Évidemment, cet exemple ne vérifie pas pile limites... et vraiment vous pourriez taille la pile basée sur le pire des cas donné à gauche et à droite des valeurs. Mais vous voyez l’idée.

Answer 3

Il semble que personne n'a pris en compte lorsqu'le récursive de la fonction s'appelle elle-même plus d'une fois dans le corps, et les poignées de revenir à un point spécifique de la récursivité (c'est à dire n'est pas primitive récursive). Il est dit que chaque récursion peut être transformé en itération, de sorte qu'il semble que ce devrait être possible.

Je suis juste venu avec un exemple en C# de comment faire cela. Supposons que vous disposez de la fonction récursive, qui agit comme un postorder de la traversée, et que AbcTreeNode est un 3-ary arbre avec des pointeurs a, b, c.

public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
        if (x != null) {
            AbcRecursiveTraversal(x.a, list);
            AbcRecursiveTraversal(x.b, list);
            AbcRecursiveTraversal(x.c, list);
            list.Add(x.key);//finally visit root
        }
}

La solution itérative:

        int? address = null;
        AbcTreeNode x = null;
        x = root;
        address = A;
        stack.Push(x);
        stack.Push(null)    

        while (stack.Count > 0) {
            bool @return = x == null;

            if (@return == false) {

                switch (address) {
                    case A://   
                        stack.Push(x);
                        stack.Push(B);
                        x = x.a;
                        address = A;
                        break;
                    case B:
                        stack.Push(x);
                        stack.Push(C);
                        x = x.b;
                        address = A;
                        break;
                    case C:
                        stack.Push(x);
                        stack.Push(null);
                        x = x.c;
                        address = A;
                        break;
                    case null:
                        list_iterative.Add(x.key);
                        @return = true;
                        break;
                }

            }


            if (@return == true) {
                address = (int?)stack.Pop();
                x = (AbcTreeNode)stack.Pop();
            }


        }

Answer 4

S’efforcer de rendre votre récursive appel Tail Recursion (récursivité où la dernière instruction est l’appel récursif). Une fois que vous avez, convertissant d’itération est généralement assez facile.

Answer 5

Eh bien, en général, la récursivité peut être imité que l'itération en utilisant simplement une variable. Notez que la récursivité et iteraction sont généralement équivalentes; on peut presque toujours être converti à l'autre. Une queue-fonction récursive est très facile de convertir un processus itératif. Juste faire de l'accumulateur variable locale, et de réitérer au lieu de répéter. Voici un exemple en C++ (C était pas pour l'utilisation d'un argument par défaut):

// tail-recursive
int factorial (int n, int acc = 1)
{
  if (n == 1)
    return acc;
  else
    return factorial(n - 1, acc * n);
}

// iterative
int factorial (int n)
{
  int acc = 1;
  for (; n > 1; --n)
    acc *= n;
  return acc;
}

Me connaissant, j'ai probablement fait une erreur dans le code, mais l'idée est là.