wake-up-neo.com

Kann jede Rekursion in eine Iteration umgewandelt werden?

Ein reddit thread hat eine anscheinend interessante Frage aufgeworfen:

Schwanzrekursive Funktionen können trivial in iterative Funktionen umgewandelt werden. Andere können mithilfe eines expliziten Stacks transformiert werden. Kann jede Rekursion in eine Iteration umgewandelt werden?

Das (counter?) Beispiel im Beitrag 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))
174
Tordek

Können Sie eine rekursive Funktion immer in eine iterative umwandeln? Ja, absolut, und die Church-Turing-These beweist es, wenn das Gedächtnis dient. Laienhaft ausgedrückt heißt es, dass das, was durch rekursive Funktionen berechenbar ist, durch ein iteratives Modell (wie die Turing-Maschine) berechenbar ist und umgekehrt. Die Arbeit sagt Ihnen nicht genau, wie Sie die Konvertierung durchführen sollen, aber sie sagt, dass dies definitiv möglich ist.

In vielen Fällen ist das Konvertieren einer rekursiven Funktion einfach. Knuth bietet verschiedene Techniken in "The Art of Computer Programming" an. Und oft kann eine Sache, die rekursiv berechnet wird, durch einen völlig anderen Ansatz in weniger Zeit und Raum berechnet werden. Das klassische Beispiel hierfür sind Fibonacci-Zahlen oder deren Folgen. Sie haben dieses Problem sicherlich in Ihrem Studienplan angetroffen.

Auf der anderen Seite dieser Medaille können wir uns sicherlich ein Programmiersystem vorstellen, das so fortschrittlich ist, dass es eine rekursive Definition einer Formel als Aufforderung ansieht, frühere Ergebnisse zu speichern, und so den Geschwindigkeitsvorteil bietet, ohne dem Computer genau sagen zu müssen, welche Schritte erforderlich sind Folgen Sie der Berechnung einer Formel mit einer rekursiven Definition. Dijkstra hat sich mit ziemlicher Sicherheit ein solches System vorgestellt. Er hat lange versucht, die Implementierung von der Semantik einer Programmiersprache zu trennen. Andererseits liegen seine nicht deterministischen und mehrfach verarbeitenden Programmiersprachen in einer Liga über dem praktizierenden professionellen Programmierer.

Letztendlich sind viele Funktionen einfach einfacher zu verstehen, zu lesen und in rekursiver Form zu schreiben. Sofern kein zwingender Grund vorliegt, sollten Sie diese Funktionen wahrscheinlich nicht (manuell) in einen explizit iterativen Algorithmus konvertieren. Ihr Computer wird diesen Job korrekt ausführen.

Ich kann einen zwingenden Grund sehen. Angenommen, Sie haben ein Prototypsystem in einer überragenden Sprache wie [Asbestunterwäsche anziehen] Scheme, LISP, Haskell, OCaml, Perl oder Pascal. Angenommen, die Bedingungen sind so, dass Sie eine Implementierung in C oder Java benötigen. (Vielleicht ist es Politik.) Dann könnten Sie sicherlich einige Funktionen rekursiv schreiben lassen, die aber, wörtlich übersetzt, Ihr Laufzeitsystem sprengen würden. Beispielsweise ist in Schema eine unendliche Schwanzrekursion möglich, aber dieselbe Redewendung verursacht ein Problem in vorhandenen C-Umgebungen. Ein weiteres Beispiel ist die Verwendung von lexikalisch verschachtelten Funktionen und statischem Gültigkeitsbereich, die Pascal unterstützt, C jedoch nicht.

Unter diesen Umständen könnten Sie versuchen, den politischen Widerstand gegen die Originalsprache zu überwinden. Sie könnten feststellen, dass Sie LISP schlecht umsetzen, wie in Greenspuns (ironischem) zehntem Gesetz. Oder Sie finden einfach einen völlig anderen Lösungsansatz. Aber auf jeden Fall gibt es sicherlich einen Weg.

175
Ian

Ist es immer möglich, für jede rekursive Funktion ein nicht-rekursives Formular zu schreiben?

Ja. Ein einfacher formaler Beweis soll zeigen, dass sowohl µ-Rekursion als auch ein nicht-rekursiver Kalkül wie GOTO vollständig sind. Da alle Turing-Vervollständigungskalküle in ihrer Ausdruckskraft streng äquivalent sind, können alle rekursiven Funktionen durch die nicht-rekursive Turing-Vervollständigungskalküle implementiert werden.

Leider kann ich keine gute, formale Definition von GOTO online finden.

Ein GOTO-Programm ist eine Folge von Befehlen [~ # ~] p [~ # ~] , die auf einer Registermaschine wie z das [~ # ~] p [~ # ~] ist eine der folgenden:

  • HALT, was die Ausführung anhält
  • r = r + 1 woher r ist ein beliebiges Register
  • r = r – 1 woher r ist ein beliebiges Register
  • GOTO x woher x ist ein Label
  • IF r ≠ 0 GOTO x woher r ist ein beliebiges Register und x ist ein Label
  • Eine Bezeichnung, gefolgt von einem der oben genannten Befehle.

Die Konvertierungen zwischen rekursiven und nicht rekursiven Funktionen sind jedoch nicht immer trivial (außer durch sinnlose manuelle Neuimplementierung des Aufrufstapels).

Weitere Informationen finden Sie unter diese Antwort .

39
Konrad Rudolph

Die Rekursion wird als Stapel oder ähnliche Konstrukte in den eigentlichen Interpretern oder Compilern implementiert. Sie können also sicherlich eine rekursive Funktion in eine iterative konvertieren weil das immer so gemacht wird (wenn automatisch). Sie duplizieren die Arbeit des Compilers nur ad-hoc und wahrscheinlich auf sehr hässliche und ineffiziente Weise.

27
Vinko Vrsalovic

Grundsätzlich ja, im Wesentlichen müssen Sie Methodenaufrufe (die implizit den Status auf den Stapel schieben) durch explizite Stapelschübe ersetzen, um sich daran zu erinnern, wo der 'vorherige Aufruf' angekommen ist, und dann die 'aufgerufene Methode' ausführen. stattdessen.

Ich könnte mir vorstellen, dass die Kombination aus einer Schleife, einem Stapel und einer Zustandsmaschine für alle Szenarien verwendet werden kann, indem die Methodenaufrufe im Grunde simuliert werden. Ob dies "besser" (entweder schneller oder in gewissem Sinne effizienter) sein wird, kann im Allgemeinen nicht wirklich gesagt werden.

12
jerryjvl
  • Der Ablauf der Ausführung rekursiver Funktionen kann als Baum dargestellt werden.

  • Dieselbe Logik kann durch eine Schleife ausgeführt werden, die eine Datenstruktur verwendet, um diesen Baum zu durchlaufen.

  • Die Durchquerung der Tiefe kann über einen Stapel erfolgen, die Durchquerung der Breite über eine Warteschlange.

Die Antwort lautet also: Ja. Warum: https://stackoverflow.com/a/531721/2128327 .

Kann eine Rekursion in einer einzelnen Schleife durchgeführt werden? Ja, weil

eine Turing-Maschine macht alles, was sie macht, indem sie eine einzelne Schleife ausführt:

  1. eine Anweisung holen,
  2. bewerte es,
  3. gehe zu 1.
9
Khaled.K

Ja, explizit einen Stack verwenden (aber Rekursion ist viel angenehmer zu lesen, IMHO).

6
dfa

Ja, es ist immer möglich, eine nicht rekursive Version zu schreiben. Die einfache Lösung besteht darin, eine Stack-Datenstruktur zu verwenden und die rekursive Ausführung zu simulieren.

6
Heinzi

Grundsätzlich ist es immer möglich, die Rekursion zu entfernen und durch eine Iteration in einer Sprache zu ersetzen, die sowohl für Datenstrukturen als auch für den Aufrufstapel einen unendlichen Zustand aufweist. Dies ist eine grundlegende Konsequenz der Church-Turing-These.

Bei einer tatsächlichen Programmiersprache ist die Antwort nicht so offensichtlich. Das Problem ist, dass es durchaus möglich ist, eine Sprache zu haben, in der die Menge an Speicher, die im Programm zugewiesen werden kann, begrenzt ist, aber die Menge an Aufrufstapel, die verwendet werden kann, unbegrenzt ist (32-Bit-C, wo die Adresse von Stapelvariablen ist ist nicht zugänglich). In diesem Fall ist die Rekursion leistungsfähiger, weil sie über mehr Speicher verfügt, den sie verwenden kann. Es ist nicht genügend explizit zuweisbarer Speicher vorhanden, um den Aufrufstapel zu emulieren. Eine ausführliche Diskussion hierzu finden Sie unter diese Diskussion .

3
Zayenz

Manchmal ist es viel einfacher, die Rekursion zu ersetzen. Rekursion war in den Neunzigerjahren die Modeerscheinung in CS, und so dachten viele durchschnittliche Entwickler aus dieser Zeit, wenn man etwas mit Rekursion löste, wäre es eine bessere Lösung. Sie würden also eine Rekursion verwenden, anstatt rückwärts zu schleifen, um die Reihenfolge umzukehren, oder dumme Dinge wie diese. Manchmal ist das Entfernen von Rekursionen eine einfache Übung.

Dies ist jetzt weniger problematisch, da sich die Mode auf andere Technologien verlagert hat.

1
Matthias Wandel

Alle berechenbaren Funktionen können von Turing-Maschinen berechnet werden, und daher sind die rekursiven Systeme und Turing-Maschinen (iterative Systeme) gleichwertig.

1
JOBBINE

Werfen Sie einen Blick auf die folgenden Einträge auf Wikipedia, um eine vollständige Antwort auf Ihre Frage zu finden.

Befolgen Sie einen Absatz, der Ihnen einen Hinweis geben kann, wo Sie anfangen sollen:

Das Lösen einer Wiederholungsrelation bedeutet das Erhalten einer Lösung in geschlossener Form : einer nicht-rekursiven Funktion von n.

Schauen Sie sich auch den letzten Absatz von dieser Eintrag an.

0

Es ist möglich, jeden rekursiven Algorithmus in einen nicht rekursiven Algorithmus umzuwandeln, aber häufig ist die Logik viel komplexer und erfordert die Verwendung eines Stapels. Tatsächlich verwendet die Rekursion selbst einen Stapel: den Funktionsstapel.

Weitere Details: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Functions

0
Teoman shipahi

Das Entfernen der Rekursion ist ein komplexes Problem und unter genau definierten Umständen möglich.

Die folgenden Fälle gehören zu den einfachen:

0

Ich würde ja sagen - ein Funktionsaufruf ist nichts anderes als eine Goto-und-Stack-Operation (grob gesagt). Alles, was Sie tun müssen, ist, den Stapel zu imitieren, der beim Aufrufen von Funktionen erstellt wurde, und etwas Ähnliches wie goto zu tun (Sie können gotos auch mit Sprachen imitieren, die dieses Schlüsselwort nicht explizit enthalten).

0
sfussenegger

Abgesehen vom expliziten Stapel wird ein weiteres Muster zum Umwandeln der Rekursion in Iteration mit einem Trampolin verwendet.

Hier geben die Funktionen entweder das Endergebnis oder einen Abschluss des Funktionsaufrufs zurück, den sie sonst ausgeführt hätten. Dann ruft die auslösende (Trampolin-) Funktion die zurückgegebenen Verschlüsse so lange auf, bis das endgültige Ergebnis erreicht ist.

Dieser Ansatz funktioniert für sich gegenseitig rekursive Funktionen, aber ich fürchte, er funktioniert nur für Tail-Calls.

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

0
Chris Vest