Iteration kann Rekursion ersetzen?

Ich habe da im ganzen Stack - Überlauf, zB hier , hier , hier , hier , hier und einige andere , die ich interessiere mich nicht zu erwähnen, dass „jedes Programm , das Verwendung Rekursion in ein Programm umgewandelt werden kann unter Verwendung von Iteration nur“.

Es gab sogar einen hochrangigen Thread mit einer hochrangigen Antwort , die sagte, dass es möglich ist.

Jetzt sage ich nicht, dass sie falsch liegen. Es ist nur so, dass diese Antwort meinem dürftigen Wissen und Verständnis über Computer widerspricht.

Ich glaube, dass jede iterative Funktion als Rekursion ausgedrückt werden kann, und Wikipedia hat eine entsprechende Aussage. Ich bezweifle jedoch, dass das Gegenteil der Fall ist. Zum einen bezweifle ich, dass nicht-primitive rekursive Funktionen iterativ ausgedrückt werden können.

Ich bezweifle auch, dass Hyperoperationen iterativ ausgedrückt werden können.

In seiner Antwort (die ich übrigens nicht verstehe) auf meine Frage sagte @YuvalFIlmus, dass es nicht möglich ist, eine Folge von mathematischen Operationen in eine Folge von Additionen umzuwandeln.

Wenn YFs Antwort in der Tat richtig ist (ich denke, es ist, aber seine Argumentation war über meinem Kopf), bedeutet dies dann nicht, dass nicht jede Rekursion in Iteration umgewandelt werden kann? Denn wenn es möglich wäre, jede Rekursion in eine Iteration umzuwandeln, wäre ich in der Lage, alle Operationen als Folge von Hinzufügungen auszudrücken.

Meine Frage lautet:

Kann jede Rekursion in eine Iteration umgewandelt werden und warum?

Bitte geben Sie eine Antwort, die ein kluger Highschooler oder ein Erstklässler verstehen wird. Danke.

PS Ich weiß nicht, was primitiv rekursiv ist (Ich weiß über die Ackermann-Funktion Bescheid und weiß, dass sie nicht primitiv rekursiv ist, aber dennoch berechenbar ist. Mein Wissen dazu stammt von der Wikipedia-Seite über die Ackermann-Funktion.)

PPS: Wenn die Antwort ja ist, könnten Sie zum Beispiel eine iterative Version einer nicht-primitiv-rekursiven Funktion schreiben. ZB Ackermann in der Antwort. Es wird mir helfen zu verstehen.

Es ist möglich, die Rekursion durch Iteration und unbegrenzten Speicher zu ersetzen .

Wenn Sie nur eine Iteration (etwa while-Schleifen) und eine begrenzte Menge an Speicher haben, ist alles, was Sie haben, ein endlicher Automat. Mit einer endlichen Menge an Speicher hat die Berechnung eine endliche Anzahl möglicher Schritte, so dass es möglich ist, sie alle mit einem endlichen Automaten zu simulieren.

Unbegrenztes Gedächtnis zu haben, verändert den Deal. Dieses unbegrenzte Gedächtnis kann viele Formen annehmen, die sich als äquivalente Ausdruckskraft herausstellen. Eine Turing-Maschine zum Beispiel macht es einfach: Es gibt ein einzelnes Band, und der Computer kann sich auf dem Band nur schrittweise vorwärts oder rückwärts bewegen - aber das reicht aus, um alles zu tun, was Sie mit rekursiven Funktionen tun können.

Eine Turing-Maschine kann als idealisiertes Modell eines Computers (Finite-State-Maschine) mit zusätzlichem Speicher angesehen werden, der bei Bedarf wächst. Beachten Sie, dass es nicht nur wichtig ist, dass das Band nicht begrenzt ist, sondern dass Sie auch bei der Eingabe nicht zuverlässig vorhersagen können, wie viel Band benötigt wird. Wenn Sie vorhersagen (dh berechnen) könnten, wie viel Band von der Eingabe benötigt wird, dann könnten Sie entscheiden, ob die Berechnung anhalten würde, indem Sie die maximale Bandgröße berechnen und dann das gesamte System, einschließlich des jetzt endlichen Bandes, als endliche Zustandsmaschine behandeln .

Eine andere Möglichkeit, eine Turing-Maschine mit Computern zu simulieren, ist die folgende. Simulieren Sie die Turing-Maschine mit einem Computerprogramm, das den Bandanfang im Speicher ablegt. Wenn die Berechnung das Ende des Teils des Bandes erreicht, der in den Speicher passt, ersetzen Sie den Computer durch einen größeren Computer und führen Sie die Berechnung erneut aus.

Angenommen, Sie möchten eine rekursive Berechnung mit einem Computer simulieren. Die Techniken zum Ausführen von rekursiven Funktionen sind gut bekannt: jeder Funktionsaufruf ein Stück Speicher, ein sogenannten Stapelrahmen . Entscheidend ist, dass rekursive Funktionen Informationen durch mehrere Aufrufe verbreiten können, indem sie Variablen weitergeben. In Bezug auf die Implementierung auf einem Computer bedeutet dies, dass ein Funktionsaufruf möglicherweise auf den Stack-Frame eines (grand-) ^* Elternaufrufs zugreift .

Ein Computer ist ein Prozessor - eine Finite-State-Maschine (mit einer großen Anzahl von Zuständen, aber wir machen hier eine Berechnungstheorie, es kommt also nur darauf an, dass sie endlich ist) - gekoppelt mit einem endlichen Speicher. Der Mikroprozessor führt eine Riesen-While-Schleife aus: "Lies bei eingeschalteter Stromversorgung einen Befehl aus dem Speicher und führe ihn aus". (Echte Prozessoren sind viel komplexer als das, aber es hat keinen Einfluss darauf, was sie berechnen können, nur darauf, wie schnell und bequem sie es tun.) Ein Computer kann mit genau dieser while-Schleife rekursive Funktionen ausführen, um Iteration und den Mechanismus dafür bereitzustellen Zugriff auf den Speicher, einschließlich der Möglichkeit, den Speicher nach Belieben zu vergrößern.

Wenn Sie die Rekursion auf die primitive Rekursion beschränken, können Sie die Iteration auf eine begrenzte Iteration beschränken . Das heißt, anstatt while-Schleifen mit unvorhersehbarer Laufzeit zu verwenden, können Sie for-Schleifen verwenden, bei denen die Anzahl der Iterationen am Anfang der Schleife bekannt ist¹. Die Anzahl der Iterationen ist zu Beginn des Programms möglicherweise nicht bekannt: Sie können selbst durch vorherige Schleifen berechnet worden sein.

Ich werde hier nicht einmal einen Beweis skizzieren, aber es gibt eine intuitive Beziehung zwischen dem Übergang von der primitiven zur vollständigen Rekursion und dem Übergang von for-Schleifen zu while-Schleifen: In beiden Fällen müssen Sie nicht im Voraus wissen, wann Sie sich befinden halt. Bei vollständiger Rekursion wird dies mit dem Minimierungsoperator durchgeführt, in dem Sie so lange weitermachen, bis Sie einen Parameter finden, der die Bedingung erfüllt. Bei while-Schleifen wird dies so lange durchgeführt, bis die Schleifenbedingung erfüllt ist.

_forwhile$n$

Jede Rekursion kann in eine Iteration konvertiert werden, wie Ihre CPU bezeugt, die beliebige Programme mit einer unendlichen Iteration zum Abrufen und Ausführen ausführt. Dies ist eine Form des Böhm-Jacopini-Theorems . Darüber hinaus haben viele Turing-vollständige Rechenmodelle keine Rekursion, zum Beispiel Turing-Maschinen und Zählmaschinen .

Primitive rekursive Funktionen entsprechen Programmen mit beschränkter Iteration, dh, Sie müssen vorab die Anzahl der Iterationen angeben, die eine Schleife ausgeführt wird. Eine gebundene Iteration kann im Allgemeinen keine Rekursion simulieren, da die Ackermann-Funktion nicht primitiv rekursiv ist. Eine unbegrenzte Iteration kann jedoch jede teilweise berechenbare Funktion simulieren.

$a(n,m)$

$s$

$\DeclareMathOperator{\push}{push}\push(s, x)$$x$$\DeclareMathOperator{\pop}{pop} x ← \pop(s)$$\DeclareMathOperator{\empty}{empty}\empty(s)$

$\texttt{Ackermann}(n_0, m_0):$ $\def\ifop#1{\texttt{if(}#1\texttt{):}}$ $\def\elseif#1{\texttt{else if(}#1\texttt{):}}$ $\def\elsop{\texttt{else:}}$

• $s = \emptyset$ (leeren Stack initialisieren)
• $\push(s,n_0)$
• $\push(s,m_0)$
• $\texttt{while(true):}$
  • $m ← \pop(s)$
  • $\ifop{\empty(s)}$
    • $\texttt{return }m$ (dies beendet die Schleife)
  • $n ← \pop(s)$
  • $\ifop{n = 0}$
    • $\push(s, m+1)$
  • $\elseif{m=0}$
    • $\push(s, n-1)$
    • $\push(s, 1)$
  • $\elsop$
    • $\push(s, n-1)$
    • $\push(s, n)$
    • $\push(s, m-1)$

Ich habe dies in Ceylon implementiert, Sie können es im WebIDE ausführen , wenn Sie möchten. (Es gibt den Stapel zu Beginn jeder Iteration der Schleife aus.)

Dies hat natürlich nur den impliziten Aufrufstapel von der Rekursion in einen expliziten Stapel mit den Parametern und Rückgabewerten verschoben.

Es gibt bereits einige großartige Antworten (mit denen ich nicht einmal konkurrieren kann), aber ich möchte diese einfache Erklärung abgeben.

Rekursion ist nur die Manipulation des Laufzeitstacks. Recursing fügt einen neuen Stack-Frame hinzu (für den erneuten Aufruf der rekursiven Funktion) und Return entfernt einen Stack-Frame (für die gerade abgeschlossene Neuerung der rekursiven Funktion). Durch die Rekursion wird eine bestimmte Anzahl von Stack-Frames hinzugefügt / entfernt, bis schließlich alle beendet werden (hoffentlich!) Und das Ergebnis an den Aufrufer zurückgegeben wird.

Was würde nun passieren, wenn Sie Ihren eigenen Stack erstellen, rekursive Funktionsaufrufe durch Pushing auf den Stack ersetzen, die Rückkehr von rekursiven Funktionen durch Poppen des Stacks ersetzen und eine while-Schleife ausführen, bis der Stack leer ist?

Soweit ich das beurteilen kann, können Sie nach meiner Erfahrung jede Rekursion als Iteration implementieren. Wie oben erwähnt, verwendet die Rekursion den Stapel, der konzeptionell unbegrenzt, aber praktisch begrenzt ist (haben Sie jemals eine Stapelüberlaufnachricht erhalten?). In meinen Anfängen als Programmierer (im dritten Viertel des letzten Jahrhunderts des letzten Jahrtausends) verwendete ich nicht-rekursive Sprachen, die rekursive Algorithmen implementierten, und hatte keine Probleme. Ich bin mir jedoch nicht sicher, wie man es beweisen würde.