Weg von der Rekursion zur Iteration

349

Ich habe in meiner langjährigen Programmierung viel Rekursion verwendet, um einfache Probleme zu lösen, aber ich bin mir völlig bewusst, dass Sie manchmal aufgrund von Speicher- / Geschwindigkeitsproblemen eine Iteration benötigen.

Irgendwann in der Vergangenheit habe ich versucht herauszufinden, ob es ein "Muster" oder eine Lehrbuchmethode gibt, um einen gemeinsamen Rekursionsansatz in Iteration umzuwandeln, und nichts gefunden. Oder zumindest nichts, woran ich mich erinnern kann, würde helfen.

  • Gibt es allgemeine Regeln?
  • Gibt es ein "Muster"?
Gustavo Carreno
quelle
4
Ich fand diese Serie informativ: blog.moertel.com/posts/2013-05-11-recursive-to-iterative.html
orionrush

Antworten:

333

Normalerweise ersetze ich einen rekursiven Algorithmus durch einen iterativen Algorithmus, indem ich die Parameter, die normalerweise an die rekursive Funktion übergeben werden, auf einen Stapel schiebe. Tatsächlich ersetzen Sie den Programmstapel durch einen 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 enthalten und die Reihenfolge der Aufrufe beibehalten möchten, müssen Sie diese in umgekehrter Reihenfolge zum Stapel hinzufügen:

foo(first);
foo(second);

muss ersetzt werden durch

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

Bearbeiten: Der Artikel Stacks and Recursion Elimination (oder Article Backup Link ) enthält weitere Details zu diesem Thema.

David Segonds
quelle
4
Wenn Sie Ihren Stapel durch eine Warteschlange ersetzen, löst dies nicht das Problem der Umkehrung der Additionsreihenfolge?
Samuel Warren
2
Ich habe es auf Papier ausgearbeitet und es sind zwei verschiedene Dinge. Wenn Sie die Reihenfolge, in der Sie sie hinzugefügt haben, umkehren, werden Sie wie gewohnt vorwärts bewegt, aber Ihre Durchquerung ist immer noch eine Tiefensuche. Aber wenn Sie das Ganze jetzt in eine Warteschlange verwandeln, führen Sie die Breite zuerst durch und nicht die Tiefe zuerst.
Pete
1
Ich habe dies erst kürzlich allgemein getan, indem ich meine Knotenbesuchsfunktion (node)->()durch " (node)->[actions]wo Aktion ist" ersetzt habe () -> [actions]. Dann nehmen Sie außen einfach eine Aktion / Fortsetzung vom Stapel, wenden sie an / führen sie aus, verschieben die auf dem Stapel zurückgegebenen Aktionen in umgekehrter Reihenfolge und wiederholen sie. Kontingente / komplexe Durchläufe, Sie erfassen nur lokale Stapelvariablen in Zeigern mit Referenzzählung, die Sie in Ihren Thunks schließen, und nachfolgende Thunks können von den Ergebnissen früherer Sub-Traversals usw.
abhängig sein
6
Manchmal vermeiden wir eine Rekursion, um einen Stapelüberlauf zu vermeiden. Die Wartung unseres eigenen Stacks führt jedoch auch zu einem Stapelüberlauf. Warum wollen wir die Rekursion mit unserem eigenen Stack implementieren?
Zhu Li
8
@ZhuLi Wenn wir verwenden new, können wir anstelle des Stapels ein Objekt auf dem Heap erstellen. Im Gegensatz zum Stapel hat der Heap keine Speicherbeschränkungen. Siehe gribblelab.org/CBootCamp/7_Memory_Stack_vs_Heap.html
yuqli
77

Wirklich ist der häufigste Weg, dies zu tun, Ihren eigenen Stapel zu behalten. 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);
}

So könnten wir es iterativ machen, indem wir unseren eigenen Stapel behalten:

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 werden in diesem Beispiel die Stapelgrenzen nicht überprüft ... und Sie können den Stapel tatsächlich anhand des ungünstigsten Falls für die linken und rechten Werte dimensionieren. Aber du kommst auf die Idee.

bobwienholt
quelle
1
Irgendwelche Ideen, wie der maximale Stapel für eine bestimmte Rekursion ermittelt werden kann?
Lexicalscope
@lexicalscope Angenommen, Sie haben einen rekursiven Algorithmus in O(N) = O(R*L), wobei Ldie Summe der Komplexität "für Schicht r" ist. In diesem Fall müssen Sie O(N)bei jedem Schritt die Partitionierungen durchführen. Die rekursive Tiefe ist hier O(R), dh im schlimmsten Fall O(N), der durchschnittliche Fall O(logN).
Caleth
48

Es scheint, dass niemand angesprochen hat, wo sich die rekursive Funktion mehr als einmal im Körper aufruft und die Rückkehr zu einem bestimmten Punkt in der Rekursion (dh nicht primitiv-rekursiv) behandelt. Es wird gesagt, dass jede Rekursion in Iteration umgewandelt werden kann , so dass dies möglich sein sollte.

Ich habe mir gerade ein C # -Beispiel ausgedacht, wie das geht. Angenommen, Sie haben die folgende rekursive Funktion, die sich wie eine Nachbestellungsdurchquerung verhält, und AbcTreeNode ist ein 3-ariger Baum mit den Zeigern 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();
            }


        }
T. Webster
quelle
5
Es ist wirklich nützlich, ich musste eine iterative Version der Wiederholung schreiben, die sich n-mal selbst hervorruft, dank Ihres Beitrags, den ich gemacht habe.
Wojciech Kulik
1
Dies muss das beste Beispiel sein, das ich je gesehen habe, um die Rekursion des Aufrufstapels für Situationen zu emulieren, in denen innerhalb der Methode mehrere rekursive Aufrufe ausgeführt werden. Gut gemacht.
CCS
1
Sie hatten mich bei "Es scheint, dass niemand angesprochen hat, wo sich die rekursive Funktion mehr als einmal im Körper aufruft und die Rückkehr zu einem bestimmten Punkt in der Rekursion behandelt", und dann habe ich bereits upvoted. OK, jetzt werde ich den Rest Ihrer Antwort lesen und sehen, ob meine vorzeitige Gegenstimme gerechtfertigt war. (Weil ich unbedingt die Antwort darauf wissen muss).
Mydoghaswürmer
1
@mydoghasworms - Nach so langer Zeit kam ich auf diese Frage zurück und brauchte sogar einen Moment, um mich daran zu erinnern, was ich dachte. Hoffe die Antwort hat geholfen.
T. Webster
1
Die Idee dieser Lösung hat mir gefallen, aber sie kam mir verwirrend vor. Ich habe eine vereinfachte Version für den Binärbaum in Python geschrieben. Vielleicht hilft sie jemandem, die Idee zu verstehen: gist.github.com/azurkin/abb258a0e1a821cbb331f2696b37c3ac
Azurkin
33

Bemühen Sie sich, Ihren rekursiven Aufruf Tail Recursion (Rekursion, bei der die letzte Anweisung der rekursive Aufruf ist) durchzuführen. Sobald Sie das haben, ist die Konvertierung in Iteration im Allgemeinen ziemlich einfach.

Chris Shaffer
quelle
2
Einige JITs
Liran Orevi
Viele Dolmetscher (dh das Schema ist das bekannteste) optimieren die Schwanzrekursion gut. Ich weiß, dass GCC mit einer bestimmten Optimierung eine Schwanzrekursion durchführt (obwohl C eine seltsame Wahl für eine solche Optimierung ist).
new123456
19

Im Allgemeinen kann die Rekursion als Iteration nachgeahmt werden, indem einfach eine Speichervariable verwendet wird. Beachten Sie, dass Rekursion und Iteration im Allgemeinen gleichwertig sind. man kann fast immer zum anderen konvertieren. Eine rekursive Schwanzfunktion lässt sich sehr leicht in eine iterative umwandeln. Machen Sie einfach die Akkumulatorvariable zu einer lokalen und iterieren Sie anstatt zu rekursieren. Hier ist ein Beispiel in C ++ (C wäre es nicht für die Verwendung eines Standardarguments):

// 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;
}

Als ich mich kannte, habe ich wahrscheinlich einen Fehler im Code gemacht, aber die Idee ist da.

coppro
quelle
14

Selbst die Verwendung eines Stapels konvertiert einen rekursiven Algorithmus nicht in einen iterativen. Normale Rekursion ist eine funktionsbasierte Rekursion. Wenn wir einen Stapel verwenden, wird sie zu einer stapelbasierten Rekursion. Aber es ist immer noch Rekursion.

Für rekursive Algorithmen ist die Raumkomplexität O (N) und die Zeitkomplexität O (N). Bei iterativen Algorithmen beträgt die Raumkomplexität O (1) und die Zeitkomplexität O (N).

Wenn wir jedoch Stapel verwenden, bleibt die Komplexität gleich. Ich denke, nur die Schwanzrekursion kann in Iteration umgewandelt werden.

BOGEN
quelle
1
Ich stimme Ihrem ersten Teil zu, aber ich glaube, ich verstehe den zweiten Absatz falsch. Betrachten Sie das Klonen eines Arrays durch einfaches Kopieren des Speicherplatzes copy = new int[size]; for(int i=0; i<size; ++i) copy[i] = source[i];und die zeitliche Komplexität sind beide O (N), basierend auf der Größe der Daten, aber es ist eindeutig ein iterativer Algorithmus.
Ponkadoodle
13

Der Artikel zur Beseitigung von Stapeln und Rekursionen enthält die Idee, den Stapelrahmen auf dem Heap zu externalisieren, bietet jedoch keine einfache und wiederholbare Möglichkeit zum Konvertieren. Unten ist einer.

Bei der Konvertierung in iterativen Code muss beachtet werden, dass der rekursive Aufruf von einem beliebig tiefen Codeblock aus erfolgen kann. Es geht nicht nur um die Parameter, sondern auch um den Punkt, an dem die noch auszuführende Logik und der Status der Variablen, die an nachfolgenden Bedingungen beteiligt sind, von Bedeutung sind. Im Folgenden finden Sie eine sehr einfache Möglichkeit, mit geringsten Änderungen in iterativen Code zu konvertieren.

Betrachten Sie diesen rekursiven 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);
    }    
}

Iterativer 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, dass die Struktur des Codes weiterhin der rekursiven Logik entspricht und die Änderungen minimal sind, was zu einer geringeren Anzahl von Fehlern führt. Zum Vergleich habe ich die Änderungen mit ++ und - markiert. Die meisten der neu eingefügten Blöcke mit Ausnahme von v.push_back sind allen konvertierten iterativen Logik gemeinsam

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
quelle
Das hat mir sehr geholfen, aber es gibt ein Problem: stackitemObjekte werden mit einem Müllwert für zugewiesen ra. Alles funktioniert immer noch im ähnlichsten Fall, aber sollte es razufällig 1 oder 2 sein, erhalten Sie ein falsches Verhalten. Die Lösung besteht darin, raauf 0 zu initialisieren .
JanX2
@ JanX2, stackitemdarf nicht ohne Initialisierung gepusht werden. Aber ja, das Initialisieren auf 0 würde Fehler auffangen.
Chethan
Warum werden nicht v.pop_back()stattdessen beide Absenderadressen auf die Anweisung festgelegt?
is7s
7

Suchen Sie in Google nach "Continuation Passing Style". Es gibt ein allgemeines Verfahren zum Konvertieren in einen rekursiven Endstil. Es gibt auch ein allgemeines Verfahren zum Umwandeln von rekursiven Schwanzfunktionen in Schleifen.

Marcin
quelle
6

Nur die Zeit totzuschlagen ... Eine rekursive Funktion

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

kann konvertiert werden zu

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
quelle
Das obige Beispiel ist ein Beispiel für rekursive zu iterativen dfs auf binären Suchbaum :)
Amit
5

Im Allgemeinen wird die Technik zur Vermeidung eines Stapelüberlaufs für rekursive Funktionen als Trampolintechnik bezeichnet, die von Java-Entwicklern weit verbreitet ist.

Doch für C # gibt es ein kleines Hilfsmethode hier die Ihre rekursive Funktion zu iterative schaltet ohne Änderung Logik zu erfordern oder den Code in-verständlich machen. C # ist eine so schöne Sprache, dass damit erstaunliche Dinge möglich sind.

Es funktioniert, indem Teile der Methode mit einer Hilfsmethode umbrochen werden. Zum Beispiel die 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;
}

Verwandelt 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);
}
naiem
quelle
4

Denken Sie an Dinge, die tatsächlich einen Stapel benötigen:

Wenn wir das Rekursionsmuster betrachten als:

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 Turm von 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 eine Schleife übersetzt werden, die an einem expliziten Stapel arbeitet, indem es wie folgt angepasst wird:

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 den Turm von Hanoi wird dies:

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()));
    }
}

Hier besteht eine erhebliche Flexibilität bei der Definition Ihres Stapels. Sie können Ihren Stapel zu einer Liste von CommandObjekten machen, die anspruchsvolle Dinge tun. Oder Sie können in die entgegengesetzte Richtung gehen und eine Liste mit einfacheren Typen erstellen (z. B. kann eine "Aufgabe" 4 Elemente auf einem Stapel von intstatt eines Elements auf einem Stapel von sein Task).

Dies bedeutet lediglich, dass sich der Speicher für den Stapel im Heap und nicht im Java-Ausführungsstapel befindet. Dies kann jedoch hilfreich sein, da Sie mehr Kontrolle darüber haben.

schlank
quelle
3

Ein zu suchendes Muster ist ein Rekursionsaufruf am Ende der Funktion (sogenannte Schwanzrekursion). Dies kann leicht durch eine Weile ersetzt werden. Zum Beispiel die Funktion foo:

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

endet mit einem Anruf bei foo. Dies kann ersetzt werden durch:

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

Dadurch wird der zweite rekursive Aufruf eliminiert.

Andrew Stein
quelle
3
Sieht für mich immer noch rekursiv aus ... :)
Nathan
2
Ja, aber es ist halb so rekursiv. Um die andere Rekursion loszuwerden, muss eine andere Technik angewendet werden ...
Mark Bessey
2

Eine Frage , die als Duplikat dieser Frage geschlossen worden war, hatte eine sehr spezifische Datenstruktur:

Geben Sie hier die Bildbeschreibung ein

Der Knoten hatte 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 folgendermaßen aus:

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

Im Allgemeinen ist es nicht immer möglich, einen Stapel für rekursive Funktionen zu vermeiden, die sich mehr als einmal (oder sogar einmal) aufrufen. Für diese spezielle Struktur ist es jedoch möglich. Die Idee ist, alle Knoten in einer einzigen Liste zusammenzufassen. Dies wird erreicht, indem die aktuellen Knoten childam Ende der Liste der obersten Zeile platziert werden.

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 jede datengebundene Struktur angewendet werden, die auf eine DAG mit einer deterministischen topologischen Reihenfolge reduziert werden kann. Die aktuellen untergeordneten Knoten werden neu angeordnet, sodass das letzte untergeordnete Element alle anderen untergeordneten Elemente übernimmt. Dann kann der aktuelle Knoten gelöscht werden und das Durchlaufen kann dann zum verbleibenden untergeordneten Knoten iterieren.

jxh
quelle
1

Rekursion ist nichts anderes als das Aufrufen einer Funktion von der anderen. Nur dieser Vorgang erfolgt durch Aufrufen einer Funktion für sich. Wie wir wissen, speichert die erste Funktion beim Aufrufen der anderen Funktion ihren Status (ihre Variablen) und übergibt die Steuerung dann an die aufgerufene Funktion. Die aufgerufene Funktion kann unter Verwendung des gleichen Namens von Variablen aufgerufen werden. Ex fun1 (a) kann fun2 (a) aufrufen. Wenn wir rekursiv aufrufen, passiert nichts Neues. Eine Funktion ruft sich selbst auf, indem sie denselben Typ und ähnliche Namensvariablen (aber offensichtlich sind die in Variablen gespeicherten Werte unterschiedlich, nur der Name bleibt gleich) an sich selbst übergibt. Vor jedem Aufruf speichert die Funktion ihren Status und dieser Speichervorgang wird fortgesetzt. Die Einsparung erfolgt auf einem Stapel.

JETZT KOMMT DER STAPEL ZUM SPIELEN.

Wenn Sie also jedes Mal ein iteratives Programm schreiben und den Status auf einem Stapel speichern und dann bei Bedarf die Werte aus dem Stapel entfernen, haben Sie ein rekursives Programm erfolgreich in ein iteratives Programm konvertiert!

Der Beweis ist einfach und analytisch.

Bei der Rekursion verwaltet der Computer einen Stapel, und bei der iterativen Version müssen Sie den Stapel manuell verwalten.

Denken Sie darüber nach, konvertieren Sie einfach ein rekursives Programm für die Tiefensuche (in Diagrammen) in ein iteratives dfs-Programm.

Alles Gute!

Ajay Manas
quelle
1

Ein weiteres einfaches und vollständiges Beispiel für die Umwandlung der rekursiven Funktion in eine iterative Funktion mithilfe des Stapels.

#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
quelle
0

Eine grobe Beschreibung, wie ein System eine rekursive Funktion übernimmt und sie mithilfe eines Stapels ausführt:

Dies sollte die Idee ohne Details zeigen. Betrachten Sie diese Funktion, mit der Knoten eines Diagramms ausgedruckt werden:

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 Grafik: A-> B A-> C show (A) würde B, A, C drucken

Funktionsaufrufe bedeuten, den lokalen Status und den Fortsetzungspunkt zu speichern, damit Sie zurückkehren und dann die Funktion überspringen können, die Sie aufrufen möchten.

Angenommen, Show (A) beginnt zu laufen. Der Funktionsaufruf in Zeile 3. show (B) bedeutet - Element zum Stapel hinzufügen, was bedeutet, dass Sie in Zeile 2 mit dem lokalen Variablenstatus node = A fortfahren müssen. - Gehen Sie zu Zeile 0 mit node = B.

Um Code auszuführen, durchläuft das System die Anweisungen. Wenn ein Funktionsaufruf auftritt, sendet das System Informationen, die es benötigt, um dorthin zurückzukehren, wo es war, führt den Funktionscode aus und zeigt nach Abschluss der Funktion die Informationen darüber an, wohin es gehen muss, um fortzufahren.

Rick Giuly
quelle
0

Dieser Link bietet einige Erklärungen und schlägt die Idee vor, "Ort" beizubehalten, um zwischen mehreren rekursiven Aufrufen an den genauen Ort zu gelangen:

Alle diese Beispiele beschreiben jedoch Szenarien, in denen ein rekursiver Aufruf eine feste Anzahl von Malen ausgeführt wird. Die Dinge werden schwieriger, wenn Sie etwas haben wie:

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

Es gibt eine allgemeine Möglichkeit, die rekursive Durchquerung in einen Iterator umzuwandeln, indem ein verzögerter Iterator verwendet wird, der mehrere Iteratorlieferanten verkettet (Lambda-Ausdruck, der einen Iterator zurückgibt). Siehe meine Konvertierung der rekursiven Durchquerung in einen Iterator .

Dagang
quelle
0

Meine Beispiele sind in Clojure, sollten aber ziemlich einfach in jede Sprache zu übersetzen sein.

Bei dieser Funktion gilt StackOverflows für große Werte von n:

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

Wir können eine Version definieren, die ihren eigenen Stapel auf folgende Weise verwendet:

(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)))))

wo returnist definiert als:

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

Dies funktioniert auch für komplexere Funktionen, zum Beispiel die ackermann-Funktion :

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

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

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

kann umgewandelt werden in:

(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
quelle