Rekursion entfernen - ein Blick in die Theorie hinter den Kulissen

10

Ich bin neu auf dieser Seite und diese Frage ist sicherlich nicht auf Forschungsniveau - aber na ja. Ich habe einen kleinen Hintergrund in Software-Engineering und fast keinen in CSTheory, aber ich finde es attraktiv. Um es kurz zu machen, ich möchte eine detailliertere Antwort auf Folgendes, wenn diese Frage auf dieser Website akzeptabel ist.

Ich weiß also, dass jedes rekursive Programm ein iteratives Analogon hat, und ich verstehe die beliebte Erklärung, die dafür angeboten wird, indem ich etwas Ähnliches wie den "Systemstapel" behalte und Umgebungseinstellungen wie die Absenderadresse usw. drücke. Ich finde diese Art von Handwellen .

Da ich etwas konkreter bin, möchte ich (formal) sehen, wie man diese Aussage in Fällen beweist, in denen Sie eine Funktion haben, die die Kette . Außerdem was ist, wenn es einige bedingten Anweisungen , die einen führen könnten einen Anruf zu einem gewissen machen ? Das heißt, der potenzielle Funktionsaufrufgraph enthält einige stark verbundene Komponenten. $F_0 \rightarrow F_1 \ldots F_i \rightarrow F_{i+1} \ldots F_n \rightarrow F_0$ $F_i$ $F_j$

Ich würde gerne wissen, wie mit diesen Situationen umgegangen werden kann, indem wir einige rekursive zu iterativen Konverter sagen. Und ist die Handwellenbeschreibung, auf die ich mich zuvor bezogen habe, wirklich genug für dieses Problem? Ich meine, warum finde ich es dann in einigen Fällen einfach, die Rekursion zu entfernen? Insbesondere das Entfernen der Rekursion aus der Vorbestellungsdurchquerung eines Binärbaums ist wirklich einfach - es ist eine Standard-Interviewfrage, aber das Entfernen der Rekursion im Falle einer Nachbestellung war für mich immer ein Albtraum.

Was ich wirklich stelle, sind Fragen $2$

(1) Gibt es wirklich einen formelleren (überzeugenden?) Beweis dafür, dass Rekursion in Iteration umgewandelt werden kann?

(2) Wenn diese Theorie wirklich da draußen ist, warum finde ich es dann beispielsweise einfacher , die Vorbestellung einfacher und die Nachbestellung so schwer zu iterieren? (außer meiner begrenzten Intelligenz)

pl.programming-languages recursion recursive Itachi Uchiha
quelle

1

wie das Wort iterieren :)

Akash Kumar

Ich bin nicht sicher, ob ich es vollständig verstehe, aber wenn die Rekursion irgendwo endet, können Sie tatsächlich einen Systemstapel mit Ihrem eigenen Stapel simulieren. Für Teil (2) unterscheiden sich die Probleme nicht in Bezug auf die Rechenkomplexität.

singhsumit

Ich denke, diese Frage wäre am besten für die Informatik- Site geeignet gewesen, die noch nicht live ist. Können Sie bei Ihrer zweiten Frage erläutern, warum Sie der Meinung sind, dass es schwieriger ist? Der Prozess sollte fast identisch sein.

Raphael

Vielen Dank an alle für Ihre Kommentare - ich schätze, ich habe noch einiges zu lesen.

Itachi Uchiha

@Raphael - Ein Kommentar darüber, warum ich es für schwierig halte, Postorder zu iterieren (außer dass ich es nicht kann). Ich habe ein paar Artikel über das Entfernen von Rekursion gelesen und bin auf so genannte rekursive Schwanzfunktionen gestoßen. Es stellt sich heraus, dass sie leichter zu iterieren sind. Ich verstehe formal immer noch nicht, warum dies wahr ist; Aber ich sollte noch etwas hinzufügen. Ich habe gehört, dass das Iterieren der Nachbestellung zwei Stapel erfordert und nicht einen, aber ich kenne die Details nicht. Und jetzt bin ich verloren - warum dieser Unterschied zwischen diesen beiden Traversal-Modi? Und warum ist die Schwanzrekursion einfach zu handhaben?

Itachi Uchiha

6

Wenn ich das richtig verstehe, ist Ihnen klar, dass Sie Funktionen konvertieren, die keine anderen Funktionsaufrufe als sich selbst enthalten.

So nehmen wir eine "Call - Kette" haben . Wenn wir weiterhin davon aus, dass sind sich nicht rekursiv (weil wir sie bereits umgesetzt haben), können wir inline alle diese Anrufe in die Definition von , die auf diese Weise eine direkt rekursive Funktion wird können wir bereits beschäftigen. $F \to F_1 \to \dots \to F_n \to F$ $F_1, \dots, F_n$ $F$

Dies schlägt fehl, wenn einige selbst eine rekursive Aufrufkette haben, in der auftritt, dh . In diesem Fall haben wir eine gegenseitige Rekursion, die einen weiteren Trick erfordert, um sie loszuwerden. Die Idee ist, beide Funktionen gleichzeitig zu berechnen. Zum Beispiel im trivialen Fall: $F_j$ $F$ $F_j \to \dots \to F \to \dots \to F_j$

f(0) = a
f(n) = f'(g(n-1))

g(0) = b
g(n) = g'(f(n-1))

mit f'und g'nicht rekursiven Funktionen (oder zumindest unabhängig von fund g) wird

h(0) = (a,b)
h(n) = let (f,g) = h(n-1) in (f'(g), g'(f)) end

f(n) = let (f, _) = h(n) in f end
g(n) = let (_, g) = h(n) in g end

Dies erstreckt sich natürlich auf mehr beteiligte Funktionen und kompliziertere Funktionen.

Raphael
quelle

Froh, dass ich helfen konnte. Bitte denken Sie daran, Ihre Lieblingsantwort zu akzeptieren, indem Sie auf das Häkchen daneben klicken.

Raphael

1

Raphel, Ihr Trick funktioniert nur, wenn beide rekursiven Funktionen Argumente desselben Typs akzeptieren. Wenn fund gverschiedene Arten von Typen zu akzeptieren, ein allgemeinere Trick benötigt.

Andrej Bauer

@AndrejBauer gute Beobachtung, das habe ich total vermisst. Ich mochte Raphaels Ansatz sehr, aber wie Sie im Allgemeinen beobachtet haben, brauchen wir wahrscheinlich eine andere Idee. Können Sie weitere Vorschläge machen?

Itachi Uchiha

@AndrejBauer Stimmt. Ich dachte aus rekursionstheoretischer Sicht; hier haben wir nur natürliche Zahlen. Dies ist ausreichend, da wir alles auf geeignete Weise codieren können. Aber Ihr Punkt ist für die Praxis sehr gültig. Ich denke, wir müssten umschreiben fund gbis sie ein gemeinsames Eingabecodierungs- und Rekursionsschema haben (wir können nicht eines haben, das und das andere ).

n - 1

$n-1$

n - 2

$n-2$

Raphael

Nun, siehe meine Antwort, wie es geht.

Andrej Bauer

8

Ja, es gibt überzeugende Gründe zu der Annahme, dass Rekursion in Iteration umgewandelt werden kann. Dies tut jeder Compiler, wenn er Quellcode in die Maschinensprache übersetzt. Theoretisch sollten Sie den Vorschlägen von Dave Clarke folgen. Wenn Sie tatsächlichen Code sehen möchten, der Rekursion in nicht rekursiven Code konvertiert, sehen Sie sich machine.mldie MiniML-Sprache in meinem PL Zoo an (beachten Sie, dass die loopFunktion unten, die tatsächlich Code ausführt, schwanzrekursiv ist und dies auch kann trivial in eine tatsächliche Schleife umgewandelt werden).

Eine Sache noch. MiniML unterstützt keine gegenseitig rekursiven Funktionen. Das ist aber kein Problem. Wenn Sie eine gegenseitige Rekursion zwischen Funktionen haben

f_{1} : A_{1} \to B_{1}

$f_1 : A_1 \to B_1$

f_{2} : A_{2} \to B_{2}

$f_2 : A_2 \to B_2$

⋮

$\vdots$

f_{n} : A_{n} \to B_{n}

$f_n : A_n \to B_n$

Die Rekursion kann in Form einer einzelnen rekursiven Karte ausgedrückt werden

f : A_{1} + \dots + A_{n} \to B_{1} + \dots + B_{n},

$f : A_1 + \cdots + A_n \to B_1 + \cdots + B_n,$

Andrej Bauer
quelle

8

Vielleicht möchten Sie sich die SECD-Maschine ansehen . Eine funktionale Sprache (obwohl es sich um eine beliebige Sprache handeln kann) wird in eine Reihe von Anweisungen übersetzt, die beispielsweise das Setzen von Argumenten von Stapeln, das "Aufrufen" neuer Funktionen usw. verwalten, die alle von einer einfachen Schleife verwaltet werden.
Rekursive Aufrufe werden nie aufgerufen. Stattdessen werden die Anweisungen des Hauptteils der aufgerufenen Funktion zum Ausführen auf den Stapel gelegt.

Ein verwandter Ansatz ist die CEK-Maschine .

Beide gibt es schon lange, daher gibt es viel zu tun. Und natürlich gibt es Beweise dafür, dass sie funktionieren, und das Verfahren zum "Kompilieren" eines Programms in SECD-Anweisungen ist in der Größe des Programms linear (es muss nicht über das Programm nachdenken).

Der Punkt meiner Antwort ist, dass es ein automatisches Verfahren gibt, um das zu tun, was Sie wollen. Leider wird die Transformation nicht unbedingt in Bezug auf Dinge erfolgen, die für einen Programmierer sofort leicht zu interpretieren sind. Ich denke, der Schlüssel ist, dass Sie, wenn Sie ein Programm iterieren möchten, auf dem Stapel speichern müssen, was das Programm tun muss, wenn Sie von einem iterierten Funktionsaufruf zurückkehren (dies wird als Fortsetzung bezeichnet). Für einige Funktionen (wie z. B. rekursive Funktionen) ist die Fortsetzung trivial. Für andere ist die Fortsetzung möglicherweise sehr komplex, insbesondere wenn Sie sie selbst codieren müssen.

Dave Clarke
quelle

Ich werde hier ehrlich sein. Ich möchte wirklich verstehen, warum (und wie) Sie jedes rekursive Programm iterieren können. Aber ich finde es schwierig, eine Zeitung durchzulesen - sie sind mir normalerweise nicht zugänglich. Ich meine, ich möchte einen tieferen Grund als die "handgewellte" Beschreibung, über die ich in der Frage gesprochen habe. aber ich bin auch glücklich mit etwas, das mir neue Einblicke gibt - es muss nicht der ganze Beweis in seinen kleinen Details sein

Itachi Uchiha

[cntd] Ich meine, ich werde den Beweis mögen, wenn es einen gibt, um mir zu sagen, warum es einfacher ist, ein Programm zu iterieren als das andere. In gewissem Sinne sollte der Konverter von rekursiv zu iterativ funktionieren, unabhängig davon, welches rekursive Programm als Eingabe verwendet wird. Nicht sicher, aber ich denke, ein solcher Konverter könnte etwas so Schwieriges sein wie das Problem des Anhaltens? Ich rate hier nur - aber ich würde es lieben, wenn ein Konverter von rekursiv zu iterativ existiert, und wenn ja, möchte ich, dass er die inhärente Komplexität der Iteration verschiedener rekursiver Programme erklärt. bin mir nicht sicher, aber soll ich die frage bearbeiten? Ist meine Frage klar?

Itachi Uchiha

@ItachiUchiha - Ich glaube nicht, dass Ihr Problem unentscheidbar ist. Schauen Sie sich die Antwort von Andrej Bauer an. Er stellt fest, dass jeder Compiler dies tut, wenn er Quellcode in die Maschinensprache übersetzt. Außerdem fügt er hinzu, dass Sie den tatsächlichen Code sehen können, der rekursiv in nicht rekursiv in der Sprache MiniM (a) l konvertiert. Dies zeigt deutlich, dass es ein Entscheidungsverfahren gibt, um die Rekursion zu "iterieren". Ich bin mir nicht sicher über die inhärente (konzeptionelle) Schwierigkeit / Komplexität des Entfernens von Rekursion. Ich verstehe diese Frage nicht sehr klar, aber sie sieht interessant aus. Vielleicht können Sie Ihre Frage bearbeiten, um eine bessere Antwort zu erhalten

Akash Kumar

Der Punkt meiner Antwort ist, dass es ein automatisches Verfahren gibt, um das zu tun, was Sie wollen. Leider wird die Transformation nicht unbedingt in Bezug auf Dinge erfolgen, die für einen Programmierer sofort leicht zu interpretieren sind. Ich denke, der Schlüssel ist, dass Sie, wenn Sie ein Programm iterieren möchten, auf dem Stapel speichern müssen, was das Programm tun muss, wenn Sie von einem iterierten Funktionsaufruf zurückkehren (dies wird als Fortsetzung bezeichnet). Für einige Funktionen (wie z. B. rekursive Funktionen) ist die Fortsetzung trivial. Für andere ist die Fortsetzung möglicherweise sehr komplex, insbesondere wenn Sie sie selbst codieren müssen.

Dave Clarke

6

F : "Gibt es wirklich einen formaleren (überzeugenderen?) Beweis dafür, dass Rekursion in Iteration umgewandelt werden kann?"

A : Die Vollständigkeit einer Turingmaschine :-)

Abgesehen von Witzen entspricht das RASP-Maschinenmodell ( Turing Equivalent Random Access Stored Program) in etwa der Funktionsweise realer Mikroprozessoren, und sein Befehlssatz enthält nur einen bedingten Sprung (keine Rekursion). Die Möglichkeit, den Code dinamisch selbst zu ändern, erleichtert die Implementierung von Unterprogrammen und rekursiven Aufrufen.

Ich denke, dass Sie viele Artikel / Artikel über die " rekursive zu iterative Konvertierung " finden können (siehe Daves Antwort oder nur Google die Schlüsselwörter), aber vielleicht ist ein weniger bekannter (und praktischer ) Ansatz die neueste Forschung zur Hardware-Implementierung rekursiver Algorithmen ( Verwenden der VHDL-Sprache , die direkt in eine Hardware "kompiliert" wird). Siehe zum Beispiel V.Sklyarovs Artikel " FPGA-basierte Implementierung rekursiver Algorithmen " ( Der Artikel schlägt eine neuartige Methode zur Implementierung rekursiver Algorithmen in Hardware vor. ... Zwei praktische Anwendungen rekursiver Algorithmen im Bereich der Datensortierung und -komprimierung wurden untersucht im Detail .... ).

Marzio De Biasi
quelle

1

Wenn Sie mit Sprachen vertraut sind, die Lambdas unterstützen, besteht eine Möglichkeit darin, die CPS-Transformation zu untersuchen. Das Entfernen der Verwendung des Aufrufstapels (und insbesondere der Rekursion) ist genau das, was die CPS-Transformation bewirkt. Es wandelt ein Programm mit Prozeduraufrufen in ein Programm mit nur Endaufrufen um (Sie können sich diese als gotos vorstellen, was ein iteratives Konstrukt ist).

Die CPS-Umwandlung hängt eng mit der expliziten Aufbewahrung eines Aufrufstapels in einem herkömmlichen Array-basierten Stapel zusammen. Statt eines Arrays wird der Aufrufstapel jedoch mit verknüpften Abschlüssen dargestellt.

Jules
quelle

0

Meiner Meinung nach geht diese Frage auf die Ursprünge der Definitionen von Berechnungen zurück und wurde vor langer Zeit rigoros bewiesen, als gezeigt wurde, dass der kirchliche Lambda-Kalkül (der das Konzept der Rekursion in hohem Maße erfasst) Turing-Maschinen entspricht und enthalten ist in der noch verwendeten Terminologie "rekursive Sprachen / Funktionen". anscheinend ist eine spätere Schlüsselreferenz in dieser Richtung wie folgt

Wie in Peter Landins Aufsatz A Correspondence zwischen ALGOL 60 und Churchs Lambda-Notation von 1965 hervorgehoben, können sequentielle prozedurale Programmiersprachen im Sinne des Lambda-Kalküls verstanden werden, der die grundlegenden Mechanismen für die prozedurale Abstraktion und die Anwendung von Prozeduren (Unterprogrammen) bereitstellt.

ein großer Teil der BKD hierzu finden Sie in dieser Wikipedia - Seite Kirche-Turing - These . Ich bin mir der genauen Einzelheiten nicht sicher, aber der Wikipedia-Artikel scheint darauf hinzudeuten, dass es Rosser (1939) war, der diese Äquivalenz zwischen Lambda-Kalkül und Turingmaschinen zum ersten Mal bewiesen hat. Vielleicht / Vermutlich hat sein Papier einen stapelartigen Mechanismus zum Konvertieren der (möglicherweise rekursiven) Lambda-Aufrufe in die TM-Konstruktion?

Rosser, JB (1939). "Eine informelle Darstellung von Beweisen des Satzes von Godel und des Satzes der Kirche". Das Journal of Symbolic Logic (Das Journal of Symbolic Logic, Band 4, Nr. 2) 4 (2): 53–60. doi: 10.2307 / 2269059. JSTOR 2269059.

Anmerkung natürlich für jedermann in den Prinzipien der modernen interessiert Lisp Sprache und die Variante Scheme haben absichtlich eine starke Ähnlichkeit mit dem Lambda - Kalkül. Das Studium des Interpreter-Codes für die Bewertung von Ausdrücken führt zu Ideen, die ursprünglich in Abhandlungen zur Vollständigkeit der Lambda-Berechnung enthalten waren.

vzn
quelle

1

Der Turing / Lambda-Äquivalenznachweis befindet sich im Anhang dieses Dokuments: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Radu GRIGore

Rekursion entfernen - ein Blick in die Theorie hinter den Kulissen

Antworten: