Können alle rekursiven Funktionen mit Iterationen codiert werden? [geschlossen]

10

Was sind die Vorteile der Rekursion?

Einige Programmiersprachen können die Schwanzrekursion optimieren, aber im Allgemeinen verbraucht die Rekursion mehr Ressourcen als normale Schleifen.

Ist es möglich, eine iterative Version einer rekursiven Funktion zu haben?

OscarRyz
quelle

Antworten:

10

Ja, Sie können rekursive Funktionen als Iterationen codieren. Grundsätzlich müssen Sie die Informationen manuell verwalten, für die sonst die vom Compiler generierte Methode zum Aufrufen von Code gesorgt hätte.

Mit anderen Worten, Sie benötigen einen Stapel, in dem jeder Eintrag eine Struktur ist, die die übergebenen Parameter und alle lokalen Variablen enthält. Sie arbeiten immer am obersten Eintrag im Stapel. Wenn Sie sich selbst anrufen müssen, erstellen Sie einen neuen Eintrag und legen Sie ihn auf den Stapel. Wenn Sie fertig sind, nehmen Sie den obersten Eintrag des Stapels und legen Sie den darunter liegenden frei. Verwenden Sie den zuvor obersten Eintrag, um die Rückgabewerte zu extrahieren und den neuen obersten Eintrag entsprechend zu aktualisieren.

Ich schlage vor, dass Sie ein Compiler-Buch studieren, um zu sehen, wie dies normalerweise im Maschinencode implementiert wird.


quelle
Ich verstehe es. Welchen Vorteil hätte eine Rekursion? Einfachheit?
OscarRyz
2
@OscarRyz: Ja, und es ist eleganter.
Michael K
@OscarRyz, die Art, wie ich beschrieben habe, ist Rekursion. Es wird einfach nicht mit nativen CPU-Anweisungen gemacht. Wenn Sie es manuell ausführen, können Sie Dinge wie die Parallelisierung ausführen, die den nativen Anweisungen schlecht zugeordnet sind.
15

Rekursion ist oft eine natürlichere Sichtweise als Iteration. Betrachten Sie beispielsweise das Durchlaufen eines Binärbaums in der Reihenfolge: Dies inorder(left); process(); inorder(right);ist viel einfacher als das explizite Verwalten eines Stapels.

Solange Sie nicht zu tief gehen (den Stapel sprengen), ist der Unterschied in der Ressourcennutzung normalerweise trivial. Mach dir im Allgemeinen keine Sorgen. Einfacher Code ist normalerweise besser als handoptimierter Code, obwohl es Ausnahmen gibt. Richtig ist normalerweise besser als schnell.

Jeder rekursive Algorithmus kann als iterativer Algorithmus ausgedrückt werden. Möglicherweise müssen Sie jedoch einen expliziten Stapel beibehalten (entsprechend dem Aufrufstapel, der implizit behandelt wird). Wenn Sie eine rekursive Funktion kompilieren, erhalten Sie schließlich etwas, das darauf beruht, einen Stapel zu manipulieren und die Funktion zu durchlaufen, und das ist iterativ.

Schwanzrekursive Funktionen können leicht in Schleifen übersetzt werden und benötigen keinen Stapel, aber das ist ein Sonderfall.

David Thornley
quelle
8
Ich würde sagen, dass richtig immer besser als schnell ist. Code, der sehr schnell das Falsche tut, ist für niemanden sehr gut.
Mason Wheeler
1
Aber was ist, wenn Sie das Falsche wirklich schnell tun können ?!
RationalGeek
1
@jkohlhepp - Ich kann jedes Problem sofort lösen. Die Antwort ist 0.
Hinweis für sich selbst - denken Sie an einen Namen
2
Die Verwendung von Rekursion anstelle eines expliziten Stapels kann effizienter sein - ohne Heap-Zuweisungen, mögliche Speicherfragmentierung und mögliche Lokalitätsprobleme. Auf "rechts ist normalerweise besser als schnell" bedeutet ein Stapelüberlauf in Fällen, in denen Ihre Software umgehen muss, dass Ihr Code beschädigt ist. Normalerweise sind Problemfälle ziemlich leicht zu erkennen - eine Rekursion auf einem (einigermaßen) ausgeglichenen Baum ist in Ordnung, aber eine Rekursion auf einem Baum, der möglicherweise sehr unausgeglichen ist, oder auf einer verknüpften Liste kann in einer Sprache wie C. Worse ein schwerwiegender Fehler sein Es kann einfache Tests überstehen und nur dann abstürzen, wenn es tatsächlich bereitgestellt wird.
Steve314
1
Ich denke, Sie alle verstehen, was Mason gemeint hat, und machen nur zum Spaß Witze. Natürlich ist ein langsam korrektes Programm nützlicher als ein schnell falsches Programm.
Giorgio
4

Was sind die Vorteile der Rekursion?

Versuchen Sie, das Problem der Türme von Hanoi iterativ zu lösen. Wenn Sie aufgeben, schauen Sie sich die iterative Lösung an und vergleichen Sie sie mit der rekursiven. Welches ist einfacher?

Ist es möglich, eine iterative Version einer rekursiven Funktion zu haben?

Ja, im Prinzip. Für viele Probleme, einschließlich sehr häufiger Aufgaben wie Baumdurchquerungen, sind die rekursiven Lösungen jedoch viel einfacher und eleganter als die iterativen.

Dima
quelle
3

Was sind die Vorteile der Rekursion?

Einfachheit. Ohne Tail-Call-Optimierung werden natürlich mehr Ressourcen (Stack) benötigt, aber wie würden Sie beispielsweise deltreeohne Rekursion in Java implementieren ? Der Clou ist, dass delete()Verzeichnisse nur gelöscht werden können, wenn sie leer sind. Hier ist es mit Rekursion:

deltree(File fileOrDirectory) {
    if (fileOrDirectory.isDirectory()) {
        for (File subFileOrDirectory : fileOrDirectory.listFiles()) {
            deltree(subFileOrDirectory);
        }
    }
    fileOrDirectory.delete();
}
Joonas Pulakka
quelle
1
Mit einem Stapel, wie in anderen Antworten erwähnt.
Nicole
Ja, aber wie einfach ist das? -)
Joonas Pulakka
Oh, Rekursion ist definitiv besser. Ich dachte, Sie sagten, es sei nicht möglich.
Nicole
0

Ich glaube , dass Rekursion eines dieser Tools ist , dass ein Programmierer muss leben müssen. Mit Rekursion können Sie Ihre Algorithmen "denken" und sie so lösen, wie Sie es sich vorgestellt haben. Aber ich muss Sie warnen, alle reden darüber, wie hübsch Rekursion ist und wie viel Einfachheit der Code bringt, da ich ein paar Dinge zu sagen habe:

  1. Zunächst einmal ist es nicht einfach, den "rekursiven Weg" eines Algorithmus zu denken. Das Bauen einer Funktion wie einer Fakultät (n!) Oder so etwas wie Hanoi Towers ist nur die Spitze des Eisbergs, und das Erreichen des Bodens erfordert eine lange Zeit.
  2. Denken Sie nicht, dass Rekursion nur Einfachheit in Ihren Code bringt. Manchmal ist der iterative Weg hässlich und chaotisch, aber kostengünstig (sehen Sie sich die rekursive Lösung des Fibonacci-Problems an).

Lernen Sie unter Berücksichtigung dieser Dinge die Rekursion! Es ist lustig, komplex und wird dein Gehirn zerschlagen!, aber du wirst feststellen, dass du es liebst.

Viel Glück!

David Conde
quelle