Weg zu gehen von Rekursion Iteration
https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe ziemlich viel Rekursion auf meiner langjährigen Programmierung, einfache Probleme zu lösen, aber ich bin mir voll bewusst, dass manchmal aufgrund Sie Iteration müssen Speicher / Geschwindigkeitsprobleme.
Also, irgendwann in der Vergangenheit sehr weit ich versuche, ging zu und zu finden, wenn es ein „Muster“ bestanden oder Lehrbuch Art und Weise einen gemeinsamen Rekursion Ansatz der Umwandlung nichts Iteration und gefunden. Oder zumindest nichts, was ich mich erinnern kann, es würde helfen.
- Gibt es allgemeine Regeln?
- Gibt es ein "Muster"?
Lösung
Normalerweise ersetze ich einen rekursiven Algorithmus durch einen iterativen Algorithmus, der durch die Parameter drängen, die normalerweise auf die rekursive Funktion auf einen Stapel übergeben werden würde. In der Tat, ersetzen Sie das Programm Stapel von einem Ihrer eigenen.
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
Hinweis: Wenn Sie mehr als einen rekursiven Aufruf innen haben und Sie möchten die Reihenfolge der Anrufe zu erhalten, müssen Sie sie in umgekehrter Reihenfolge auf den Stapel hinzufügen:
foo(first);
foo(second);
hat ersetzt werden durch
stack.push(second);
stack.push(first);
Edit: Der Artikel Stacks und Rekursion Beseitigung (oder Artikel Backup-Link ) geht in weitere Details zu diesem Thema.
Andere Tipps
Wirklich, der häufigste Weg, es zu tun ist, Ihren eigenen Stapel zu halten. Hier ist eine rekursive quicksort Funktion in 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);
}
Hier ist, wie wir es, indem sie unseren eigenen Stack iterativen machen könnten:
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;
}
}
Offensichtlich ist, dass dieses Beispiel nicht Stack Grenzen überprüfen ... und wirklich können Sie Größe der Stapel auf der Grundlage des schlimmsten Fall gegeben, nach links und rechts und Werten. Aber Sie bekommen die Idee.
Es scheint niemand angesprochen hat, in dem die rekursive Funktion selbst im Körper mehr Anrufe als einmal, und Griffe in der Rekursion (das heißt nicht primitiv-rekursiv) zu einem bestimmten Punkt zurück. Es wird gesagt, dass jede Rekursion in Iteration gedreht werden kann , so scheint es, dass dies möglich sein sollte.
Ich kam gerade mit einem C # Beispiel von oben, wie dies zu tun. Angenommen, Sie haben die folgende rekursive Funktion, die wie ein Nachordnungsdurchquerung wirkt, und dass AbcTreeNode ist ein 3-ary Baum mit Zeiger 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
}
}
Die iterative Lösung:
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();
}
}
Strive Ihre rekursiven Aufruf Endrekursion (Rekursion zu machen, wo die letzte Anweisung der rekursive Aufruf ist ). Sobald Sie, dass es zu Iteration Umwandlung der Regel recht einfach ist.
Nun, im Allgemeinen, kann Rekursion als Iteration durch die Verwendung eines Speichervariable nachgeahmt werden. Man beachte, dass die Rekursion und iteraction ist im allgemeinen äquivalent; man kann fast immer auf die andere umgewandelt werden. Eine tail-rekursive Funktion ist sehr leicht zu einem iterativen einem konvertiert. So stellen Sie die Akku-Variable eine lokale und iterieren statt recurse. Hier ist ein Beispiel in C ++ (C wurden sie nicht für die Verwendung eines Standardargument):
// 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;
}
Knowing me, ich habe wahrscheinlich einen Fehler im Code, aber die Idee ist da.
Auch Stack wird nicht einen rekursiven Algorithmus in iterativen umwandeln. Normale Rekursion Funktion basiert Rekursion und wenn wir Stack verwenden, dann wird es auf Basis Rekursion stapeln. Aber es ist immer noch Rekursion.
Für rekursive Algorithmen, Raumkomplexität O (N) und Zeitkomplexität O (N). Für iterative Algorithmen ist Raum Komplexität O (1) und die Zeitkomplexität O (N).
Aber wenn wir Stapel Dinge in Bezug auf die Komplexität bleibt gleiche verwenden. Ich denke nur Endrekursion kann in Iteration umgewandelt werden.
Die Stacks und Rekursion Beseitigung Artikel fangen die Idee, den Stack-Frame auf Haufen der Externalisierung, sondern eine einfach und wiederholbar Art und Weise zu konvertieren nicht geben. Im Folgenden finden Sie ein.
Während auf iterativen Code umwandelt, muss man sich bewusst sein, dass der rekursive Aufruf von einem beliebig tiefen Codeblock passieren kann. Es ist nicht nur die Parameter, sondern auch der Punkt, an die Logik zurückzukehren, die ausgeführt werden soll, bleibt und den Zustand der Variablen, die in den nachfolgenden conditionals teilnehmen, die wichtig sind. Im Folgenden ist eine sehr einfache Art und Weise zu iterativen Code mit mindestens Änderungen zu konvertieren.
Betrachten Sie diese rekursive Code:
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);
}
}
Iterative Code:
// 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();
}
}
Beachten Sie, wie die Struktur des Codes noch treu bleibt auf der rekursiven Logik und Modifikationen sind minimal, in einer geringeren Anzahl von Fehlern führt. Zum Vergleich habe ich die Änderungen mit ++ und - gekennzeichnet. Die meisten der neu eingefügten Blöcke außer v.push_back, sind häufig zu einem gewandelten iterative Logik
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();
}
-------------------------
}
Google-Suche nach „Fortsetzung Übertragungsstil.“ Es gibt ein allgemeines Verfahren zu einem Schwanz rekursive Stil umzuwandeln; gibt es auch ein allgemeines Verfahren Schwanz rekursive Funktionen in Schleifen für das Drehen.
Nur die Zeit zu ... Eine rekursive Funktion
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
können umgewandelt werden
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);
}
}
Im Allgemeinen ist die Technik Stapelüberlauf zu vermeiden, ist für rekursive Funktionen aufgerufen wird, Trampolin-Technik, die von Java Devs weithin angenommen wird.
Doch für C # eine kleine Helfer-Methode ist hier dass macht Ihre rekursive Funktion zu iterativen, ohne Logik zu ändern oder den Code in-verständlich zu machen. C # ist so eine schöne Sprache, die erstaunlichen Dinge sind damit möglich.
Es funktioniert durch Teile des Verfahrens durch eine Hilfsmethode gewickelt wird. Zum Beispiel der folgende rekursive Funktion:
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;
}
Es stellt sich in:
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);
}
Denken an Dinge, die eigentlich einen Stapel brauchen:
Wenn man bedenkt, das Muster der Rekursion wie:
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
}
Zum Beispiel der klassische Tower of 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
}
Dies kann in einer Schleife übersetzt werden auf einem expliziten Stapel arbeiten, indem er sie als Neuformulierung:
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
}
}
Für Turm von Hanoi dies zu:
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()));
}
}
Es gibt eine beträchtliche Flexibilität hier, wie Sie Ihren Stack definieren. Sie können Ihren Stack eine Liste von Objekten, die Command tun anspruchsvolle Dinge machen. Oder Sie können die entgegengesetzte Richtung gehen und eine Liste von einfacheren Typen machen (beispielsweise eine „Aufgabe“ könnte sein 4 Elemente auf einem Stapel von int, eher als ein Element auf einem Stapel von Task).
All dies bedeutet, dass der Speicher für den Stapel in dem Heap ist und nicht in dem Java-Ausführungsstapel, aber dies kann nützlich sein, dass Sie mehr Kontrolle über sie haben.
Ein Muster zu suchen ist ein Rekursion Anruf am Ende der Funktion (so genannte Tail-Rekursion). Dies kann leicht mit einer Weile ersetzt werden. Zum Beispiel kann die Funktion foo:
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
endet mit einem Aufruf an foo. Dies kann ersetzt werden durch:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
, die den zweiten rekursiven Aufruf eliminiert.
Ich upvoted nur die Antwort eine explizite Stack zu verwenden was darauf hindeutet, dass ich denke, die richtige Lösung und ist allgemein anwendbar.
Ich meine, dass Sie es verwenden können jede rekursive Funktion in einer iterativen Funktion zu transformieren. Überprüfen Sie einfach, welche Werte über rekursive Aufrufe gespeichert, sind diejenigen, die, die wurde sein, lokal für die rekursive Funktion und ersetzen die Anrufe mit einem Zyklus, wo man sie auf einem Stapel schieben werde. Wenn der Stapel leer ist die rekursive Funktion beendet worden wäre.
Ich kann widerstehen, nicht zu sagen, dass der Beweis, dass jede rekursive Funktion zu einer iterativen Funktion auf einem anderen Datentyp entspricht, es ist einer meiner liebsten Erinnerung an meiner Universität Zeiten. Das war der Kurs (und der Professor), das hat mich wirklich zu verstehen, was Computer-Programmierung ging.
Frage , die als ein Duplikat dieser eine geschlossen worden war, eine sehr spezifische Datenstruktur hatte:
Der Knoten hat die folgende Struktur:
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
Die rekursive Löschfunktion sah aus wie:
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
In der Regel ist es nicht immer möglich, einen Stapel für rekursive Funktionen zu vermeiden, die berufen sich mehr als einmal (oder auch nur einmal). Doch für diese besondere Struktur ist es möglich. Die Idee ist, alle Knoten in einer einzigen Liste zu glätten. Dies wird erreicht durch den aktuellen Knotens child am Ende der oberen Reihe der Liste setzen.
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;
}
}
Diese Technik kann auf alle Daten verknüpfen Struktur angewandt werden, die zu einer DAG mit einer deterministischen topologischen Anordnung reduzieren werden können. Die aktuellen Knoten Kinder werden neu angeordnet, so dass das letzte Kind alle anderen Kinder annimmt. Dann kann der aktuelle Knoten gelöscht und Traversal kann dann auf die verbleibenden Kind laufen.
Rekursion ist nichts anderes als der Prozess von einer Funktion von dem anderen des Aufruf nur dieser Prozess durch den Aufruf einer Funktion von selbst erfolgt. Wie wir wissen, wann eine Funktion, um die andere Funktion die erste Funktion speichert seinen Zustand (seine Variablen) und übergibt dann die Kontrolle an die aufgerufene Funktion aufruft. Die aufgerufene Funktion kann unter Verwendung des gleichen Namens von Variablen ab fun1 (a) genannt werden fun2 nennen kann (a). Wenn wir rekursiven Aufruf nichts passiert neu. Eine Funktion nennt sich durch die gleiche Art vorbei und ähnliche Namensvariablen (aber offensichtlich die gespeicherten Werte in Variablen unterschiedlich sind, nur der Name bleibt gleich.) Auf sich. Aber vor jedem Aufruf der Funktion speichert seinen Zustand und dieser Prozess des Sparens weiter. Die Einsparung ist auf einem Stapel DONE.
JETZT DER STACK ins Spiel kommt.
Wenn Sie also ein iteratives Programm schreiben und den Zustand auf einem Stapel jedes Mal speichern und dann aus dem Stapel die Werte herausspringen, wenn nötig, haben Sie erfolgreich ein rekursive Programm in einen iterativen einer umgewandelt!
Der Beweis ist einfach und analytisch.
In Rekursion hält den Computer einen Stapel und in iterativer Version müssen Sie manuell den Stapel halten.
Denken Sie darüber, nur eine Tiefensuche konvertieren (auf Graphen) rekursive Programm in ein dfs iteratives Programm.
Alles Gute!
Eine grobe Beschreibung, wie ein System nimmt jede rekursive Funktion und führt es aus, einen Stapel verwendet:
Damit soll die Idee, ohne Details zeigen. Betrachten Sie diese Funktion, die Knoten eines Graphen auszudrucken würde:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
Zum Beispiel grafische Darstellung: A-> B A-> C Show (A) würde drucken B, A, C
Funktionsaufrufe bedeuten den lokalen Zustand und die Fortsetzung Punkt speichern, um sie zurückkommen, und dann springen die die Funktion, die Sie aufrufen möchten.
Zum Beispiel beginnt suppose zeigen (A) zu laufen. Der Funktionsaufruf auf der Leitung 3. anzeigen (B) Mittel - Artikel in dem Stapel bedeutet „Sie müssen in Zeile 2 mit lokalen Variablen Zustandsknoten = A fortzusetzen“ -. Gehe zu Zeile 0 mit Knoten = B
Um Code auszuführen, führt das System den Anweisungen. Wenn ein Funktionsaufruf angetroffen wird, drückt die Systeminformationen muss sie zurück kommen, wo es war, den Funktionscode ausgeführt wird, und wenn die Funktion beendet ist, erscheint die Information darüber, wo muss es weitergehen.
Der Link liefert eine Erklärung und schlägt vor, die Idee der Haltung „Ort“ auf den genauen Ort zwischen mehreren rekursiven Aufrufe erhalten zu können:
Doch all diese Beispiele beschreiben Szenarien, in denen ein rekursiver Aufruf eine gemacht wird festgelegt Höhe der Zeit. Die Dinge werden komplizierter, wenn Sie so etwas wie haben:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
Es gibt eine allgemeine Art und Weise rekursive Traversal Iterator der Umwandlung durch einen faulen Iterator, die mehrere Iterator Lieferanten (Lambda-Ausdruck, die einen Iterator zurückgibt) verkettet. Sehen Sie mein Converting rekursive Traversal Iterator.
Ein weiteres einfaches und vollständiges Beispiel für die rekursive Funktion in iterativen ein Drehen des Stapels verwendet wird.
#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;
}
