Comment passer de la récursion à l'itération
j'ai beaucoup utilisé la récursion 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, parfois dans le passé très lointain je suis allé pour essayer de trouver s'il existait un" modèle " ou un livre de texte façon de transformer une approche commune de récursion à l'itération et n'a rien trouvé. Ou du moins, rien dont je me souvienne ne pourrait m'aider.
- Sont il y a des règles générales?
- y a-t-il un"motif"?
19 réponses
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 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 Stacks and Recursion Elimination (ou Article Backup link ) va dans plus de détails sur ce sujet.
Vraiment, la façon la plus courante de le faire est de garder votre propre pile. Voici une fonction quicksort récursive 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 gardant 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;
}
}
évidemment, cet exemple ne vérifie pas les limites de la pile... et vraiment, vous pourriez dimensionner la pile en fonction du pire des cas étant donné les valeurs à gauche et et à droite. Mais vous obtenez l'idée.
il semble que personne n'a abordé où la fonction récursive s'appelle plus d'une fois dans le corps, et les poignées revenant à un point spécifique dans la récursion (c.-à-d. pas primitif-récursive). Il est dit que chaque récursion peut être transformée en itération , il semble donc que cela devrait être possible.
je viens de trouver un exemple de C# de la façon de faire ceci. Supposons que vous ayez la fonction récursive suivante, qui agit comme un postordeur transversal, et que AbcTreeNode est un arbre 3-ary avec des pointes 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();
}
}
S'efforcer de faire votre appel récursif Retail Recursion (recursion où la dernière déclaration est l'appel récursif). Une fois que vous avez cela, le convertir en itération est généralement assez facile.
Eh bien, en général, la récursion peut être imitée comme itération en utilisant simplement une variable de stockage. Notez que la récursion et l'itération sont généralement équivalentes; l'une peut presque toujours être convertie en l'autre. Une fonction récursive de queue est très facilement convertie en une fonction itérative. 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à.
même en utilisant la pile ne convertira pas un algorithme récursif en itératif. La récursion normale est une récursion basée sur la fonction et si nous utilisons stack alors elle devient une récursion basée sur la pile. Mais sa reste de 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 la pile de choses en termes de complexité reste le même. Je je pense que seule la récursion de la queue peut être convertie en itération.
l'article stacks and recursion elimination capte l'idée d'externaliser le cadre de la pile sur tas, mais ne fournit pas une façon simple et reproductible façon de convertir. Ci-dessous en est 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 profond arbitraire. Pas seulement les paramètres, mais également le point de revenir à la logique qui reste à exécuter et l'état des variables qui participent aux conditionnals ultérieurs, qui comptent. Ci-dessous est une façon très simple de convertir en code itératif avec le moins de changements.
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 que la structure du code reste fidèle à la logique récursive et que les modifications sont minimes, ce qui entraîne moins de bogues. Pour la comparaison, j'ai marqué les changements ++ 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();
}
-------------------------
}
utilisez google pour" Continuation passing style."Il existe une procédure générale pour la conversion à un style récursif de la queue; il existe également une procédure générale pour transformer les fonctions récursives de la queue en boucles.
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);
}
}
généralement, la technique pour éviter le débordement de la pile est pour les fonctions récursives est appelé technique de trampoline qui est largement adopté par Java devs.
Cependant, pour C# il y a une petite méthode d'aide ici qui transforme votre fonction récursive en itérative sans exiger de changer la logique ou de rendre le code in-compréhensible. C# est un langage tellement agréable que des choses étonnantes sont possibles avec lui.
il fonctionne en enveloppant les pièces de la méthode par une méthode d'aide. Par exemple la fonction récursive:
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);
}
Un motif à rechercher est une récursivité appel à la fin de la fonction (appelée queue-de récursivité). Cela peut facilement être remplacé par un tout. 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 à toto. Ceci peut être remplacé par:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
qui élimine le second appel récursif.
je viens d'annuler la réponse suggérant d'utiliser une pile explicite que je pense être la bonne solution et est d'application générale.
je veux dire que vous pouvez l'utiliser pour transformer n'importe quelle fonction récursive dans une fonction itérative. Il suffit de vérifier quelles valeurs sont sauvegardées à travers les appels récursifs, ce sont celles que ont pour être locales à la fonction récursive, et de remplacer les appels par un cycle où vous les pousserez sur une pile. Lorsque la pile la fonction récursive aurait été terminée.
Je ne peux résister à dire que la preuve que chaque fonction récursive est équivalente à une fonction itérative sur un type de données différent, c'est l'un de mes souvenirs les plus chers de mon époque universitaire. C'est bien (et le professeur) qui m'a vraiment fait comprendre ce que la programmation informatique.
a question qui avait été fermée en double de celle-ci avait une structure de données très spécifique:
le noeud 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 pour les fonctions récursives qui s'invoquer plus d'une fois (ou même 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. Ceci est accompli en plaçant le noeud courant child à la fin de la liste de la première rangée.
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 à n'importe quelle structure liée aux données qui peut être réduite à un DAG avec un ordre topologique déterministe. Les noeuds courants enfants sont réarrangés de sorte que le dernier enfant adopte toutes les autres enfants. Puis le noeud courant peut être supprimé et transversal peut alors itérer à l'enfant restant.
la récursion n'est rien d'autre que le processus d'appel d'une fonction de l'autre seulement ce processus est fait en appelant d'une fonction par elle-même. Comme nous le savons, lorsqu'une fonction appelle l'autre fonction, la première fonction sauve son état(ses variables) et passe ensuite le contrôle à la fonction appelée. La fonction appelée peut être appelé en utilisant le même nom de variables ex fun1(a) peut appeler fun2(un). Quand nous faisons appel récursif rien de nouveau n'arrive. Une fonction s'appelle elle-même en passant même type et similaires dans les variables de nom (mais évidemment les valeurs stockées dans les variables sont différentes,seul le nom reste le même.)de lui-même. Mais avant chaque appel la fonction sauve son état et ce processus d'épargne continue. La sauvegarde se fait sur une pile.
MAINTENANT LA PILE ENTRE EN JEU.
donc si vous écrivez un programme itératif et sauvez l'état sur une pile à chaque fois et puis pop out les valeurs de la pile quand nécessaire, vous avez avec succès converti un programme récursif dans un processus itératif!
La preuve est simple et analytique.
en récursion l'ordinateur maintient une pile et en version itérative vous devrez maintenir manuellement la pile.
pensez-y, il suffit de convertir une première recherche en profondeur(sur les graphiques) programme récursif en un programme itératif dfs.
Tout le meilleur!
de Penser à des choses qui ont réellement besoin d'une pile:
si nous considérons le schéma de récursion 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
}
ceci peut être traduit dans une boucle travaillant sur une pile explicite, en la reformulant comme:
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 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é comment vous définissez votre pile. Vous pouvez faire votre pile une liste d'objets Command 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 est dans le tas plutôt que dans le Java pile d'exécution, mais cela peut être utile, que vous avez plus de contrôle sur il.
une description sommaire de la façon dont un système prend n'importe quelle fonction récursive et l'exécute en utilisant une pile:
il s'agissait de montrer l'idée sans détails. Considérez cette fonction qui imprimerait des noeuds d'un graphe:
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 graphe: A- > B A- > C l'indication (A) indiquerait B, A, C
les appels de fonction signifient enregistrer l'état local et le point de continuation de sorte que vous pouvez revenir, puis sauter la fonction que vous souhaitez appeler.
par exemple, supposons que show(a) commence à courir. L'appel de fonction sur la ligne 3. montrer(B) des moyens - Ajouter un élément à la pile qui signifie "vous devrez continuer à la ligne 2 avec le noeud local variable state = A" - Goto ligne 0 avec noeud=B.
pour exécuter le code, le système exécute les instructions. Quand un appel de fonction est rencontré, le système pousse l'information dont il a besoin pour revenir à l'endroit où il était, exécute le code de fonction, et quand la fonction complète, pop les informations sur l'endroit où il faut aller pour continuer.
Ce lien fournit quelques explications et propose l'idée de conserver le terme "emplacement" pour être en mesure d'obtenir à l'endroit exact entre plusieurs appels récursifs:
Cependant, tous ces exemples décrivent des scénarios dans lesquels un appel récursif est en fait un fixe nombre de fois. Les choses deviennent plus compliquées quand vous avez quelque chose comme:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
il y a une façon générale de convertir la traversée récursive en itérateur en utilisant un itérateur paresseux qui concaténate plusieurs fournisseurs d'itérateur (expression lambda qui renvoie un itérateur). Voir mon conversion de traversée récursive en itérateur .
un autre exemple simple et complet de transformation de la fonction récursive en une fonction itérative utilisant 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;
}