Chemin à parcourir de la récursion à l'itération
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
J'ai souvent utilisé la récursivité au cours de mes nombreuses années de programmation pour résoudre des problèmes simples, mais je suis tout à fait conscient du fait que vous avez parfois besoin d'itération à cause de problèmes de mémoire / vitesse.
Ainsi, très récemment, je suis allé à la recherche de l'existence d'un "motif". ou une manière de manuel de transformer une approche de récursion commune à l'itération et n'a rien trouvé. Ou du moins rien dont je puisse me souvenir aurait pu aider.
- Existe-t-il des règles générales?
- Y a-t-il un "motif"?
La solution
Généralement, je remplace un algorithme récursif par un algorithme itératif en poussant les paramètres qui seraient normalement transmis à 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 plusieurs appels récursifs à l'intérieur et que vous souhaitez conserver 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);
Modifier: L'article Élimination des piles et des récurrences (ou lien de sauvegarde d’article ) donne plus de détails à ce sujet.
Autres conseils
Vraiment, la façon la plus courante de le faire est de garder votre propre pile. Voici une fonction de tri rapide récursive dans 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 pouvons 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 vous pouvez réellement dimensionner la pile en fonction du cas le plus défavorable étant donné les valeurs left et and right. Mais vous avez l’idée.
Il semble que personne n’ait abordé le point 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écursion (c’est-à-dire non primitive-récursive). Il est dit que peut être transformé en itération , il semble donc que cela devrait être possible.
Je viens juste de trouver un exemple en C # sur la façon de procéder. Supposons que vous ayez la fonction récursive suivante, qui agit comme une traversée postérieure, et que AbcTreeNode est un arbre à trois niveaux avec les 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();
}
}
Efforcez-vous de faire votre appel récursif Récursion de la queue (récursivité où la dernière instruction est l'appel récursif ). Une fois que vous avez cela, la convertir en itération est généralement assez facile.
Eh bien, en général, la récursivité peut être simulée comme une itération en utilisant simplement une variable de stockage. Notez que récursivité et itération sont généralement équivalentes; l'un peut presque toujours être converti à l'autre. Une fonction queue-récursive est très facilement convertie en une fonction itérative. Il suffit de faire de la variable accumulateur une variable locale et d’itérer 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;
}
En me connaissant, j’ai probablement commis une erreur dans le code, mais l’idée est là.
Même en utilisant stack ne convertira pas un algorithme récursif en itératif. La récursivité normale est la récursivité basée sur les fonctions et si nous utilisons la pile, elle devient récursive. Mais c'est toujours la récursivité.
Pour les algorithmes récursifs, la complexité de l’espace est O (N) et la complexité du temps 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 éléments de pile, la complexité reste la même. Je pense que seule la récursion de la queue peut être convertie en itération.
Le élimination des piles et des récursions article reprend l'idée d'externaliser le cadre de pile sur le tas, mais ne fournit pas de moyen de conversion simple et reproductible . En dessous, un.
Lors de la conversion en code itératif, vous devez être conscient du fait que l'appel récursif peut provenir 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 ultérieures, ce qui compte. Voici un moyen très simple de convertir en code itératif avec le moins de changements.
Considérons 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();
}
}
Notez que la structure du code reste fidèle à la logique récursive et que les modifications sont minimes, ce qui réduit le nombre de bogues. Pour 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();
}
-------------------------
}
Recherchez sur Google pour " Style de passage continu. " Il existe une procédure générale pour convertir en style récursif; il existe également une procédure générale permettant de transformer des fonctions récursives 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 permettant d'éviter le débordement de pile pour les fonctions récursives est appelée technique de trampoline, qui est largement adoptée par les développeurs Java.
Cependant, il existe une petite méthode d'assistance pour C # "rel =" noreferrer "> ici transforme votre fonction récursive en itérative sans qu'il soit nécessaire de changer de logique ou de rendre le code incompréhensible. C # est un langage tellement agréable qu’il est possible de créer des choses incroyables.
Cela fonctionne en encapsulant 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);
}
Penser 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
}
Ceci peut être traduit en une boucle fonctionnant sur une pile explicite, en la reformulant ainsi:
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 existe une flexibilité considérable dans la manière dont vous définissez votre pile. Vous pouvez créer dans votre pile une liste d'objets Command exécutant des tâches complexes. Ou vous pouvez aller dans le sens opposé et en faire une liste de types plus simples (par exemple, une "tâche" peut être constituée de 4 éléments sur une pile de int , plutôt que d'un élément sur une pile de Tâche ).
Cela signifie simplement 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 car vous avez plus de contrôle dessus.
Un modèle à rechercher est un appel de récursion à la fin de la fonction (aussi appelé 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. 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 deuxième appel récursif.
Je viens de voter pour la réponse suggérant d’utiliser une pile explicite qui, à mon avis, est la bonne solution et dont l’applicabilité est générale.
Je veux dire que vous pouvez l’utiliser pour transformer toute fonction récursive en une fonction itérative. Il suffit de vérifier quelles valeurs sont enregistrées dans les appels récursifs. Ce sont celles qui doivent être locales à la fonction récursive et remplacer les appels par un cycle dans lequel vous les placerez sur une pile. Lorsque la pile est vide, la fonction récursive aurait été terminée.
Je ne peux m'empêcher de 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 le cours (et le professeur) qui m’a vraiment fait comprendre ce qu’était la programmation informatique.
Une question fermée en tant que duplicata 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’appellent elles-mêmes plus d’une fois (voire une fois). Cependant, pour cette structure particulière, c'est possible. L'idée est de mettre à plat tous les nœuds dans une seule liste. Ceci est accompli en plaçant enfant du noeud actuel à la fin de la liste de la ligne du haut.
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 pouvant être réduite à un DAG avec un ordre topologique déterministe. Les nœuds actuels des enfants 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 sur l’enfant restant.
La récursivité n’est rien d’autre que le processus d’appel d’une fonction à l’autre. Ce processus est effectué en appelant une fonction seule. Comme on le sait, 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 effectuons un appel récursif, rien de nouveau ne se produit. Une fonction s’appelle elle-même en passant le même type et des variables de nom similaires (mais les valeurs stockées dans les variables sont évidemment différentes, seul le nom reste identique.) À elle-même. Mais avant chaque appel, la fonction enregistre son état et le processus de sauvegarde se poursuit. L’ÉCONOMIE EST FAITE SUR UN EMPILEMENT.
Maintenant, la pile entre en jeu.
Donc, si vous écrivez un programme itératif et sauvegardez l'état sur une pile à chaque fois, puis extrayez les valeurs de la pile si nécessaire, vous avez converti avec succès un programme récursif en un programme itératif!
La preuve est simple et analytique.
Lors de la récursivité, l'ordinateur conserve une pile et en version itérative, vous devez gérer la pile manuellement.
Réfléchissez-y, convertissez simplement un programme récursif de recherche en profondeur (sur des graphiques) en programme itératif dfs.
Tout le meilleur!
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:
Ceci visait à montrer l'idée sans détails. Considérez cette fonction qui afficherait les nœuds 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 graphique: A- & B; B A- > C show (A) afficherait B, A, C
Les appels de fonction signifient l’enregistrement de l’état local et du point de continuation afin que vous puissiez revenir puis la fonction que vous souhaitez appeler.
Par exemple, supposons que show (A) commence à s'exécuter. La fonction appelle sur la ligne 3. show (B) signifie - Ajouter un élément à la pile, ce qui signifie "vous devrez continuer à la ligne 2 avec le noeud d'état de la variable locale = A". - Aller à la ligne 0 avec noeud = B.
Pour exécuter le 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 à son état actuel, exécute le code de la fonction et, une fois la fonction terminée, affiche les informations sur les endroits où il doit être poursuivi.
Cette lien fournit des explications et propose l’idée de conserver "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 de fois fixe . Les choses se compliquent lorsque vous avez quelque chose comme:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
Il existe un moyen général de convertir une traversée récursive 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 mon Conversion de la conversion récursive en itérateur .
Un autre exemple simple et complet de conversion 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;
}
