Kann jeder Rekursion in Iteration umgewandelt werden?

https://stackoverflow.com/questions/931762

06-09-2019
|

Frage

reddit fädeln eine scheinbar interessante Frage aufgeworfen:

Schwanz rekursive Funktionen können trivialerweise in iterativen Funktionen umgewandelt werden. Andere diejenigen, können durch die Verwendung eines expliziten Stapel umgewandelt werden. Kann alle Rekursion in Iteration umgewandelt werden?

(? Zähler) Beispiel in der Post ist das Paar:

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

Lösung

Können Sie immer eine rekursive Funktion in einem iterativen eine Umdrehung? Ja, absolut, und die Kirche-Turing-These erweist es sich, wenn der Speicher dient. In Laien ausgedrückt, heißt es, dass berechenbar was durch rekursive Funktionen durch ein iteratives Modell (wie die Turing Maschine) berechenbar ist, und umgekehrt. Die These ist Ihnen nicht genau sagen, wie die Konvertierung zu tun, aber es sagt, dass es auf jeden Fall möglich.

In vielen Fällen ist eine rekursive Funktion Konvertierung einfach. Knuth bietet verschiedene Techniken in "The Art of Computer Programming". Und oft, berechnet ein Ding rekursiv durch einen völlig anderen Ansatz in kürzerer Zeit und Raum berechnet werden. Das klassische Beispiel ist Fibonacci-Zahlen oder Sequenzen davon. Sie haben sicherlich dieses Problem in Ihrem Grad Plan erfüllt werden.

Auf der Kehrseite der Medaille, können wir uns vorstellen, sicherlich ein Programmiersystem so weit fortgeschritten, als eine rekursive Definition einer Formel als Einladung zur Behandlung von früheren Ergebnissen memoize, wodurch die Geschwindigkeit profitieren, ohne den Aufwand und bietet von den Computer zu sagen genau wobei die Schritte in der Berechnung einer Formel mit einer rekursiven Definition zu folgen. Dijkstra hat fast sicher vorstellen, ein solches System. Er verbrachte eine lange Zeit versucht, die Umsetzung von der Semantik einer Programmiersprache zu trennen. Dann wieder, seine nicht-deterministisch und Multiprocessing-Programmiersprachen sind in einer Liga über dem praktizierenden professionellen Programmierer.

In der abschließenden Analyse sind viele Funktionen einfach nur leichter zu verstehen, zu lesen, und in rekursiven Form zu schreiben. Es sei denn, es besteht ein zwingender Grund ist, sollten Sie wahrscheinlich nicht (manuell), um diese Funktionen zu einem explizit iterativen Algorithmus konvertieren. Ihr Computer wird behandelt diesen Job richtig.

Ich kann einen zwingenden Grund sehen. Angenommen, Sie haben ein Prototyp-System in einer Super-High-Level-Sprache wie [ Anziehen Asbest Unterwäsche ] Schema, Lisp, Haskell, OCaml, Perl oder Pascal. Es sei Bedingungen so sind, dass Sie eine Implementierung in C oder Java benötigen. (Vielleicht ist es die Politik.) Dann könnten Sie haben sicherlich einige Funktionen rekursiv geschrieben, aber die, wörtlich übersetzt, würde Ihr Laufzeitsystem explodieren. Zum Beispiel ist unendlich Endrekursion möglich in Schema, aber das gleiche Idiom verursacht ein Problem für bestehende C-Umgebungen. Ein weiteres Beispiel ist die Verwendung von lexikalisch verschachtelten Funktionen und statischen Rahmen, die Pascal unterstützt aber C nicht.

Unter diesen Umständen könnten Sie versuchen, politischen Widerstand zu der Originalsprache zu überwinden. Sie könnten sich Lisp schlecht Neuimplementierung finden, wie in Greenspun der (tongue-in-cheek) zehnte Gesetz. Oder Sie könnten nur einen völlig anderen Ansatz zur Lösung finden. Aber auf jeden Fall, es ist sicherlich ein Weg.

Andere Tipps

Ist es immer möglich, eine nicht-rekursive Form für jede rekursive Funktion zu schreiben?

Ja. Ein einfacher Beweis ist, formal zu zeigen, dass sowohl μ Rekursion und ein nicht rekursive Kalkül wie GOTO sind beide Turing abgeschlossen. Da alle Turing komplette Kalküle in ihrer Ausdruckskraft absolut gleichwertig sind, werden alle rekursiven Funktionen können durch die nicht-rekursive Turing-complete Kalkül umgesetzt werden.

Leider bin ich nicht in der Lage eine gute, formale Definition von GOTO online zu finden ist so hier ein:

Ein GOTO-Programm ist eine Folge von Befehlen P auf Maschine registrieren so dass P ist eine der folgenden Möglichkeiten:

HALT, die Ausführung stoppt
r = r + 1 wo r ist jedes Register
r = r – 1 wo r ist jedes Register
GOTO x wo x ist ein Label
IF r ≠ 0 GOTO x wo r ist jedes Register und x ist ein Label
Ein Etikett, durch eine der oben genannten Befehle befolgt.

Allerdings ist die Konvertierungen zwischen rekursiven und nicht-rekursive Funktionen sind nicht immer trivial (mit Ausnahme von sinnloser manueller Re-Implementierung des Call-Stack).

Weitere Informationen finden Sie unter diese Antwort .

Rekursion wird als Stapel oder ähnliche Konstrukte, die in den tatsächlichen Interpreter oder Compiler implementiert. So können Sie sicher eine rekursive Funktion zu einem iterativen Pendant konvertieren, weil das ist, wie es immer getan (wenn automatisch) . Sie werden nur die Arbeit der Compiler Duplizieren in einer Ad-hoc-und wahrscheinlich in einem sehr hässlich und ineffiziente Art und Weise.

Im Prinzip ja, im Grunde, was Sie am Ende zu tun ist, Methodenaufrufe ersetzen in explizite Stapel (die implizit Zustand auf den Stapel schieben) schiebt sich daran zu erinnern, wo die ‚letzten Aufruf‘ hatte, aufgestanden und führen Sie dann die ' genannt Methode‘statt.

Ich könnte mir vorstellen, dass die Kombination aus einer Schleife, einem Stapel und einer Zustandsmaschine durch grundsätzlich Simulation der Methodenaufrufe für alle Szenarien verwendet werden könnten. Ob dies sein wird, ‚besser‘ (entweder schneller oder effizienter in gewissem Sinne) ist nicht wirklich möglich, im Allgemeinen zu sagen.

rekursive Funktion Ausführungsablauf kann als Baum dargestellt werden.
Die gleiche Logik kann durch eine Schleife durchgeführt werden, die eine Datenstruktur verwendet, den Baum zu durchqueren.
Depth-first Traversal kann mit einem Stapel, Breiten ersten Traversal kann unter Verwendung einer Warteschlange getan werden, durchgeführt werden.

Also, die Antwort lautet: ja. Warum: https://stackoverflow.com/a/531721/2128327

Kann jede Rekursion in einer einzigen Schleife durchgeführt werden? Ja, denn

eine Turing-Maschine tut alles, was es tut, durch eine einzige Schleife ausführen:


holt einen Befehl,

auswerten,

gehe zu 1.

Ja, es ist immer möglich, eine nicht-rekursive Version zu schreiben. Die triviale Lösung ist, eine Stapeldatenstruktur zu verwenden und die rekursive Ausführung zu simulieren.

Ja, mit explizit einen Stapel (aber Rekursion ist viel angenehmer zu lesen, IMHO).

Im Prinzip ist es immer möglich, die Rekursion zu entfernen und durch Iteration in einer Sprache zu ersetzen, die unendlichen Zustand sowohl für Datenstrukturen und für den Call-Stack. Dies ist eine grundlegende Folge der Kirche-Turing-These.

eine tatsächliche Programmiersprache gegeben, ist die Antwort nicht so offensichtlich ist. Das Problem ist, dass es durchaus möglich ist, eine Sprache zu haben, wo die Menge an Speicher, die in dem Programm zugeordnet werden können, beschränkt ist, sondern wo die Menge des Call-Stack, der verwendet werden kann unbegrenzt (32-Bit-C, wo die Adresse des Stack-Variablen ist nicht zugänglich). In diesem Fall ist Rekursion mächtiger, nur weil es mehr Speicher hat, kann sie verwenden; es gibt nicht genug explizit zuweisbaren Speicher den Call-Stack zu emulieren. Für eine detaillierte Diskussion zu diesem Thema, dieses Diskussion .

Manchmal ersetzt Rekursion ist viel einfacher als das. Rekursion verwendete die modische Sache in den 1990er Jahren in CS gelehrt zu sein, und so viele durchschnittlichen Entwickler von dieser Zeit dachte, wenn Sie etwas mit Rekursion gelöst, es war eine bessere Lösung. So würden sie rückwärts Rekursion statt Schleife verwenden, um rückwärts oder dumme Sachen. Also manchmal Entfernen Rekursion ist ein einfacher „duh, das war offensichtlich“ Art der Übung.

Dies ist weniger ein Problem, jetzt, da die Art und Weise gegenüber anderen Technologien verschoben hat.

Alle berechenbaren Funktionen können von Turing-Maschinen und damit die rekursiven Systeme und Turing-Maschinen (iterative Systeme) sind äquivalent berechnet werden.

Entfernen von Rekursion ist ein komplexes Problem und ist machbar unter genau definierten Umständen.

Die folgenden Fälle sind unter den einfach:

Endrekursion
direkte lineare Rekursion

Appart vom expliziten Stapel, ein anderes Muster Rekursion in Iteration für die Umwandlung ist mit der Verwendung von einem Trampolin.

Dabei kann entweder die Funktionen des Endergebnisses zurückzukehren, oder eine Schließung der Funktionsaufruf, dass es auch anders ausgeführt hätte. Dann halten die initiierende (trampolining) -Funktion die Verschlüsse Aufruf zurückgegeben, bis das Endergebnis erreicht wird.

Dieser Ansatz funktioniert für beide Seiten rekursiven Funktionen, aber ich fürchte, es funktioniert nur für Schwanz-Anrufe.

http://en.wikipedia.org/wiki/Trampoline_(computers)

Ich würde sagen, ja - ein Funktionsaufruf ist nichts anderes als ein goto und eine Stapeloperation (grob gesagt). Alles, was Sie tun müssen, ist, den Stapel zu imitieren, die während Aufrufen von Funktionen integriert ist und ähnlich wie eine goto etwas tun (Sie gotos mit Sprachen nachahmen kann, die nicht ausdrücklich zu diesem Schlüsselwort haben).

Haben Sie einen Blick auf die folgenden Einträge auf wikipedia, können Sie sie als Ausgangspunkt verwenden können, eine vollständige Antwort auf Ihre Frage zu finden.

Es folgt eine Ziffer, die Sie einen Hinweis auf möglicherweise geben, wo ich anfangen:

eine Rekursionsformel Mittel zur Lösung wird ein geschlossene Lösung : eine nicht- rekursive Funktion von n.

Haben Sie auch einen Blick auf die letzten Absatz von diesen Eintrag .

Es ist möglich, jeden rekursive Algorithmus auf eine nicht-rekursive zu konvertieren ein, aber oft die Logik ist viel komplexer und erfordert dabei die Verwendung von einem Stapel. In der Tat, Rekursion selbst verwendet einen Stapel: die Funktion Stack.

Weitere Informationen: https://developer.mozilla.org / en-US / docs / Web / JavaScript / Guide / Funktionen

tazzego bedeutet Rekursion, dass eine Funktion selbst nennen, ob es Ihnen gefällt oder nicht. Wenn die Leute reden, ob die Dinge nicht ohne Rekursion durchgeführt werden, meinen sie dies und man kann nicht sagen: „Nein, das ist nicht wahr, weil ich mit der Definition der Rekursion nicht einverstanden“ als gültige Aussage.

Mit dem im Verstand, so ziemlich alles, was Sie sagen, ist Unsinn. Die einzige andere Sache, die Sie sagen, dass kein Unsinn ist, ist die Idee, dass Sie nicht die Programmierung ohne Aufrufliste vorstellen können. Das ist etwas, das bis unter Verwendung eines Callstack wurde populär seit Jahrzehnten hatte. Alte Versionen von Fortran fehlte eine Aufrufliste und sie funktionierte gut.

By the way, gibt es Turing-complete Sprachen, die nur Rekursion (zum Beispiel SML) als Mittel zur Schleife implementieren. Es gibt auch Turing-complete Sprachen, die nur als Mittel implementieren Iteration der Schleife (z Fortran IV). Die Kirche-Turing-These beweist, dass alles möglich in einer Rekursion nur für Sprachen können in einer nicht-rekursive Sprache und umgekehrt durch die Tatsache gemacht werden, dass sie sowohl die Eigenschaft der Turing-Vollständigkeit haben.

Hier ist ein iterativer Algorithmus:

def howmany(x,y)
  a = {}
  for n in (0..x+y)
    for m in (0..n)
      a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
    end
  end
  return a[[x,y]]
end

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow