webentwicklung-frage-antwort-db.com.de

Weg von der Rekursion zur Iteration

Ich habe die Rekursion in meinen vielen Jahren der Programmierung sehr häufig verwendet, um einfache Probleme zu lösen, aber ich bin mir bewusst, dass Sie manchmal eine Iteration aufgrund von Speicher-/Geschwindigkeitsproblemen benötigen.

Irgendwann in der Vergangenheit versuchte ich herauszufinden, ob es eine Art "Muster" oder einen Lehrbuchweg gab, um einen üblichen Rekursionsansatz in die Iteration zu transformieren, und fand nichts. Oder zumindest nichts, woran ich mich erinnern kann, würde helfen.

  • Gibt es allgemeine Regeln?
  • Gibt es ein "Muster"?
292
Gustavo Carreno

Normalerweise ersetze ich einen rekursiven Algorithmus durch einen iterativen Algorithmus, indem ich die Parameter, die normalerweise an die rekursive Funktion übergeben würden, 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 haben und die Reihenfolge der Aufrufe beibehalten möchten, müssen Sie sie in umgekehrter Reihenfolge zum Stack hinzufügen:

foo(first);
foo(second);

muss durch ersetzt werden

stack.Push(second);
stack.Push(first);

Bearbeiten: Der Artikel Stapel- und Rekursionsbeseitigung (oder Artikelsicherungslink ) enthält weitere Details zu diesem Thema.

282
David S.

Der üblichste Weg ist, den eigenen Stack 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 Stack 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 prüft dieses Beispiel die Stapelgrenzen nicht ... und Sie könnten die Größe des Stapels basierend auf dem ungünstigsten Fall für die linken und rechten Werte festlegen. Aber du hast die Idee.

70
bobwienholt

Es scheint, dass niemand angesprochen hat, wo die rekursive Funktion sich mehr als einmal im Körper aufruft und zu einem bestimmten Punkt der Rekursion zurückkehrt (d. H. Nicht primitiv-rekursiv). Man sagt, dass jede Rekursion in Iteration umgewandelt werden kann, also scheint es möglich zu sein.

Ich habe mir gerade ein C # -Beispiel dafür vorgestellt. Angenommen, Sie haben die folgende rekursive Funktion, die wie eine Nachordnungstraversierung wirkt, und dass AbcTreeNode ein 3-ary-Baum mit den Zeigern a, b, c ist.

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


        }
43
T. Webster

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

28
Chris Shaffer

Nun, im Allgemeinen kann Rekursion als Iteration simuliert werden, indem einfach eine Speichervariable verwendet wird. Beachten Sie, dass Rekursion und Iteration im Allgemeinen gleichwertig sind. eine kann fast immer in die andere umgewandelt werden. Eine tailrekursive Funktion kann sehr leicht in eine iterative Funktion umgewandelt werden. Machen Sie die Akkumulatorvariable einfach zu einer lokalen und wiederholen Sie, anstatt zu rekursieren. Hier ein Beispiel in C++ (C wäre kein 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;
}

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

18
coppro

Selbst wenn Sie stack verwenden, wird ein rekursiver Algorithmus nicht in einen iterativen Algorithmus konvertiert. Die normale Rekursion ist eine funktionsbasierte Rekursion, und wenn wir Stack verwenden, wird dies zu einer rekursiven Stack-Rekursion. Aber es ist immer noch eine Rekursion.

Für rekursive Algorithmen ist die Raumkomplexität O(N) und die zeitliche Komplexität ist O (N). Für iterative Algorithmen ist die Raumkomplexität O(1) und die zeitliche Komplexität ist O (N). 

Wenn wir jedoch Stack-Dinge in Bezug auf die Komplexität verwenden, bleibt dies dasselbe. Ich denke, nur die Rekursion des Schwanzes kann in Iteration umgewandelt werden.

13
ARC

Der Artikel Stacks and Recursion Elimination fängt die Idee der Externalisierung des Stack-Frames auf dem Heap ein, bietet jedoch kein direktes und wiederholbares Weg zu konvertieren. Unten ist einer.

Bei der Konvertierung in iterativen Code muss beachtet werden, dass der rekursive Aufruf aus einem beliebig tiefen Codeblock erfolgen kann. Es sind nicht nur die Parameter, sondern auch der Punkt, an dem zur noch auszuführenden Logik zurückgekehrt werden muss, und der Zustand der Variablen, die an nachfolgenden Bedingungen beteiligt sind. Im Folgenden finden Sie eine sehr einfache Möglichkeit, mit den 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 immer noch 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 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();
    }

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

}
13
Chethan

Suchen Sie in Google nach "Weiterleitungsstil". Es gibt ein allgemeines Verfahren zum Konvertieren in einen rekursiven Stil. Es gibt auch ein allgemeines Verfahren, um rekursive Funktionen von Endpunkten in Schleifen umzuwandeln.

6
Marcin

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 in konvertiert 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);
    }

}
5
Tae-Sung Shin

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

Für C # gibt es jedoch eine kleine Hilfsmethode hier , die Ihre rekursive Funktion zu iterativ macht, ohne die Logik ändern oder den Code unverständlich zu machen. C # ist eine so schöne Sprache, dass damit erstaunliches möglich ist.

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

Ein Muster, nach dem gesucht werden muss, ist ein Rekursionsaufruf am Ende der Funktion (so genannte Tail-Rekursion). Dies kann leicht mit einer 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 entfällt der zweite rekursive Aufruf.

3
Andrew Stein

Eine -Frage , die als Duplikat dieser abgeschlossen wurde, hatte eine sehr spezifische Datenstruktur:

enter image description here

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 mehrmals (oder sogar einmal) aufrufen. Für diese spezielle Struktur ist es jedoch möglich. Die Idee ist, alle Knoten zu einer einzigen Liste zusammenzufassen. Dies wird erreicht, indem die child des aktuellen Knotens am Ende der Liste der obersten Zeile steht.

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 mit einer deterministischen topologischen Reihenfolge zu einer DAG 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 die Durchquerung kann dann an das verbleibende untergeordnete Element durchlaufen werden.

2
jxh

Ich habe gerade die Antwort bekräftigt und vorgeschlagen, einen expliziten Stack zu verwenden, von dem ich denke, dass er die richtige Lösung ist und allgemein anwendbar ist.

Ich meine damit, dass Sie es verwenden können, um jede rekursive Funktion in eine iterative Funktion zu transformieren. Prüfen Sie einfach, welche Werte bei rekursiven Aufrufen gespeichert werden. Dies sind diejenigen, die haben , um lokal für die rekursive Funktion zu sein, und ersetzen Sie die Aufrufe durch einen Zyklus, in den Sie sie auf einen Stapel legen. Wenn der Stapel leer ist, wäre die rekursive Funktion beendet worden.

Ich kann nicht widerstehen zu sagen, dass der Beweis, dass jede rekursive Funktion einer iterativen Funktion eines anderen Datentyps entspricht, eine meiner schönsten Erinnerungen an meine Universitätszeiten ist. Das war der Kurs (und der Professor), durch den ich wirklich verstanden habe, worum es bei Computerprogrammierung geht.

2
Remo.D

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

Betrachten wir das Muster der Rekursion 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 Stack arbeitet, indem es wie folgt neu geschrieben 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 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 hier eine große Flexibilität, wie Sie Ihren Stack definieren. Sie können aus Ihrem Stack eine Liste von Command-Objekten erstellen, die anspruchsvolle Aufgaben ausführen. Oder Sie können in die entgegengesetzte Richtung gehen und eine Liste mit einfacheren Typen erstellen (z. B. könnte eine "Aufgabe" 4 Elemente auf einem Stack von int und nicht ein Element auf einem Stack von Task sein).

Dies bedeutet lediglich, dass sich der Speicher für den Stack im Heapspeicher befindet und nicht im Java-Ausführungsstack. Dies kann jedoch nützlich sein, da Sie mehr Kontrolle darüber haben.

1
slim

Rekursion ist nichts anderes als der Aufruf einer Funktion von der anderen, nur dieser Prozess wird durch Aufruf einer Funktion von selbst ausgeführt. Wie wir wissen, wenn eine Funktion die andere Funktion aufruft, speichert die erste Funktion ihren Zustand (ihre Variablen) und übergibt die Steuerung an die aufgerufene Funktion. Die aufgerufene Funktion kann mit dem gleichen Namen 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 übergibt (aber die in Variablen gespeicherten Werte sind natürlich unterschiedlich, nur der Name bleibt derselbe.). Vor jedem Aufruf speichert die Funktion ihren Zustand und dieser Vorgang wird fortgesetzt. Das Speichern IS wurde auf einem Stapel erledigt.

Jetzt kommt der Stapel ins Spiel.

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

Der Beweis ist einfach und analytisch.

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

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

Alles Gute!

1
Ajay Manas

Es gibt eine allgemeine Möglichkeit, rekursives Durchlaufen in Iterator zu konvertieren, indem ein Lazy-Iterator verwendet wird, der mehrere Iterator-Anbieter verkettet (Lambda-Ausdruck, der einen Iterator zurückgibt). Siehe mein Konvertieren von rekursivem Durchlauf in Iterator .

0
Dagang

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;
}
0
L_J

Eine grobe Beschreibung, wie ein System eine rekursive Funktion verwendet und diese mit einem Stack ausführt:

Dies sollte die Idee ohne Details zeigen. Betrachten Sie diese Funktion, die Knoten eines Diagramms ausdrucken 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 graph: A-> B A-> C Show (A) würde B, A, C drucken

Funktionsaufrufe bedeuten, den lokalen Zustand und den Fortsetzungspunkt zu speichern, damit Sie zurückkommen und die Funktion aufrufen können, die Sie aufrufen möchten.

Angenommen, show (A) beginnt zu laufen. Der Funktionsaufruf in Zeile 3. show (B) bedeutet - Fügen Sie dem Stapel ein Element hinzu, das bedeutet "Sie müssen in Zeile 2 mit dem Statusknoten der lokalen Variablen = A fortfahren" - Springe Zeile 0 mit Knoten = B.

Um Code auszuführen, führt das System die Anweisungen durch. Wenn ein Funktionsaufruf gefunden wird, gibt das System die Informationen weiter, die es benötigt, um wieder dorthin zurückzukehren, führt den Funktionscode aus, und wenn die Funktion abgeschlossen ist, werden die Informationen darüber angezeigt, wohin sie gehen müssen, um fortzufahren.

0
Rick Giuly

Dieser link enthält einige Erklärungen und schlägt die Idee vor, "location" beizubehalten, um genau an den Ort zwischen mehreren rekursiven Aufrufen zu gelangen:

In all diesen Beispielen werden jedoch Szenarien beschrieben, in denen ein rekursiver Aufruf mit fixed ausgeführt wird. Die Dinge werden schwieriger, wenn Sie Folgendes haben:

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