Ist eine while-Schleife eigentlich eine Rekursion?

Ich habe mich gefragt, ob eine while-Schleife eigentlich eine Rekursion ist.

Ich denke, es liegt daran, dass eine while-Schleife als eine Funktion angesehen werden kann, die sich am Ende selbst aufruft. Wenn es keine Rekursion ist, was ist dann der Unterschied?

Schleifen sind sehr viel keine Rekursion. Tatsächlich sind sie das Paradebeispiel für den entgegengesetzten Mechanismus: die Iteration .

Der Punkt der Rekursion ist, dass ein Verarbeitungselement eine andere Instanz von sich selbst aufruft . Die Loop-Control-Maschinerie springt lediglich zu dem Punkt zurück, an dem sie begonnen hat.

Das Herumspringen im Code und das Aufrufen eines anderen Codeblocks sind verschiedene Vorgänge. Wenn Sie beispielsweise zum Anfang der Schleife springen, hat die Regelungsvariable der Schleife immer noch denselben Wert wie vor dem Sprung. Wenn Sie jedoch eine andere Instanz der Routine aufrufen, in der Sie sich gerade befinden, enthält die neue Instanz neue, nicht verwandte Kopien aller Variablen. Tatsächlich kann eine Variable einen Wert auf der ersten Verarbeitungsebene und einen anderen Wert auf einer niedrigeren Ebene haben.

Diese Funktion ist für viele rekursive Algorithmen von entscheidender Bedeutung. Aus diesem Grund können Sie die Rekursion nicht über Iteration emulieren, ohne auch einen Stapel aufgerufener Frames zu verwalten, der alle diese Werte verfolgt.

Zu sagen , dass X ist intrinsisch Y nur dann sinnvoll , wenn Sie einige (formal) System im Auge habe , dass Sie X ausdrückt in Wenn Sie die Semantik definieren. whileIn Bezug auf die Lambda - Kalkül, könnte man Rekursion erwähnen *; Wenn Sie es als Registermaschine definieren, werden Sie es wahrscheinlich nicht tun.

In beiden Fällen werden Sie wahrscheinlich nicht verstanden, wenn Sie eine Funktion rekursiv aufrufen, nur weil sie eine while-Schleife enthält.

* Obwohl vielleicht nur indirekt, zum Beispiel, wenn Sie es in Bezug auf definieren fold.

Dies hängt von Ihrer Sichtweise ab.

Wenn Sie sich die Berechnungstheorie ansehen , sind Iteration und Rekursion gleichermaßen aussagekräftig . Das bedeutet, dass Sie eine Funktion schreiben können, die etwas berechnet, und es spielt keine Rolle, ob Sie es rekursiv oder iterativ tun, Sie können beide Ansätze wählen. Sie können nichts rekursiv berechnen, was Sie nicht iterativ berechnen können, und umgekehrt (obwohl die internen Abläufe des Programms möglicherweise unterschiedlich sind).

Viele Programmiersprachen behandeln Rekursion und Iteration aus gutem Grund nicht gleich. In der Regel bedeutet Rekursion, dass die Sprache / der Compiler den Aufrufstapel verarbeitet, und Iteration bedeutet, dass Sie möglicherweise die Stapelverarbeitung selbst durchführen müssen.

Es gibt jedoch Sprachen - insbesondere funktionale Sprachen -, in denen Dinge wie Schleifen (für, während) tatsächlich nur syntaktischer Zucker für die Rekursion sind und auf diese Weise hinter den Kulissen implementiert werden. Dies ist in funktionalen Sprachen oft wünschenswert, da sie normalerweise nicht das Konzept haben, eine Schleife zu bilden, und wenn sie dies hinzufügen, wird ihr Kalkül aus wenig praktischen Gründen komplexer.

Also nein, sie sind nicht an sich gleich . Sie sind gleichermaßen aussagekräftig , dh Sie können etwas nicht iterativ berechnen, Sie können es nicht rekursiv berechnen und umgekehrt, aber das ist es im Allgemeinen (gemäß der Church-Turing-These).

Beachten Sie, dass es sich hier um rekursive Programme handelt . Es gibt andere Formen der Rekursion, z. B. in Datenstrukturen (z. B. Bäume).

Wenn Sie es aus Sicht der Implementierung betrachten , sind Rekursion und Iteration ziemlich unterschiedlich. Bei der Rekursion wird für jeden Aufruf ein neuer Stapelrahmen erstellt. Jeder Schritt der Rekursion ist in sich abgeschlossen und bezieht die Argumente für die Berechnung vom Angerufenen (selbst).

Loops hingegen erzeugen keine Callframes. Für sie bleibt der Kontext nicht bei jedem Schritt erhalten. Für die Schleife springt das Programm lediglich zum Anfang der Schleife zurück, bis die Schleifenbedingung fehlschlägt.

Dies ist sehr wichtig zu wissen, da es in der realen Welt ziemlich radikale Unterschiede machen kann. Zur Rekursion muss bei jedem Aufruf der gesamte Kontext gespeichert werden. Bei der Iteration können Sie genau steuern, welche Variablen sich im Speicher befinden und was wo gespeichert wird.

Wenn Sie es so betrachten, werden Sie schnell feststellen, dass sich Iteration und Rekursion für die meisten Sprachen grundlegend unterscheiden und unterschiedliche Eigenschaften haben. Je nach Situation sind einige Eigenschaften wünschenswerter als andere.

Rekursion können Programme einfacher und leichter zu testen und machen Beweis . Das Konvertieren einer Rekursion in eine Iteration macht den Code in der Regel komplexer und erhöht die Wahrscheinlichkeit eines Fehlers. Auf der anderen Seite kann das Konvertieren in Iteration und Reduzieren der Anzahl der Call-Stack-Frames den dringend benötigten Speicherplatz einsparen.

Der Unterschied ist der implizite Stapel und die Semantik.

Eine while-Schleife, die sich "am Ende selbst aufruft", hat keinen Stapel, der nach Abschluss des Vorgangs erneut gecrawlt werden kann. Es ist die letzte Iteration, die festlegt, in welchem ​​Zustand sie endet.

Die Rekursion kann jedoch nicht ohne diesen impliziten Stapel ausgeführt werden, der den Stand der zuvor ausgeführten Arbeiten speichert.

Es ist richtig, dass Sie jedes Rekursionsproblem mit Iteration lösen können, wenn Sie ihm explizit Zugriff auf einen Stapel gewähren. Aber das ist nicht dasselbe.

Der semantische Unterschied hat damit zu tun, dass das Betrachten von rekursivem Code eine Idee auf eine völlig andere Art und Weise vermittelt als iterativer Code. Iterativer Code erledigt die Dinge Schritt für Schritt. Es akzeptiert jeden Zustand, von dem es vorher gekommen ist, und schafft nur den nächsten Zustand.

Rekursiver Code zerlegt ein Problem in Fraktale. Dieser kleine Teil sieht aus wie dieser große Teil, so dass wir genau diesen und den gleichen Teil davon machen können. Es ist eine andere Art, über Probleme nachzudenken. Es ist sehr mächtig und gewöhnungsbedürftig. In wenigen Zeilen lässt sich viel sagen. Das kann man nicht aus einer while-Schleife herausholen, selbst wenn sie Zugriff auf einen Stapel hat.

Es alle Scharniere auf der Verwendung des Begriffs in sich . Auf der Programmiersprachenebene unterscheiden sie sich syntaktisch und semantisch, und sie haben eine ganz andere Leistung und Speichernutzung. Aber wenn Sie tief genug in die Theorie eintauchen, können sie in Bezug aufeinander definiert werden und sind daher in gewissem theoretischen Sinne "gleich".

Die eigentliche Frage lautet: Wann ist es sinnvoll, zwischen Iteration (Schleifen) und Rekursion zu unterscheiden, und wann ist es sinnvoll, sie als dieselben Dinge zu betrachten? Die Antwort ist, dass es beim Programmieren (im Gegensatz zum Schreiben mathematischer Beweise) wichtig ist, zwischen Iteration und Rekursion zu unterscheiden.

Durch die Rekursion wird ein neuer Stapelrahmen erstellt, dh ein neuer Satz lokaler Variablen für jeden Aufruf. Dies hat Overhead und beansprucht Platz auf dem Stack, was bedeutet, dass eine ausreichend tiefe Rekursion den Stack überlaufen kann, wodurch das Programm abstürzt. Die Iteration ändert dagegen nur die vorhandenen Variablen, ist also im Allgemeinen schneller und belegt nur eine konstante Menge an Speicher. Das ist also eine sehr wichtige Unterscheidung für einen Entwickler!

In Sprachen mit Tail-Call-Rekursion (normalerweise funktionale Sprachen) kann der Compiler rekursive Aufrufe möglicherweise so optimieren, dass sie nur eine konstante Menge an Speicher belegen. In diesen Sprachen ist der wichtige Unterschied nicht die Iteration gegenüber der Rekursion, sondern die Nicht-Tail-Call-Rekursionsversion, die Tail-Call-Rekursion und die Iteration.

Fazit: Sie müssen den Unterschied erkennen können, sonst stürzt Ihr Programm ab.

whileSchleifen sind eine Form der Rekursion, siehe zB die akzeptierte Antwort auf diese Frage . Sie entsprechen dem μ-Operator in der Berechenbarkeitstheorie (siehe zB hier ).

Alle Variationen von forSchleifen, die auf einer Reihe von Zahlen, einer endlichen Sammlung, einem Array usw. iterieren, entsprechen einer primitiven Rekursion, siehe z . B. hier und hier . Beachten Sie, dass die forSchleifen von C, C ++, Java usw. tatsächlich syntaktischer Zucker für eine whileSchleife sind und daher nicht der primitiven Rekursion entsprechen. Die Pascal- forSchleife ist ein Beispiel für eine primitive Rekursion.

Ein wichtiger Unterschied besteht darin, dass die primitive Rekursion immer beendet wird, wohingegen die generalisierte Rekursion ( whileSchleifen) möglicherweise nicht beendet wird.

BEARBEITEN

Einige Erläuterungen zu Kommentaren und anderen Antworten. "Rekursion tritt auf, wenn ein Objekt in Bezug auf sich selbst oder seinen Typ definiert ist." (siehe Wikipedia ). So,

Ist eine while-Schleife eigentlich eine Rekursion?

Da kann man eine whileSchleife in sich definieren

while p do c := if p then (c; while p do c))

dann ist ja eine whileSchleife eine Form der Rekursion. Rekursive Funktionen sind eine andere Form der Rekursion (ein weiteres Beispiel für die rekursive Definition). Listen und Bäume sind andere Formen der Rekursion.

Eine andere Frage, die von vielen Antworten und Kommentaren implizit angenommen wird, ist

Sind while-Schleifen und rekursive Funktionen gleichwertig?

Die Antwort auf diese Frage lautet nein : Eine whileSchleife entspricht einer rekursiven Endfunktion, wobei Variablen, auf die die Schleife zugreift, den Argumenten der impliziten rekursiven Funktion entsprechen, aber, wie andere bereits ausgeführt haben, nicht rekursive Funktionen kann nicht durch eine whileSchleife ohne Verwendung eines zusätzlichen Stapels modelliert werden .

Die Tatsache, dass "eine whileSchleife eine Form der Rekursion ist", widerspricht nicht der Tatsache, dass "einige rekursive Funktionen nicht durch eine whileSchleife ausgedrückt werden können ".

Ein Tail Call (oder Tail Recursive Call) wird genau als "goto with arguments" implementiert (ohne einen zusätzlichen Call Frame auf den Call Stack zu schieben ) und ist in einigen funktionalen Sprachen (insbesondere Ocaml) die übliche Art der Schleife.

Eine while-Schleife (in Sprachen, in denen sie vorkommt) endet also mit einem Tail-Aufruf an ihren Körper (oder ihrem Head-Test).

Ebenso können normale rekursive Aufrufe (ohne Tail-Call) durch Schleifen (unter Verwendung eines Stacks) simuliert werden.

Lesen Sie auch über Fortsetzungen und Fortsetzungsstil .

"Rekursion" und "Iteration" sind also zutiefst gleichwertig.

Es ist richtig, dass sowohl die Rekursion als auch die unbegrenzten while-Schleifen in Bezug auf die Rechenleistung gleichwertig sind. Das heißt, jedes rekursiv geschriebene Programm kann stattdessen unter Verwendung von Schleifen in ein äquivalentes Programm umgeschrieben werden und umgekehrt. Beide Ansätze sind vollständig , dh es kann jede berechenbare Funktion berechnet werden.

Der grundlegende Unterschied bei der Programmierung besteht darin, dass Sie bei der Rekursion auf Daten zurückgreifen können, die auf dem Aufrufstapel gespeichert sind. Nehmen Sie zur Veranschaulichung an, Sie möchten Elemente einer einfach verknüpften Liste entweder mit einer Schleife oder einer Rekursion drucken. Ich werde C für den Beispielcode verwenden:

 typedef struct List List;
 struct List
 {
     List* next;
     int element;
 };

 void print_list_loop(List* l)
 {
     List* it = l;
     while(it != NULL)
     {
          printf("Element: %d\n", it->element);
          it = it->next;
     }
 }

 void print_list_rec(List* l)
 {
      if(l == NULL) return;
      printf("Element: %d\n", l->element);
      print_list_rec(l->next);
 }

Einfach, richtig? Nehmen wir nun eine kleine Änderung vor: Drucken Sie die Liste in umgekehrter Reihenfolge aus.

Für die rekursive Variante ist dies eine fast triviale Modifikation der ursprünglichen Funktion:

void print_list_reverse_rec(List* l)
{
    if (l == NULL) return;
    print_list_reverse_rec(l->next);
    printf("Element: %d\n", l->element);
}

Für die Schleifenfunktion haben wir jedoch ein Problem. Unsere Liste ist einfach verlinkt und kann daher nur vorwärts durchlaufen werden. Da wir jedoch in umgekehrter Reihenfolge drucken, müssen wir das letzte Element drucken. Sobald wir das letzte Element erreicht haben, können wir nicht mehr zum vorletzten Element zurückkehren.

Entweder müssen wir eine ganze Menge neu durchlaufen oder wir müssen eine Hilfsdatenstruktur aufbauen, die die besuchten Elemente verfolgt und aus der wir dann effizient drucken können.

Warum haben wir dieses Problem mit der Rekursion nicht? Denn in der Rekursion haben wir bereits eine Hilfsdatenstruktur: den Funktionsaufruf-Stack.

Da die Rekursion es uns ermöglicht, zum vorherigen Aufruf des rekursiven Aufrufs zurückzukehren, wobei alle lokalen Variablen und der Status für diesen Aufruf noch intakt sind, gewinnen wir eine gewisse Flexibilität, die im iterativen Fall mühsam zu modellieren wäre.

Schleifen sind eine spezielle Form der Rekursion, um eine bestimmte Aufgabe zu erfüllen (meistens Iteration). Man kann eine Schleife in einem rekursiven Stil mit der gleichen Leistung [1] in mehreren Sprachen implementieren. und in der SICP [2] sehen Sie, dass Schleifen als "syntastischer Zucker" bezeichnet werden. In den meisten imperativen Programmiersprachen verwenden for- und while-Blöcke denselben Gültigkeitsbereich wie ihre übergeordnete Funktion. In den meisten funktionalen Programmiersprachen gibt es jedoch weder for- noch while-Schleifen, da sie nicht benötigt werden.

Der Grund, warum imperative Sprachen for / while-Schleifen haben, ist, dass sie Zustände handhaben, indem sie sie mutieren. Aber wenn Sie aus einer anderen Perspektive schauen, wenn Sie sich einen while-Block als eine Funktion selbst vorstellen, Parameter nehmen, verarbeiten und einen neuen Zustand zurückgeben, der auch der Aufruf derselben Funktion mit verschiedenen Parametern sein kann Schleife kann man sich als Rekursion vorstellen.

Die Welt könnte auch als veränderlich oder unveränderlich definiert werden. Wenn wir die Welt als Regelsatz definieren und eine ultimative Funktion aufrufen, die alle Regeln und den aktuellen Status als Parameter verwendet, und den neuen Status gemäß diesen Parametern mit derselben Funktionalität zurückgeben (nächsten Status im selben generieren) Weise), können wir auch sagen, dass dies eine Rekursion und eine Schleife ist.

Im folgenden Beispiel übernimmt die Funktion life die beiden Parameter "rules" und "state", und der neue Zustand wird beim nächsten Mal erstellt.

life rules state = life rules new_state
    where new_state = construct_state_in_time rules state

[1]: Tail Call Optimization ist eine in funktionalen Programmiersprachen übliche Optimierung, um den vorhandenen Funktionsstapel in rekursiven Aufrufen zu verwenden, anstatt einen neuen zu erstellen.

[2]: Struktur und Interpretation von Computerprogrammen, MIT. https://mitpress.mit.edu/books/structure-and-interpretation-computer-programs

Eine while-Schleife unterscheidet sich von einer Rekursion.

Wenn eine Funktion aufgerufen wird, geschieht Folgendes:

1. Ein Stapelrahmen wird dem Stapel hinzugefügt.

2. Der Codezeiger springt an den Anfang der Funktion.

Wenn eine while-Schleife beendet ist, geschieht Folgendes:

1. Eine Bedingung fragt, ob etwas wahr ist.

2. In diesem Fall springt der Code zu einem Punkt.

Im Allgemeinen ähnelt die while-Schleife dem folgenden Pseudocode:

 if (x)

 {

      Jump_to(y);

 }

Am wichtigsten ist jedoch, dass Rekursion und Schleifen unterschiedliche Assemblycode- und Maschinencode-Darstellungen haben. Das bedeutet, dass sie nicht gleich sind. Sie haben zwar die gleichen Ergebnisse, aber der unterschiedliche Maschinencode beweist, dass sie nicht zu 100% dasselbe sind.

Nur die Iteration ist nicht ausreichend, um im Allgemeinen der Rekursion zu entsprechen, aber die Iteration mit einem Stapel ist im Allgemeinen äquivalent. Jede rekursive Funktion kann als iterative Schleife mit einem Stapel umprogrammiert werden und umgekehrt. Dies bedeutet jedoch nicht, dass es praktisch ist und in einer bestimmten Situation die eine oder andere Form deutliche Vorteile gegenüber der anderen Version haben kann.

Ich bin mir nicht sicher, warum das umstritten ist. Rekursion und Iteration mit einem Stapel sind der gleiche Berechnungsprozess. Sie sind sozusagen das gleiche "Phänomen".

Das einzige, was ich mir vorstellen kann, ist, dass ich zustimme, wenn ich diese als "Programmierwerkzeuge" betrachte, dass Sie sie nicht als dasselbe ansehen sollten. Sie sind "mathematisch" oder "rechnerisch" äquivalent (wieder Iteration mit einem Stapel , nicht Iteration im Allgemeinen), aber das heißt nicht, dass Sie Probleme mit dem Gedanken angehen sollten, den einer von beiden tun wird. Aus Sicht der Implementierung / Problemlösung können einige Probleme auf die eine oder andere Weise besser funktionieren, und Ihre Aufgabe als Programmierer besteht darin, richtig zu entscheiden, welches besser geeignet ist.

Zur Verdeutlichung ist die Antwort auf die Frage Ist eine while-Schleife an sich eine Rekursion? ist ein definitives Nein oder zumindest "nicht, es sei denn, Sie haben auch Stack".