Weg von der Rekursion zur Iteration

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"?

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.

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.

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


        }

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.

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.

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.

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

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

}

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.

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

}

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

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.

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.

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

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.

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!

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

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.

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

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 .

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