Chemin à parcourir de la récursivité à l'itération

349

J'ai utilisé beaucoup de récursivité sur 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 problèmes de mémoire / vitesse.

Donc, quelque part dans un passé très lointain, je suis allé essayer de trouver s'il existait un "modèle" ou un moyen manuel de transformer une approche récursive commune de l'itération et je n'ai rien trouvé. Ou du moins rien dont je me souvienne que cela aiderait.

  • Existe-t-il des règles générales?
  • Y a-t-il un "modèle"?
Gustavo Carreno
la source
4
J'ai trouvé cette série informative: blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
orionrush

Réponses:

334

Habituellement, je remplace un algorithme récursif par un algorithme itératif en poussant les paramètres qui seraient normalement passés à la fonction récursive sur une pile. En fait, vous remplacez la pile de programmes par l'une des vôtres.

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 conserver l'ordre des appels, vous devez les ajouter dans l'ordre inverse à la pile:

foo(first);
foo(second);

doit être remplacé par

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

Edit: L'article Stacks and Recursion Elimination (ou le lien Article Backup ) donne plus de détails à ce sujet.

David Segonds
la source
4
Si vous remplacez votre pile par un son de file d'attente, cela ne résout-il pas le problème de l'inversion de l'ordre d'ajout?
SamuelWarren
2
J'ai travaillé sur papier et ce sont deux choses différentes. Si vous inversez l'ordre dans lequel vous les avez ajoutés, cela vous fait avancer comme d'habitude, mais votre traversée est toujours une recherche en profondeur. Mais si vous changez le tout en file d'attente maintenant, vous effectuez une traversée en largeur plutôt qu'en profondeur.
pete
1
Je l'ai fait récemment de manière générale, en remplaçant ma fonction de visite de noeud (node)->()par (node)->[actions]où se trouve l'action () -> [actions]. Ensuite, à l'extérieur, il vous suffit de sortir une action / continuation de la pile, de l'appliquer / l'exécuter, de pousser les actions qu'elle a renvoyées sur la pile dans l'ordre inverse et de répéter. Traversées contingentes / complexes, vous capturez simplement ce qui aurait été des variables de pile locales dans des pointeurs comptés par référence que vous fermez dans vos thunks, puis les thunks suivants peuvent dépendre des résultats des sous-traversées précédentes, etc.
2015
6
Parfois, nous évitons la récursivité afin d'éviter le stackoverflow. Mais le maintien de notre propre pile entraînera également un débordement de pile. Alors pourquoi voulons-nous implémenter la récursivité avec notre propre pile?
Zhu Li
8
@ZhuLi Si nous utilisons, newnous pouvons créer un objet sur le tas au lieu de la pile. Contrairement à la pile, le tas n'a pas de restrictions de mémoire. Voir gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html
yuqli
77

Vraiment, la façon la plus courante de le faire est de conserver votre propre pile. Voici une fonction de tri rapide récursif en C:

void quicksort(int* array, int left, int right)
{
    if(left >= right)
        return;

    int index = partition(array, left, right);
    quicksort(array, left, index - 1);
    quicksort(array, index + 1, right);
}

Voici comment nous pourrions le rendre itératif en conservant notre propre pile:

void quicksort(int *array, int left, int right)
{
    int stack[1024];
    int i=0;

    stack[i++] = left;
    stack[i++] = right;

    while (i > 0)
    {
        right = stack[--i];
        left = stack[--i];

        if (left >= right)
             continue;

        int index = partition(array, left, right);
        stack[i++] = left;
        stack[i++] = index - 1;
        stack[i++] = index + 1;
        stack[i++] = right;
    }
}

De toute évidence, cet exemple ne vérifie pas les limites de la pile ... et vous pouvez vraiment dimensionner la pile en fonction du pire des cas, compte tenu des valeurs gauche et droite. Mais vous avez l'idée.

bobwienholt
la source
1
Des idées sur la façon de déterminer la pile maximale à allouer pour une récursivité particulière?
lexicalscope
@lexicalscope suppose que vous avez un algorithme récursif dans O(N) = O(R*L), où Lest la somme de la complexité "pour la couche r", par exemple dans ce cas, vous avez du O(N)travail à chaque étape pour faire les partitions, la profondeur récursive est O(R), c'est-à-dire le pire des cas O(N), le cas moyen O(logN)ici.
Caleth
48

Il semble que personne ne se soit demandé où la fonction récursive s'appelle plus d'une fois dans le corps et gère le retour à un point spécifique de la récursivité (c'est-à-dire non récursif-primitif). On dit que chaque récursivité peut être transformée en itération , il semble donc que cela devrait être possible.

Je viens de proposer un exemple C # de la façon de procéder. Supposons que vous ayez la fonction récursive suivante, qui agit comme une traversée de post-ordre, et que AbcTreeNode est un arbre à 3 aires 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();
            }


        }
T. Webster
la source
5
C'est vraiment utile, j'ai dû écrire une version itérative de reccurence qui s'évoque n-fois, grâce à votre post je l'ai fait.
Wojciech Kulik
1
Cela doit être le meilleur exemple que j'ai jamais vu d'émuler la récursivité de la pile d'appels pour les situations où plusieurs appels récursifs sont effectués dans la méthode. Bon travail.
CCS
1
Vous m'avez eu à "Il semble que personne n'ait abordé où la fonction récursive s'appelle plus d'une fois dans le corps et gère le retour à un point spécifique de la récursivité", puis j'ai déjà voté. OK, maintenant je vais lire le reste de votre réponse et voir si mon vote prématuré était justifié. (Parce que j'ai désespérément besoin de connaître la réponse à cela).
mydoghasworms
1
@mydoghasworms - Revenant à cette question après si longtemps, il m'a même fallu un moment pour me souvenir de ce que je pensais. J'espère que la réponse a aidé.
T. Webster
1
J'ai aimé l'idée de cette solution, mais cela m'a semblé déroutant. J'ai écrit une version simplifiée pour l'arbre binaire en python, peut-être que cela aidera quelqu'un à comprendre l'idée: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac
azurkin
33

Efforcez-vous de faire votre appel récursif Tail Recursion (récursion où la dernière instruction est l'appel récursif). Une fois que vous avez cela, le convertir en itération est généralement assez facile.

Chris Shaffer
la source
2
Récurisation de la
Liran Orevi
De nombreux interprètes (c'est-à-dire le schéma le plus connu) optimiseront bien la récursivité de la queue. Je sais que GCC, avec une certaine optimisation, fait une récursivité de queue (même si C est un choix étrange pour une telle optimisation).
new123456
19

Eh bien, en général, la récursivité peut être imitée comme une itération en utilisant simplement une variable de stockage. Notez que la récursivité et l'itération sont généralement équivalentes; l'un peut presque toujours être converti en l'autre. Une fonction récursive de queue est très facilement convertie en fonction itérative. Faites simplement de la variable accumulateur une variable locale et répétez au lieu de recurse. Voici un exemple en C ++ (C sans 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à.

coppro
la source
14

Même l'utilisation de stack ne convertira pas un algorithme récursif en itératif. La récursivité normale est une récursion basée sur la fonction et si nous utilisons la pile, elle devient alors une récursion basée sur la pile. Mais c'est toujours la récursivité.

Pour les algorithmes récursifs, la complexité spatiale est O (N) et la complexité temporelle est O (N). Pour les algorithmes itératifs, la complexité spatiale est O (1) et la complexité temporelle est O (N).

Mais si nous utilisons des choses empilées en termes de complexité reste la même. Je pense que seule la récursivité de la queue peut être convertie en itération.

ARC
la source
1
Je suis d'accord avec votre premier morceau, mais je pense que je comprends mal le deuxième paragraphe. Envisagez de cloner un tableau en copiant simplement l' copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];espace mémoire et la complexité temporelle sont tous deux O (N) en fonction de la taille des données, mais il s'agit clairement d'un algorithme itératif.
Ponkadoodle
13

L' article sur l' élimination des piles et de la récursivité capture l'idée d'externaliser le cadre de pile sur le tas, mais ne fournit pas un moyen simple et reproductible de convertir. En voici un.

Lors de la conversion en code itératif, il faut être conscient que l'appel récursif peut se produire à partir d'un bloc de code arbitrairement profond. Ce ne sont pas seulement les paramètres, mais aussi le point de revenir à la logique qui reste à exécuter et à l'état des variables qui participent aux conditions subséquentes, qui comptent. Vous trouverez ci-dessous un moyen très simple de convertir en code itératif avec le moins de modifications.

Considérez ce code récursif:

struct tnode
{
    tnode(int n) : data(n), left(0), right(0) {}
    tnode *left, *right;
    int data;
};

void insertnode_recur(tnode *node, int num)
{
    if(node->data <= num)
    {
        if(node->right == NULL)
            node->right = new tnode(num);
        else
            insertnode(node->right, num);
    }
    else
    {
        if(node->left == NULL)
            node->left = new tnode(num);
        else
            insertnode(node->left, num);
    }    
}

Code itératif:

// Identify the stack variables that need to be preserved across stack 
// invocations, that is, across iterations and wrap them in an object
struct stackitem 
{ 
    stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
    tnode *node; int num;
    int ra; //to point of return
};

void insertnode_iter(tnode *node, int num) 
{
    vector<stackitem> v;
    //pushing a stackitem is equivalent to making a recursive call.
    v.push_back(stackitem(node, num));

    while(v.size()) 
    {
        // taking a modifiable reference to the stack item makes prepending 
        // 'si.' to auto variables in recursive logic suffice
        // e.g., instead of num, replace with si.num.
        stackitem &si = v.back(); 
        switch(si.ra)
        {
        // this jump simulates resuming execution after return from recursive 
        // call 
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {
                // replace a recursive call with below statements
                // (a) save return point, 
                // (b) push stack item with new stackitem, 
                // (c) continue statement to make loop pick up and start 
                //    processing new stack item, 
                // (d) a return point label
                // (e) optional semi-colon, if resume point is an end 
                // of a block.

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;         
            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {
                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;
            }
        }

        v.pop_back();
    }
}

Remarquez comment la structure du code reste fidèle à la logique récursive et les modifications sont minimes, entraînant moins de bogues. A titre de comparaison, j'ai marqué les changements avec ++ et -. La plupart des nouveaux blocs insérés, à l'exception de v.push_back, sont communs à toute logique itérative convertie

void insertnode_iter(tnode *node, int num) 
{

+++++++++++++++++++++++++

    vector<stackitem> v;
    v.push_back(stackitem(node, num));

    while(v.size())
    {
        stackitem &si = v.back(); 
        switch(si.ra)
        {
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

------------------------

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;    

-------------------------

            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;

-------------------------

            }
        }

+++++++++++++++++++++++++

        v.pop_back();
    }

-------------------------

}
Chethan
la source
Cela m'a beaucoup aidé, mais il y a un problème: les stackitemobjets sont alloués avec une valeur de poubelle pour ra. Tout fonctionne toujours dans le cas le plus similaire, mais devrait rapar coïncidence être 1 ou 2, vous obtiendrez un comportement incorrect. La solution consiste à initialiser raà 0.
JanX2
@ JanX2, stackitemne doit pas être poussé sans initialisation. Mais oui, l'initialisation à 0 entraînerait des erreurs.
Chethan
Pourquoi les deux adresses de retour ne sont-elles pas définies sur l' v.pop_back()instruction à la place?
is7s
7

Recherchez "Style de passage de continuation" sur Google. Il existe une procédure générale de conversion vers un style récursif de queue; il existe également une procédure générale pour transformer les fonctions récursives de queue en boucles.

Marcin
la source
6

Juste tuer le temps ... Une fonction récursive

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

peut être converti en

void foo(Node* node)
{
    if(node == NULL)
       return;

    // Do something with node...

    stack.push(node->right);
    stack.push(node->left);

    while(!stack.empty()) {
         node1 = stack.pop();
         if(node1 == NULL)
            continue;
         // Do something with node1...
         stack.push(node1->right);             
         stack.push(node1->left);
    }

}
Tae-Sung Shin
la source
L'exemple ci-dessus est un exemple de dfs récursif à itératif sur l'arbre de recherche binaire :)
Amit
5

Généralement, la technique pour éviter le débordement de pile est pour les fonctions récursives est appelée technique de trampoline qui est largement adoptée par les développeurs Java.

Cependant, pour C # il y a un peu d'aide méthode ici qui transforme votre fonction récursive à itérative sans nécessiter à la logique de changement ou de rendre le code en compréhensible. C # est un langage tellement agréable que des choses incroyables sont possibles avec.

Il fonctionne en enveloppant des parties de la méthode par une méthode d'assistance. Par exemple, la fonction récursive suivante:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

Se transforme en:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}
naiem
la source
4

En pensant aux choses qui ont réellement besoin d'une pile:

Si nous considérons le modèle de récursivité comme:

if(task can be done directly) {
    return result of doing task directly
} else {
    split task into two or more parts
    solve for each part (possibly by recursing)
    return result constructed by combining these solutions
}

Par exemple, la tour classique de Hanoi

if(the number of discs to move is 1) {
    just move it
} else {
    move n-1 discs to the spare peg
    move the remaining disc to the target peg
    move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}

Cela peut être traduit en une boucle fonctionnant sur une pile explicite, en la reformulant comme suit:

place seed task on stack
while stack is not empty 
   take a task off the stack
   if(task can be done directly) {
      Do it
   } else {
      Split task into two or more parts
      Place task to consolidate results on stack
      Place each task on stack
   }
}

Pour la tour de Hanoi, cela devient:

stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
    task = stack.pop();
    if(task.size() = 1) {
        just move it
    } else {
        stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
        stack.push(new Task(1, task.from(), task.to(), task.spare()));
        stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
    }
}

Il y a ici une grande flexibilité quant à la façon dont vous définissez votre pile. Vous pouvez faire de votre pile une liste d' Commandobjets qui font des choses sophistiquées. Ou vous pouvez aller dans la direction opposée et en faire une liste de types plus simples (par exemple, une "tâche" pourrait être 4 éléments sur une pile de int, plutôt qu'un élément sur une pile de Task).

Tout cela signifie que la mémoire de la pile se trouve dans le tas plutôt que dans la pile d'exécution Java, mais cela peut être utile dans la mesure où vous avez plus de contrôle sur celle-ci.

svelte
la source
3

Un modèle à rechercher est un appel de récursivité à la fin de la fonction (ce qu'on appelle la récursion de queue). Cela peut facilement être remplacé par un certain temps. Par exemple, la fonction foo:

void foo(Node* node)
{
    if(node == NULL)
       return;
    // Do something with node...
    foo(node->left);
    foo(node->right);
}

se termine par un appel à foo. Cela peut être remplacé par:

void foo(Node* node)
{
    while(node != NULL)
    {
        // Do something with node...
        foo(node->left);
        node = node->right;
     }
}

ce qui élimine le deuxième appel récursif.

Andrew Stein
la source
3
Me semble toujours récursif ... :)
nathan
2
Eh bien, oui - mais c'est à moitié aussi récursif. Pour se débarrasser de l'autre récursion, il va falloir utiliser une autre technique ...
Mark Bessey
2

Une question qui avait été fermée en double de celle-ci avait une structure de données très spécifique:

entrez la description de l'image ici

Le nœud avait la structure suivante:

typedef struct {
    int32_t type;
    int32_t valueint;
    double  valuedouble;
    struct  cNODE *next;
    struct  cNODE *prev;
    struct  cNODE *child;
} cNODE;

La fonction de suppression récursive ressemblait à:

void cNODE_Delete(cNODE *c) {
    cNODE*next;
    while (c) {
        next=c->next;
        if (c->child) { 
          cNODE_Delete(c->child)
        }
        free(c);
        c=next;
    }
}

En général, il n'est pas toujours possible d'éviter une pile de fonctions récursives qui s'appellent plusieurs fois (voire une fois). Cependant, pour cette structure particulière, c'est possible. L'idée est d'aplatir tous les nœuds en une seule liste. Pour ce faire, placez le nœud actuel childà la fin de la liste de la ligne supérieure.

void cNODE_Delete (cNODE *c) {
    cNODE *tmp, *last = c;
    while (c) {
        while (last->next) {
            last = last->next;   /* find last */
        }
        if ((tmp = c->child)) {
            c->child = NULL;     /* append child to last */
            last->next = tmp;
            tmp->prev = last;
        }
        tmp = c->next;           /* remove current */
        free(c);
        c = tmp;
    }
}

Cette technique peut être appliquée à toute structure liée aux données qui peut être réduite à un DAG avec un ordre topologique déterministe. Les nœuds enfants actuels sont réorganisés de sorte que le dernier enfant adopte tous les autres enfants. Ensuite, le nœud actuel peut être supprimé et la traversée peut ensuite être itérée jusqu'à l'enfant restant.

jxh
la source
1

La récursivité n'est rien d'autre que le processus d'appel d'une fonction de l'autre seulement ce processus se fait en appelant une fonction par elle-même. Comme nous le savons, lorsqu'une fonction appelle l'autre fonction, la première fonction enregistre son état (ses variables) puis passe le contrôle à la fonction appelée. La fonction appelée peut être appelée en utilisant le même nom de variables ex fun1 (a) peut appeler fun2 (a). Lorsque nous appelons récursivement, rien de nouveau ne se produit. Une fonction s'appelle en passant le même type et similaire dans les variables de nom (mais évidemment les valeurs stockées dans les variables sont différentes, seul le nom reste le même). Mais avant chaque appel, la fonction enregistre son état et ce processus de sauvegarde se poursuit. L'ECONOMIE SE FAIT SUR UNE PILE.

MAINTENANT LA PILE ENTRE EN JEU.

Donc, si vous écrivez un programme itératif et enregistrez l'état sur une pile à chaque fois, puis que vous sortez les valeurs de la pile si nécessaire, vous avez réussi à convertir un programme récursif en programme itératif!

La preuve est simple et analytique.

En récursivité, l'ordinateur maintient une pile et en version itérative, vous devrez maintenir manuellement la pile.

Pensez-y, il suffit de convertir un programme récursif de recherche en profondeur (sur les graphiques) en un programme itératif dfs.

Bonne chance!

Ajay Manas
la source
1

Un autre exemple simple et complet de transformation de la fonction récursive en fonction itérative à l'aide de la pile.

#include <iostream>
#include <stack>
using namespace std;

int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }

struct Par
{
    int a, b;
    Par() : Par(0, 0) {}
    Par(int _a, int _b) : a(_a), b(_b) {}
};

int GCDIter(int a, int b)
{
    stack<Par> rcstack;

    if (b == 0)
        return a;
    rcstack.push(Par(b, a % b));

    Par p;
    while (!rcstack.empty()) 
    {
        p = rcstack.top();
        rcstack.pop();
        if (p.b == 0)
            continue;
        rcstack.push(Par(p.b, p.a % p.b));
    }

    return p.a;
}

int main()
{
    //cout << GCD(24, 36) << endl;
    cout << GCDIter(81, 36) << endl;

    cin.get();
    return 0;
}
L_J
la source
0

Une description approximative de la façon dont un système prend une fonction récursive et l'exécute à l'aide d'une pile:

Cela visait à montrer l'idée sans détails. Considérez cette fonction qui imprimerait les nœuds d'un graphique:

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

Par exemple graphique: A-> B A-> C show (A) afficherait B, A, C

Les appels de fonction signifient enregistrer l'état local et le point de continuation afin que vous puissiez revenir, puis sauter la fonction que vous souhaitez appeler.

Par exemple, supposons que show (A) commence à s'exécuter. L'appel de fonction sur la ligne 3. show (B) signifie - Ajouter un élément à la pile signifiant "vous devrez continuer à la ligne 2 avec le noeud d'état variable local = A" - Aller à la ligne 0 avec le noeud = B.

Pour exécuter du code, le système exécute les instructions. Lorsqu'un appel de fonction est rencontré, le système envoie les informations dont il a besoin pour revenir à l'endroit où il se trouvait, exécute le code de la fonction et, une fois la fonction terminée, affiche les informations indiquant où il doit aller pour continuer.

Rick Giuly
la source
0

Ce lien fournit quelques explications et propose l'idée de garder "emplacement" pour pouvoir se rendre à l'endroit exact entre plusieurs appels récursifs:

Cependant, tous ces exemples décrivent des scénarios dans lesquels un appel récursif est effectué un nombre fixe de fois. Les choses deviennent plus difficiles lorsque vous avez quelque chose comme:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}
eold
la source
0

Il existe un moyen général de convertir un parcours récursif en itérateur en utilisant un itérateur paresseux qui concatène plusieurs fournisseurs d'itérateurs (expression lambda qui renvoie un itérateur). Voir ma conversion de la traversée récursive en itérateur .

Dagang
la source
0

Mes exemples sont en Clojure, mais devraient être assez faciles à traduire dans n'importe quelle langue.

Étant donné cette fonction qui StackOverflows pour les grandes valeurs de n:

(defn factorial [n]
  (if (< n 2)
    1
    (*' n (factorial (dec n)))))

nous pouvons définir une version qui utilise sa propre pile de la manière suivante:

(defn factorial [n]
  (loop [n n
         stack []]
    (if (< n 2)
      (return 1 stack)
      ;; else loop with new values
      (recur (dec n)
             ;; push function onto stack
             (cons (fn [n-1!]
                     (*' n n-1!))
                   stack)))))

returnest défini comme:

(defn return
  [v stack]
  (reduce (fn [acc f]
            (f acc))
          v
          stack))

Cela fonctionne également pour les fonctions plus complexes, par exemple la fonction ackermann :

(defn ackermann [m n]
  (cond
    (zero? m)
    (inc n)

    (zero? n)
    (recur (dec m) 1)

    :else
    (recur (dec m)
           (ackermann m (dec n)))))

peut se transformer en:

(defn ackermann [m n]
  (loop [m m
         n n
         stack []]
    (cond
      (zero? m)
      (return (inc n) stack)

      (zero? n)
      (recur (dec m) 1 stack)

      :else
      (recur m
             (dec n)
             (cons #(ackermann (dec m) %)
                   stack)))))
divs1210
la source