Rekursion Vs Iteration

Question

Ich glaube, dass alle Probleme, die iterative Logik haben, mit Iterationen gelöst werden können, aber können wir jedes Problem mit Rekursion lösen? Kann Rekursion immer Iteration ersetzen? Bitte geben Sie einen Beweis für Ihre Antwort, wenn Sie können. Nehmen Sie auch an, dass wir einen unendlichen Stapel haben oder wir das Programm auf einer Turing-Maschine ausführen. Es ist mir egal, ob dieser Beweis ein theoretischer Beweis ist. (Deshalb habe ich die Turing-Maschine erwähnt)

Answer 1

Ja, Rekursion kann immer Iteration ersetzen, dies wurde before diskutiert. Zitat aus dem verlinkten Post:

Da Sie eine Turing-vollständige Sprache mit strikt iterativen Strukturen und eine vollständige Turning-Sprache nur mit rekursiven Strukturen bauen können, dann sind die beiden daher gleichwertig.

Erklären ein wenig: wir wissen, dass jedes berechenbare Problem von einer Turing-Maschine gelöst werden kann. Und es ist möglich, eine Programmiersprache A ohne Rekursion zu konstruieren, das entspricht einer Turing-Maschine. In ähnlicher Weise ist es möglich, eine Programmiersprache B ohne Iteration zu bauen, die in Rechenleistung mit einer Turing-Maschine gleich ist.

Wenn also sowohl A als auch BTuring-complete sind, können wir daraus schließen, dass für jedes iterative Programm ein äquivalentes rekursives Programm existieren muss und umgekehrt. Dies ist ein theoretisches Ergebnis in dem Sinne, dass es keine Hinweise darauf gibt, wie man ein rekursives Programm von einem beliebigen iterativen Programm ableitet oder umgekehrt.

Answer 2

Ja. Es gibt einen Rekursionstyp namens tail recursion, der direkt in die Iteration übersetzbar ist. Man kann problemlos zum anderen konvertiert werden. Somit können alle iterativen Lösungen in rekursive Lösungen umgewandelt werden.

Tatsächlich können viele Compiler erkennen, dass Sie eine Tail-Rekursion durchführen, und diese dann zur Effizienz in einen Code vom Typ "for-loop" umwandeln.

Answer 3

Eine Rekursion sollte verwendet werden, wenn eine Schleife nicht benötigt wird, aber die Methode muss sich in einem bestimmten Fall wiederholen. Zum Beispiel, einen Ordner zippen. Wenn es einen Unterordner gibt, sollte er sich selbst nennen (rekursiv). Rekursion könnte Iterationen ersetzen, wenn Sie möchten, aber es wird nicht empfohlen. Die meisten Leute verwenden nur Iterationen und verwenden nur Rekursionen, wenn sie benötigt werden.