Ist eine while-Schleife eigentlich eine Rekursion?

37

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?

auf wiedersehen
quelle
13
Sie können die Rekursion in eine Iteration umwandeln und umgekehrt, ja. Das bedeutet nicht, dass sie gleich sind, sie haben nur die gleichen Fähigkeiten. Es gibt Zeiten, in denen die Rekursion natürlicher ist, und Zeiten, in denen die Iteration natürlicher ist.
Polygnome
18
@MooingDuck Sie können durch Induktion beweisen, dass jede Rekursion als Iteration geschrieben werden kann und umgekehrt. Ja, es wird ganz anders aussehen, aber Sie können es trotzdem tun.
Polygnome
6
Was heißt hier eigentlich dasselbe ? Beim Programmieren bedeutet die Verwendung von Rekursion eine bestimmte Sache, die sich von der Iteration (Schleifen) unterscheidet. Wenn Sie sich in CS der theoretischen Seite der Mathematik nähern, beginnen diese Dinge etwas andere Bedeutungen zu haben.
Hyde
3
@MooingDuck Die Konvertierung von rekursiv zu iterativ ist eigentlich ziemlich trivial. Sie behalten nur einen Stapel von Funktionsaufrufparametern und einen Stapel von Ergebnissen für die Funktionsaufrufe. Sie ersetzen die rekursiven Aufrufe, indem Sie die Parameter zum Aufrufstapel hinzufügen. Sicher, es gibt all die Handhabung des Stacks, die die Struktur des Algorithmus ein wenig sprengt, aber wenn Sie einmal verstanden haben, ist es ziemlich einfach zu sehen, dass der Code dasselbe tut. Grundsätzlich schreiben Sie explizit den Aufrufstapel, der in den rekursiven Definitionen implizit enthalten ist.
Bakuriu

Antworten:

116

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.

Kilian Foth
quelle
10
@Giorgio Das mag stimmen, aber es ist ein Kommentar zu einer Behauptung, die die Antwort nicht gemacht hat. "Willkürlich" ist in dieser Antwort nicht enthalten und würde die Bedeutung erheblich verändern.
HDV
12
@hvd Im Prinzip ist die Schwanzrekursion eine vollständige Rekursion wie jede andere. Intelligente Compiler können den eigentlichen Teil "Erstellen eines neuen Stapelrahmens" so optimieren, dass der generierte Code einer Schleife sehr ähnlich ist, aber die Konzepte, über die wir sprechen, gelten für die Quellcodeebene. Ich halte die Form, die ein Algorithmus als Quellcode hat, für wichtig, daher würde ich sie immer noch als Rekursion bezeichnen
Kilian Foth
15
@Giorgio "Genau das macht die Rekursion: Ruft sich selbst mit neuen Argumenten auf" - mit Ausnahme des Aufrufs. Und die Argumente.
Hobbs
12
@Giorgio Sie verwenden hier andere Definitionen von Wörtern als die meisten anderen. Wie Sie wissen, sind Wörter die Basis der Kommunikation. Dies sind Programmierer, nicht CS Stack Exchange. Wenn wir Wörter wie "argument", "call", "function" usw. so verwenden würden, wie Sie es vorschlagen, wäre es unmöglich, über den tatsächlichen Code zu diskutieren.
Hyde
6
@ Giorgio Ich betrachte das abstrakte Konzept. Es gibt das Konzept, bei dem Sie wiederkehren, und das Konzept, bei dem Sie eine Schleife ausführen. Das sind unterschiedliche Konzepte. Hobbs ist zu 100% richtig, dass es keine Argumente und keinen Aufruf gibt. Sie sind grundlegend und abstrakt verschieden. Und das ist gut so, weil sie verschiedene Probleme lösen. Andererseits überlegen Sie, wie Sie Schleifen implementieren könnten, wenn Ihr einziges Werkzeug die Rekursion ist. Ironischerweise fordern Sie Hobbs auf, nicht mehr an die Implementierung zu denken und Konzepte zu prüfen, wenn Ihre Methodik diejenige ist, die wirklich neu bewertet werden muss.
CorsiKa
37

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.

Anton Golov
quelle
4
Fairerweise ist die Funktion in keiner Definition rekursiv. Es enthält nur ein rekursives Element, die Schleife.
Luaan
@Luaan: Auf jeden Fall, aber da in Sprachen mit einem whileKonstrukt Rekursivität im Allgemeinen eine Eigenschaft von Funktionen ist, kann ich mir nichts anderes vorstellen, das in diesem Zusammenhang als "rekursiv" beschrieben werden könnte.
Anton Golov
36

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.

Polygnom
quelle
Eine Sprache mit lokalen Variablen und Rekursion, jedoch ohne Arrays, konnte Aufgaben ausführen, die nicht von einer iterativen Sprache mit lokalen Variablen und ohne Arrays ausgeführt werden konnten. Geben Sie beispielsweise an, ob eine Eingabe eine alphanumerische Zeichenfolge unbekannter Länge gefolgt von einem Leerzeichen und den Zeichen der ursprünglichen Zeichenfolge in umgekehrter Reihenfolge enthält.
Supercat
3
Solange die Sprache vollständig ist, kann es. Ein Array kann zum Beispiel leicht durch eine (doppelt) verknüpfte Liste ersetzt werden. Über Iteration oder Rekursion zu sprechen und ob sie gleich sind, macht nur Sinn, wenn man zwei Sprachen vergleicht, die vollständig sind.
Polygnome
Ich meinte, nichts anderes als einfache statische oder automatische Variablen zu haben, dh nicht vollständig zu sein. Eine rein iterative Sprache würde sich auf die Aufgaben beschränken, die über einen einfachen deterministischen endlichen Automaten ausgeführt werden können, während eine rekursive Sprache die Fähigkeit hinzufügen würde, Aufgaben auszuführen, die mindestens einen pushdown-deterministischen endlichen Automaten erfordern würden.
Supercat
1
Wenn die Sprache nicht vollständig ist, ist es zunächst sinnlos. DFAs können übrigens weder willkürlich iterieren noch rekursiv arbeiten.
Polygnome
2
Tatsächlich ist keine Implementierung vollständig und Sprachen, die nicht vollständig sind, können für viele Zwecke nützlich sein. Jedes Programm, das mit einer endlichen Anzahl von Variablen mit einem endlichen Bereich ausgeführt werden kann, kann von einem DFA aufgenommen werden, bei dem jede mögliche Kombination von Werten ein diskreter Zustand ist.
Supercat
12

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.

kandierte_orange
quelle
5
Ich denke, "impliziter Stapel" ist irreführend. Rekursion ist Teil der Semantik einer Sprache, kein Implementierungsdetail. (Zugegeben, die meisten rekursionsunterstützenden Sprachen verwenden einen Aufrufstapel, aber erstens tun es einige solcher Sprachen nicht, und zweitens hängt nicht jeder rekursive Aufruf notwendigerweise an den Aufrufstapel an, da viele Sprachen Optimierungen wie z Als Tail Call Elimination .) Das Verstehen der üblichen / einfachen Implementierung kann hilfreich sein, um die Abstraktion in den Griff zu bekommen, aber Sie sollten sich nicht darüber täuschen, dass es die ganze Geschichte ist.
Ruakh
2
@ruakh Ich würde behaupten, dass eine Funktion, die im konstanten Raum ausgeführt wird, indem die Tail-Call-Elimination verwendet wird, wirklich eine Schleife ist. Hier ist der Stack nicht das Implementierungsdetail, sondern die Abstraktion, mit der Sie verschiedene Status für verschiedene Rekursionsebenen akkumulieren können.
Cimbali
@ruakh: Jeder Zustand innerhalb eines einzelnen rekursiven Aufrufs wird in einem impliziten Stapel gespeichert, es sei denn, die Rekursion kann vom Compiler in eine iterative Schleife konvertiert werden. Die Tail-Call-Elimination ist ein Implementierungsdetail, dessen Sie sich bewusst sein müssen, wenn Sie Ihre Funktion so reorganisieren möchten, dass sie tail-rekursiv ist. Auch "wenige solche Sprachen nicht" - können Sie ein Beispiel für Sprachen angeben, die keinen Stapel für rekursive Aufrufe benötigen?
Groo
@ruakh: CPS selbst erstellt den gleichen impliziten Stack, daher muss es sich auf die Beseitigung von Tail Calls verlassen, um einen Sinn zu ergeben (was aufgrund seiner Konstruktion trivial ist). Sogar der Wikipedia-Artikel, mit dem Sie verlinkt haben, sagt dasselbe: Wenn Sie CPS ohne Tail Call Optimization (TCO) verwenden, wächst möglicherweise nicht nur die konstruierte Fortsetzung während der Rekursion, sondern auch der Aufrufstapel .
Groo
7

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.

JacquesB
quelle
3

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 ".

Giorgio
quelle
2
@morbidCode: Primitive Rekursion und μ-Rekursion sind Formen der Rekursion mit spezifischen Einschränkungen (oder deren Fehlen), die z. B. in der Berechnungstheorie untersucht wurden. Wie sich herausstellt, kann eine Sprache mit nur einer FORSchleife genau alle primitiven rekursiven Funktionen berechnen, und eine Sprache mit nur einer WHILESchleife kann genau alle µ-rekursiven Funktionen berechnen (und es stellt sich heraus, dass die µ-rekursiven Funktionen genau die Funktionen sind, die es sind) eine Turing-Maschine kann berechnen). Oder, um es kurz zu machen: Primitive Rekursion und µ-Rekursion sind Fachbegriffe aus der Mathematik / Berechenbarkeitstheorie.
Jörg W Mittag
2
Ich dachte, "Rekursion" impliziere einen Funktionsaufruf, der dazu führt, dass der aktuelle Ausführungsstatus in den Stack verschoben wird und so weiter. Aus diesem Grund haben die meisten Maschinen eine praktische Grenze für die Anzahl der Ebenen, auf die Sie zurückgreifen können. Während Schleifen keine solchen Beschränkungen haben, weil sie intern so etwas wie ein "JMP" verwenden und den Stapel nicht verwenden würden. Nur mein Verständnis könnte falsch sein.
Jay
13
Diese Antwort verwendet eine völlig andere Definition für das Wort "rekursiv" als das OP, und ist daher sehr irreführend.
Mooing Duck
2
@DavidGrinberg: Zitat: "Die C, C ++, Java for-Schleifen sind kein Beispiel für primitive Rekursion. Primitive Rekursion bedeutet, dass die maximale Anzahl von Iterationen / Rekursionstiefe vor dem Starten der Schleife festgelegt wird." Giorgio spricht über Grundelemente der Computability-Theorie . Unabhängig von Programmiersprachen.
Mooing Duck
3
Ich muss Mooing Duck zustimmen. Während die Berechnungstheorie für theoretisches CS interessant sein könnte, sind sich meiner Meinung nach alle einig, dass das OP über das Konzept der Programmiersprachen gesprochen hat.
Voo
2

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.

Basile Starynkevitch
quelle
1

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.

ComicSansMS
quelle
1
Natürlich ist die zweite rekursive Funktion nicht rekursiv - es ist viel schwieriger, den Speicherplatz zu optimieren, da Sie die TCO nicht verwenden können, um den Stapel wiederzuverwenden. Das Implementieren einer doppelt verknüpften Liste würde beide Algorithmen auf Kosten des Platzes eines Zeigers / einer Referenz pro Element trivial machen.
Baldrickk
@Baldrickk Das Komische an der Schwanzrekursion ist, dass Sie am Ende eine Version haben, die der Loop-Version sehr viel ähnlicher ist, da Sie dadurch wieder nicht mehr in der Lage sind, den Status auf dem Aufrufstapel zu speichern. Eine doppelt verknüpfte Liste würde das Problem lösen, aber eine Neugestaltung der Datenstruktur ist häufig keine Option, wenn dieses Problem auftritt. Während das Beispiel hier künstlich eingeschränkt ist, zeigt es ein Muster, das häufig in funktionalen Sprachen im Kontext von rekursiven algebraischen Typen auftaucht.
ComicSansMS
Mein Punkt war, dass, wenn Sie auf dieses Problem stoßen, es eher an einem Mangel an funktionalem Design liegt, als an den Sprachkonstrukten, mit denen Sie es implementieren, und jede Wahl hat ihre eigenen Vor- und Nachteile :)
Baldrickk
0

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

Zeawee
quelle
4
@Giorgio Nicht meine Ablehnung, sondern nur eine Vermutung: Ich glaube, die meisten Programmierer glauben, dass Rekursion einen rekursiven Funktionsaufruf impliziert, denn genau das ist Rekursion, eine Funktion, die sich selbst aufruft. In einer Schleife gibt es keinen rekursiven Funktionsaufruf. Zu sagen, dass eine Schleife ohne rekursiven Funktionsaufruf eine spezielle Form der Rekursion ist, wäre offensichtlich falsch, wenn man von dieser Definition ausgeht.
Hyde
1
Nun, vielleicht sehen wir es aus einer abstrakteren Perspektive, was unterschiedliche Dinge zu sein scheinen, sind tatsächlich konzeptionell die gleichen. Ich finde es ziemlich entmutigend und traurig zu denken, dass die Leute Antworten ablehnen, nur weil sie nicht ihren Erwartungen entsprechen, anstatt sie als Chance zu nutzen, etwas zu lernen. Alle Antworten, die zu sagen versuchen: "Hey, sieh mal, diese Dinge sehen auf der Oberfläche anders aus, sind aber auf einer abstrakteren Ebene tatsächlich gleich", wurden herabgestuft.
Giorgio
3
@Georgio: Der Zweck dieser Site ist es, Antworten auf Fragen zu erhalten. Antworten, die hilfreich und richtig sind, verdienen Aufwertungen, Antworten, die verwirrend und nicht hilfreich sind, verdienen Abwertungen. Eine Antwort, die subtil eine andere Definition eines gemeinsamen Begriffs verwendet, ohne zu verdeutlichen, welche andere Definition verwendet wird, ist verwirrend und wenig hilfreich. Antworten, die nur Sinn machen, wenn Sie die Antwort sozusagen schon kennen, sind nicht hilfreich und dienen nur dazu, dem Autor ein besseres Verständnis der Terminologie zu vermitteln.
JacquesB
2
@JacquesB: "Antworten, die nur Sinn machen, wenn man die Antwort sozusagen schon kennt, sind nicht hilfreich ...": Das kann man auch von Antworten sagen, die nur bestätigen, was der Leser schon weiß oder zu wissen glaubt. Wenn eine Antwort eine Terminologie enthält, die nicht eindeutig ist, können Sie vor dem Abstimmen Kommentare verfassen, um weitere Details anzufordern.
Giorgio
4
Schleifen sind keine spezielle Form der Rekursion. Betrachten Sie die Berechenbarkeitstheorie und z. B. die theoretische WHILE-Sprache und den µ-Kalkül. Ja, einige Sprachen verwenden Schleifen als syntaktischen Zucker, um die Rekursion tatsächlich im Hintergrund zu verwenden, aber sie können dies, weil Rekursion und Iteration gleichermaßen aussagekräftig sind und nicht, weil sie gleich sind.
Polygnome
-1

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.

Die große Ente
quelle
2
Sie sprechen von der Implementierung eines Prozeduraufrufs und einer while-Schleife, und da sie unterschiedlich implementiert sind, kommen Sie zu dem Schluss, dass sie unterschiedlich sind. Konzeptionell sind die jedoch sehr ähnlich.
Giorgio
1
Je nach Compiler kann ein optimierter, inline Rekursionsaufruf dieselbe Assembly wie eine einfache Schleife erzeugen.
Hyde
@hyde ... das ist nur ein Beispiel für die bekannte Tatsache, dass eines durch das andere ausgedrückt werden kann; bedeutet nicht, dass sie identisch sind. Ein bisschen wie Masse und Energie. Natürlich kann man argumentieren, dass alle Möglichkeiten, identische Ergebnisse zu erzielen, "gleich" sind. Wenn die Welt endlich wäre, wären am Ende alle Programme constexpr.
Peter - Reinstate Monica
@ Giorgio Nah, es ist eine logische Beschreibung, keine Implementierung. Wir wissen, dass die beiden Dinge gleichwertig sind ; Äquivalenz ist aber keine Identität , denn die Frage (und die Antworten) ist genau, wie wir zum Ergebnis kommen, dh sie enthalten notwendigerweise algorithmische Beschreibungen (die als Stapel und Variable usw. ausgedrückt werden können).
Peter - Reinstate Monica
1
@ PeterA.Schneider Ja, aber in dieser Antwort steht "Am wichtigsten von allem ... anderer Assembler-Code", was nicht ganz richtig ist.
Hyde
-1

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".

Dave Cousineau
quelle