Ist es möglich, einen rekursiven Algorithmus mit einem Iterator zu implementieren?

Question

ich gegeben habe einen Baum wie folgt:

http://www.seqan.de/dddoc/html/streePreorder.png http://www.seqan.de/dddoc/html/streePreorder.png

i jeden Knoten mit dem nächsten Operator acces kann.

// postorder dfs
Iterator< Index<String<char> >, BottomUp<> >::Type myIterator(myIndex);
for (; !atEnd(myIterator); goNext(myIterator)) 
    // do something with myIterator

, aber ich möchte einen rekursiven Algorithmus, der auf dem Baum verwenden.
Gibt es eine Möglichkeit, ich kann die rekursive Algorithmus machen (exlude die größte Teilstruktur auf jedem Knoten) iterative?
oder wie kann ich die Elemente acces nicht-rekursiv?

Edit: Das eigentliche Problem:
Ich habe einen rekursiven Algorithmus gegeben, die auf Bäumen arbeitet. (Rekursiv)
Ich benutze auch eine Bibliothek, wo ich kann nur die Elemente acces mit einem Iterator (nicht Standard, iterative)

rekursive <-> iterativer
. Wie kann ich dieses Problem lösen?

Answer 1

Wenn Ihr Iterator nur nach vorne unterstützt (und möglicherweise rückwärts) Traversal, aber nicht folgenden Links auf dem Baum oder schnellen Direktzugriff, haben Sie eine sehr harte Zeit, einen Baum Algorithmus, um es anzupassen. am Ende wird jedoch eine Antwort auf die Schnittstelle von Ihrer benutzerdefinierten Iteratoren präsentiert ab, die Sie nicht zur Verfügung gestellt haben.

Betrachten wir zum Beispiel den einfachen Algorithmus der Baumsuche. Wenn die nur durch Ihren Iterator gegebene Operation wird „aus dem ersten Elemente beginnen und bewegt auf one-by-one“, können Sie offensichtlich nicht Baumsuche effizient umzusetzen. Ebenso wenig können Sie binäre Suche implementieren. So müssen Sie eine Liste von genau das, was Operationen unterstützt werden, und (kritisch) die Komplexität für jeden begrenzt.

Answer 2

Sie können konvertieren , die rekursive Funktion zu einer iterativen Funktion mit Hilfe eines Stapels.

//breadth first traversal pseudo-code
push root to a stack
while( stack isn't empty )
    pop element off stack
    push children
    perform action on current node

Je nachdem, wie Sie die Knoten zu durchqueren wollen, dass die Implementierung unterschiedlich sein wird. Alle rekursive Funktionen können iterative Einsen umgewandelt werden. Eine allgemeine Verwendung, wie benötigt Informationen über das spezifische Problem. Verwendung Stacks / Warteschlangen und zu einer Umwandlung zur Schleife sind übliche Methoden, sollten die meisten Situationen lösen.

Sie sollten auch Endrekursion schauen und wie sie zu identifizieren, da diese Probleme gut in eine übersetzt for-Schleife, das viele Compiler auch für Sie tun.

Einige, mathematisch orientierte rekursive Aufrufe können von Beziehungen Wiederholung gelöst werden. Die Wahrscheinlichkeit, dass Sie über diese kommen, die noch nicht gelöst worden ist unwahrscheinlich, aber es könnte Sie interessieren.

// bearbeiten, Leistung? Wirklich hängt von der jeweiligen Implementierung und der Größe des Baumes. Wenn es eine Menge von Tiefe in Ihrem rekursiven Aufruf ist, dann werden Sie einen Stapelüberlauf erhalten, während eine iterative Version fein durchführen wird. Ich würde ein besseres Verständnis auf Rekursion erhalten (wie Speicher verwendet wird), und Sie sollten entscheiden können, die für Ihre Situation besser ist. Hier ist ein Beispiel für diese Art der Analyse mit der Fibonacci-Zahlen .

Answer 3

Jede rekursive Funktion kann alternativ mit Stapeln realisiert werden. Ist dies die Frage, die Sie fragen.

Hier ist ein Artikel von Phil Haack rel="nofollow zu diesem Thema.

Performance gewinnt die eine oder die andere sind spekulativ, der Compiler tut Dinge mit unserem Code hinter den Kulissen, die nicht immer vorhersagen können. Implementieren Sie beide und einige reelle Zahlen bekommen. Wenn sie ähnliche Anwendungen sind die, die Sie besser lesbar zu finden.

Answer 4

Auch bei rekursiven Iteration am Ende mit einem Knoten-per-Knoten Besuch auf.

Was müssen Sie wissen, ist: Wie kann mein Iterator gehen zuerst in die Tiefe zu sagen, und dann:. Wie soll ich, dass eine Ebene mitgeteilt hat begonnen / beendet (dh der Start / Ende eines Rekursionsschritt)

Dieses Wissen kann auf den rekursiven Algorithmus abgebildet werden.