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

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?

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.

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.

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.

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

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!