Gibt es etwas, das mit Rekursion gemacht werden kann, das nicht mit Schleifen gemacht werden kann?

126

Es gibt Zeiten, in denen die Verwendung von Rekursion besser ist als die Verwendung einer Schleife, und Zeiten, in denen die Verwendung einer Schleife besser ist als die Verwendung von Rekursion. Wenn Sie das "richtige" auswählen, können Sie Ressourcen sparen und / oder weniger Codezeilen erhalten.

Gibt es Fälle, in denen eine Aufgabe nur durch Rekursion und nicht durch eine Schleife ausgeführt werden kann?

Pikamander2
quelle
13
Ich bezweifle es ernsthaft. Rekursion ist eine verherrlichte Schleife.
Leichtigkeitsrennen im Orbit
6
Wenn Sie die unterschiedlichen Richtungen sehen, in die die Antworten gehen (und mich selbst bei der Bereitstellung einer besseren versagt haben), tun Sie möglicherweise jedem, der versucht, einen Gefallen zu erwidern, wenn Sie ein bisschen mehr Hintergrundwissen liefern und nach welcher Art von Antwort Sie suchen. Möchten Sie einen theoretischen Beweis für hypothetische Maschinen (mit unbegrenzter Speicherung und Laufzeit)? Oder praktische Beispiele? (Wo "wäre lächerlich kompliziert" könnte sich als "nicht machbar" qualifizieren.) Oder etwas anderes?
5gon12eder
8
@LightnessRacesinOrbit Für mein nicht englischsprachiges Ohr klingt "Rekursion ist eine verherrlichte Schleife". Sie meinen "Sie könnten genauso gut ein Schleifenkonstrukt anstelle eines rekursiven Aufrufs überall verwenden, und das Konzept hat seinen eigenen Namen nicht wirklich verdient." . Vielleicht interpretiere ich das "verherrlichte Etwas" als falsch.
Hyde
13
Was ist mit Ackermann-Funktion? en.wikipedia.org/wiki/Ackermann_Funktion , nicht besonders nützlich, aber unmöglich per Loop zu machen. (Vielleicht möchten Sie auch dieses Video youtube.com/watch?v=i7sm9dzFtEI von Computerphile überprüfen )
WizardOfMenlo
8
@WizardOfMenlo Der befunge Code ist eine Implementierung der ERRE- Lösung (die auch eine interaktive Lösung ist ... mit einem Stack). Ein iterativer Ansatz mit einem Stapel kann einen rekursiven Aufruf emulieren. Bei jeder entsprechend leistungsfähigen Programmierung kann ein Schleifenkonstrukt verwendet werden, um ein anderes zu emulieren. Die Registermaschine mit den Anweisungen INC (r), JZDEC (r, z)kann eine Turing - Maschine implementieren. Es gibt keine 'Rekursion' - das ist ein Sprung, wenn nichts anderes als DECrement. Wenn die Ackermann-Funktion berechenbar ist (ist), kann diese Registriermaschine dies tun.

Antworten:

164

Ja und nein. Letztendlich kann keine Rekursion berechnet werden, die eine Schleife nicht kann, aber eine Schleife erfordert viel mehr Installationsaufwand. Daher ist die einzige Sache, die eine Rekursion tun kann, dass Schleifen manche Aufgaben nicht so einfach machen können.

Geh auf einen Baum. Mit Rekursion auf einen Baum zu gehen ist einfach dumm. Es ist das Natürlichste auf der Welt. Ein Baum mit Schleifen zu gehen ist viel weniger einfach. Sie müssen einen Stapel oder eine andere Datenstruktur verwalten, um zu verfolgen, was Sie getan haben.

Oft ist die rekursive Lösung eines Problems hübscher. Das ist ein technischer Begriff, und darauf kommt es an.

Scant Roger
quelle
120
Grundsätzlich bedeutet das Ausführen von Schleifen anstelle von Rekursionen, dass der Stapel manuell behandelt wird.
Silviu Burcea
15
... die Stapel . In der folgenden Situation ist es möglicherweise sehr wichtig, mehr als einen Stapel zu haben. Betrachten Sie eine rekursive Funktion A, die etwas in einem Baum findet. Jedes AMal, wenn es auf dieses Ding stößt, startet es eine andere rekursive Funktion, Bdie an der Stelle, an der es gestartet wurde, ein verwandtes Ding im Teilbaum findet A. Sobald Bdie Rekursion beendet ist, zu der sie zurückkehrt A, setzt diese ihre eigene Rekursion fort. Man kann einen Stack für Aund einen für deklarieren Boder den BStack in die ASchleife legen . Wenn man darauf besteht, einen einzigen Stapel zu verwenden, werden die Dinge wirklich kompliziert.
rwong
35
Therefore, the one thing recursion can do that loops can't is make some tasks super easy. Und das einzige, was Schleifen tun können, ist, dass einige Aufgaben sehr einfach sind. Haben Sie die hässlichen, nicht intuitiven Dinge gesehen, die Sie tun müssen, um die meisten natürlich iterativen Probleme von naiver Rekursion zu Schwanzrekursion umzuwandeln, damit sie den Stapel nicht sprengen?
Mason Wheeler
10
@MasonWheeler 99% der Zeit , diese „Dinge“ besser in einem Rekursion-Operator eingekapselt werden , wie mapoder fold(in der Tat , wenn Sie sich dazu entscheiden , sie Primitiven zu betrachten, ich glaube , Sie verwenden können fold/ unfoldals dritte Alternative zu Schleifen oder Rekursionen verwenden). Wenn Sie keinen Bibliothekscode schreiben, gibt es nicht so viele Fälle, in denen Sie sich über die Implementierung der Iteration Gedanken machen sollten, anstatt über die Aufgabe, die sie ausführen soll. In der Praxis bedeutet dies, dass explizite Schleifen und explizite Rekursionen gleichermaßen schlecht sind Abstraktionen, die auf oberster Ebene vermieden werden sollten.
Leushenko
7
Sie können zwei Zeichenfolgen durch rekursives Vergleichen von Teilzeichenfolgen vergleichen. Wenn Sie jedoch jedes Zeichen einzeln vergleichen, können Sie eine bessere Leistung erzielen und dem Leser klarer werden.
Steven Burnap
78

Nein.

Erst bis hinunter zu den sehr Grundlagen des notwendigen Minimums , um eine Schleife zu berechnen, müssen Sie nur in der Lage sein (dies allein nicht ausreicht, sondern ist eine notwendige Komponente). Es ist egal wie .

Jede Programmiersprache, die eine Turing-Maschine implementieren kann, heißt Turing complete . Und es gibt viele Sprachen, die komplett sind.

Meine Lieblingssprache auf dem Weg dorthin von "das funktioniert tatsächlich?" Turing Vollständigkeit ist die von FRACTRAN , die Turing vollständig ist . Es hat eine Schleifenstruktur und Sie können eine Turing-Maschine darin implementieren. Somit kann alles, was berechenbar ist, in einer Sprache implementiert werden, die keine Rekursion aufweist. Daher gibt es nichts , was Ihnen eine Rekursion in Bezug auf die Berechenbarkeit bieten kann, was eine einfache Schleife nicht kann.

Das läuft wirklich auf ein paar Punkte hinaus:

  • Alles, was berechenbar ist, ist auf einer Turing-Maschine berechenbar
  • Jede Sprache, die eine Turing-Maschine (Turing complete genannt) implementieren kann, kann alles berechnen, was jede andere Sprache kann
  • Da es Turing-Maschinen in Sprachen gibt, die nicht rekursiv sind (und es gibt andere, die nur rekursiv sind, wenn Sie in einige der anderen Esolangs eintauchen), ist es zwangsläufig richtig, dass Sie mit einer Rekursion nichts anfangen können, was Sie mit einer nicht tun können Schleife (und nichts, was Sie mit einer Schleife tun können, die Sie mit Rekursion nicht tun können).

Das soll nicht heißen, dass es einige Problemklassen gibt, die eher mit Rekursion als mit Schleifen oder eher mit Schleifen als mit Rekursion betrachtet werden können. Diese Tools sind jedoch ebenso leistungsfähig.

Und während ich das auf die Spitze getrieben habe (vor allem, weil man Dinge findet, die Turing komplett und auf seltsame Weise implementiert), heißt das nicht, dass die Esolangs auf keinen Fall optional sind. Es gibt eine ganze Liste von Dingen, die versehentlich komplett sind einschließlich Magic the Gathering, Sendmail, MediaWiki-Vorlagen und dem Scala-Typensystem. Viele davon sind alles andere als optimal, wenn es darum geht, tatsächlich etwas Praktisches zu tun. Sie können lediglich alles berechnen, was mit diesen Tools berechenbar ist.


Diese Äquivalenz kann besonders interessant werden, wenn Sie sich mit einer bestimmten Art von Rekursion befassen, die als Tail Call bezeichnet wird .

Wenn Sie beispielsweise eine Fakultätsmethode haben, die wie folgt geschrieben wurde:

int fact(int n) {
    return fact(n, 1);
}

int fact(int n, int accum) {
    if(n == 0) { return 1; }
    if(n == 1) { return accum; }
    return fact(n-1, n * accum);
}

Diese Art der Rekursion wird als Schleife umgeschrieben - es wird kein Stapel verwendet. Solche Ansätze sind in der Tat oft eleganter und leichter zu verstehen als die zu schreibende äquivalente Schleife, aber auch hier kann für jeden rekursiven Aufruf eine äquivalente Schleife geschrieben werden und für jede Schleife kann ein rekursiver Aufruf geschrieben werden.

Es gibt auch Zeiten , in denen die einfache Schleife in einen Endaufruf rekursiven Aufruf Umwandlung kann verworren und seine mehr schwer zu verstehen.


Wenn Sie sich mit der Theorie befassen möchten, lesen Sie die These von Church Turing . Sie können auch die kirchliche These auf CS.SE als nützlich erachten.

Gemeinschaft
quelle
29
Die Vollständigkeit der Prüfung wird zu sehr ins Wanken gebracht, als dass es darauf ankommt. Viele Dinge sind Turing Complete ( wie Magic the Gathering ), aber das heißt nicht, dass es dasselbe ist wie etwas anderes, das Turing Complete ist. Zumindest nicht auf einem Niveau, das zählt. Ich möchte mit Magic the Gathering nicht auf einem Baum herumlaufen.
Scant Roger
7
Sobald Sie ein Problem auf "das hat die gleiche Leistung wie eine Turing-Maschine" reduzieren können, ist es genug, um es dort hin zu bringen. Turingmaschinen sind eine eher geringe Hürde, aber es ist alles was benötigt wird. Es gibt nichts, was eine Schleife nicht kann, und umgekehrt.
4
Die Aussage in dieser Antwort ist natürlich richtig, aber ich wage zu sagen, dass das Argument nicht wirklich überzeugend ist. Turing-Maschinen haben kein direktes Konzept der Rekursion. Wenn Sie also sagen, dass Sie eine Turing-Maschine ohne Rekursion simulieren können, beweisen Sie nichts. Was Sie vorweisen müssen, um die Aussage zu beweisen, ist, dass Turing-Maschinen eine Rekursion simulieren können. Wenn Sie dies nicht zeigen, müssen Sie getreu davon ausgehen, dass die Church-Turing-Hypothese auch für die Rekursion gilt (was auch der OP in Frage stellt).
5gon12eder
10
Die Frage des OP lautet "kann", nicht "am besten" oder "am effizientesten" oder ein anderes Qualifikationsmerkmal. "Turing Complete" bedeutet, dass alles, was mit der Rekursion gemacht werden kann, auch mit einer Schleife gemacht werden kann. Ob dies in einer bestimmten Sprachimplementierung der beste Weg ist, ist eine ganz andere Frage.
Steven Burnap
7
"Can" ist sehr viel NICHT das Gleiche wie "best". Wenn Sie "nicht am besten" mit "kann nicht" verwechseln, werden Sie gelähmt, weil es fast immer einen besseren Weg gibt, egal wie Sie etwas tun.
Steven Burnap
31

Gibt es Fälle, in denen eine Aufgabe nur durch Rekursion und nicht durch eine Schleife ausgeführt werden kann?

Sie können einen rekursiven Algorithmus jederzeit in eine Schleife umwandeln, die eine Last-In-First-Out-Datenstruktur (AKA-Stapel) zum Speichern des temporären Zustands verwendet, da ein rekursiver Aufruf genau das ist: Speichern des aktuellen Zustands in einem Stapel, Fortsetzen des Algorithmus. dann später den Zustand wiederherstellen. Die kurze Antwort lautet also: Nein, solche Fälle gibt es nicht .

Es kann jedoch ein Argument für "Ja" angegeben werden. Nehmen wir ein konkretes, einfaches Beispiel: Sortieren zusammenführen. Sie müssen die Daten in zwei Teile teilen, die Teile zusammenführen, sortieren und dann kombinieren. Selbst wenn Sie keinen eigentlichen Funktionsaufruf für die Programmiersprache ausführen, um die Teile zusammenzuführen, müssen Sie Funktionen implementieren, die mit denen eines tatsächlichen Funktionsaufrufs identisch sind (Push-Status auf Ihren eigenen Stack, Sprung zu Start der Schleife mit verschiedenen Startparametern, dann später den Zustand von Ihrem Stapel ziehen).

Ist es Rekursion, wenn Sie den Rekursionsaufruf selbst implementieren, als separate Schritte "Push-Status" und "Zum Anfang springen" und "Pop-Status"? Und die Antwort darauf lautet: Nein, es wird immer noch nicht als Rekursion bezeichnet, sondern als Iteration mit explizitem Stack (wenn Sie eine etablierte Terminologie verwenden möchten).


Beachten Sie, dass dies auch von der Definition von "Aufgabe" abhängt. Wenn es darum geht, zu sortieren, können Sie dies mit vielen Algorithmen tun, von denen viele keinerlei Rekursion benötigen. Wenn es die Aufgabe ist, einen bestimmten Algorithmus zu implementieren, z.

Betrachten wir also die Frage, ob es allgemeine Aufgaben gibt, für die es nur rekursionsähnliche Algorithmen gibt. Aus dem Kommentar von @WizardOfMenlo unter der Frage geht hervor, dass die Ackermann-Funktion ein einfaches Beispiel dafür ist. Das Konzept der Rekursion steht also für sich, auch wenn es mit einem anderen Computerprogrammkonstrukt (Iteration mit explizitem Stack) implementiert werden kann.

hyde
quelle
2
Wenn es sich um eine Baugruppe für einen stapellosen Prozessor handelt, werden diese beiden Techniken plötzlich zu einer.
Joshua
@ Joshua In der Tat! Es ist eine Frage der Abstraktionsebene. Wenn Sie ein oder zwei Level tiefer gehen, sind es nur logische Tore.
Hyde
2
Das ist nicht ganz richtig. Um eine Rekursion mit Iteration zu emulieren, benötigen Sie einen Stapel, auf den wahlfrei zugegriffen werden kann. Ein einzelner Stapel ohne wahlfreien Zugriff und mit einer begrenzten Menge direkt zugänglichen Speichers wäre ein PDA, der nicht vollständig ist.
Gilles
@Gilles Alter Beitrag, aber warum wird ein Stapel mit wahlfreiem Zugriff benötigt? Sind nicht auch alle realen Computer weniger als PDAs, da sie nur eine begrenzte Menge an direkt zugänglichem Speicher haben und überhaupt keinen Stapel (außer durch Verwendung dieses Speichers)? Dies scheint keine sehr praktische Abstraktion zu sein, wenn es heißt "wir können in der Realität keine Rekursion machen".
Hyde
20

Es kommt darauf an, wie streng Sie "Rekursion" definieren.

Wenn wir unbedingt verlangen, dass der Aufruf-Stack einbezogen wird (oder welcher Mechanismus zur Aufrechterhaltung des Programmstatus auch immer verwendet wird), können wir ihn jederzeit durch etwas ersetzen, das dies nicht tut. In der Tat haben Sprachen, die auf natürliche Weise zu einer starken Nutzung der Rekursion führen, in der Regel Compiler, die die Tail-Call-Optimierung stark nutzen. Was Sie also schreiben, ist rekursiv, was Sie ausführen, ist iterativ.

Betrachten wir jedoch einen Fall, in dem wir einen rekursiven Aufruf ausführen und das Ergebnis eines rekursiven Aufrufs für diesen rekursiven Aufruf verwenden.

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  if (m == 0)
    return  n+1;
  if (n == 0)
    return Ackermann(m - 1, 1);
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Es ist einfach, den ersten rekursiven Aufruf zu wiederholen:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
restart:
  if (m == 0)
    return  n+1;
  if (n == 0)
  {
    m--;
    n = 1;
    goto restart;
  }
  else
    return Ackermann(m - 1, Ackermann(m, n - 1));
}

Wir können dann gotodie Velociraptoren und den Schatten von Dijkstra entfernen , um sie abzuwehren :

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  while(m != 0)
  {
    if (n == 0)
    {
      m--;
      n = 1;
    }
    else
      return Ackermann(m - 1, Ackermann(m, n - 1));
  }
  return  n+1;
}

Um die anderen rekursiven Aufrufe zu entfernen, müssen wir die Werte einiger Aufrufe in einem Stapel speichern:

public static BigInteger Ackermann(BigInteger m, BigInteger n)
{
  Stack<BigInteger> stack = new Stack<BigInteger>();
  stack.Push(m);
  while(stack.Count != 0)
  {
    m = stack.Pop();
    if(m == 0)
      n = n + 1;
    else if(n == 0)
    {
      stack.Push(m - 1);
      n = 1;
    }
    else
    {
      stack.Push(m - 1);
      stack.Push(m);
      --n;
    }
  }
  return n;
}

Wenn wir nun den Quellcode betrachten, haben wir unsere rekursive Methode zweifellos in eine iterative Methode umgewandelt.

In Anbetracht dessen, wozu dies kompiliert wurde, haben wir Code, der den Aufrufstapel verwendet, um eine Rekursion in Code zu implementieren, der dies nicht tut, umgewandelt (und dabei Code, der eine Stapelüberlauf-Ausnahme für selbst recht kleine Werte in Code auslöst, der nur wird) es dauert unglaublich lange, bis ich zurückkomme [siehe Wie kann ich verhindern, dass meine Ackerman-Funktion den Stapel überläuft? für einige weitere Optimierungen, die dafür sorgen, dass er tatsächlich für viele weitere mögliche Eingaben zurückkommt).

In Anbetracht der allgemeinen Implementierung der Rekursion haben wir Code, der den Aufrufstapel verwendet, in Code umgewandelt, der einen anderen Stapel verwendet, um ausstehende Vorgänge zu speichern. Wir könnten daher argumentieren, dass es immer noch rekursiv ist, wenn man es auf diesem niedrigen Niveau betrachtet.

Und auf dieser Ebene gibt es in der Tat keine anderen Möglichkeiten. Wenn Sie diese Methode als rekursiv betrachten, dann gibt es tatsächlich Dinge, die wir ohne sie nicht tun können. Im Allgemeinen wird ein solcher Code jedoch nicht als rekursiv bezeichnet. Der Begriff Rekursion ist nützlich, weil er eine Reihe von Ansätzen abdeckt und uns die Möglichkeit gibt, darüber zu sprechen, und wir verwenden keinen von ihnen mehr.

All dies setzt natürlich voraus, dass Sie die Wahl haben. Es gibt sowohl Sprachen, die rekursive Aufrufe verbieten, als auch Sprachen, denen die für die Iteration erforderlichen Schleifenstrukturen fehlen.

Jon Hanna
quelle
Es ist nur möglich, den Aufrufstapel durch etwas Äquivalentes zu ersetzen, wenn entweder der Aufrufstapel begrenzt ist oder auf einen unbegrenzten Speicher außerhalb des Aufrufstapels zugegriffen werden kann. Es gibt eine bedeutende Klasse von Problemen, die durch Push-Down-Automaten gelöst werden können, die einen unbegrenzten Aufrufstapel haben, ansonsten aber nur eine begrenzte Anzahl von Zuständen haben können.
Supercat
Dies ist die beste Antwort, vielleicht die einzig richtige. Auch das zweite Beispiel ist immer noch rekursiv, und auf dieser Ebene lautet die Antwort auf die ursprüngliche Frage nein . Mit einer breiteren Definition der Rekursion ist eine Rekursion für die Ackermann-Funktion nicht zu vermeiden.
Gerrit
@gerrit und mit einem engeren, vermeidet es es. Letztendlich kommt es auf die Grenzen dessen an, was wir tun oder nicht tun, um dieses nützliche Label anzuwenden, das wir für bestimmten Code verwenden.
Jon Hanna
1
Hat sich der Seite angeschlossen, um darüber abzustimmen. Die Ackermann-Funktion / ist / rekursiv. Wenn Sie eine rekursive Struktur mit einer Schleife und einem Stapel implementieren, ist dies keine iterative Lösung. Sie haben die Rekursion lediglich in den Benutzerbereich verschoben.
Aaron McMillin
9

Die klassische Antwort lautet "Nein", aber lassen Sie mich näher erläutern, warum ich "Ja" für eine bessere Antwort halte.


Bevor wir fortfahren, lassen Sie uns etwas aus dem Weg räumen: Vom Standpunkt der Berechenbarkeit und Komplexität aus:

  • Die Antwort lautet "nein", wenn Sie beim Schleifen einen Zusatzstapel haben dürfen.
  • Die Antwort lautet "Ja", wenn Sie beim Schleifen keine zusätzlichen Daten erhalten.

Okay, jetzt lass uns einen Fuß in die Praxis setzen, den anderen Fuß in die Theorie.


Der Aufrufstapel ist eine Kontrollstruktur , während ein manueller Stapel eine Datenstruktur ist. Kontrolle und Daten sind keine gleichen Konzepte, aber sie sind in dem Sinne äquivalent, dass sie in Bezug auf Berechenbarkeit oder Komplexität auf einander reduziert (oder über einander "emuliert") werden können.

Wann könnte diese Unterscheidung von Bedeutung sein? Wenn Sie mit Tools aus der Praxis arbeiten. Hier ist ein Beispiel:

Angenommen, Sie implementieren N-way mergesort. Möglicherweise haben Sie eine forSchleife, die jedes der NSegmente durchläuft , mergesortsie separat aufruft und dann die Ergebnisse zusammenführt.

Wie könnten Sie dies mit OpenMP parallelisieren?

Im rekursiven Bereich ist es extrem einfach: einfach ausgedrückt #pragma omp parallel for Ihre Schleife um, die von 1 nach N geht, und Sie sind fertig. Im iterativen Bereich können Sie dies nicht tun. Sie müssen Threads manuell erzeugen und ihnen die entsprechenden Daten manuell übergeben, damit sie wissen, was zu tun ist.

Auf der anderen Seite gibt es andere Tools (wie z. B. automatische Vektorisierer #pragma vector), die mit Schleifen arbeiten, bei Rekursion jedoch völlig unbrauchbar sind.

Nur weil Sie beweisen können, dass die beiden Paradigmen mathematisch äquivalent sind, heißt das nicht, dass sie in der Praxis gleich sind. Ein Problem, das in einem Paradigma trivial zu automatisieren ist (z. B. Schleifenparallelisierung), ist im anderen Paradigma möglicherweise viel schwieriger zu lösen.

Das heißt: Werkzeuge für ein Paradigma werden nicht automatisch in andere Paradigmen übersetzt.

Wenn Sie ein Tool zur Lösung eines Problems benötigen, funktioniert das Tool möglicherweise nur mit einer bestimmten Herangehensweise. Infolgedessen können Sie das Problem nicht mit einer anderen Herangehensweise lösen, auch wenn Sie dies mathematisch nachweisen können so oder so gelöst werden.

Mehrdad
quelle
Bedenken Sie auch darüber hinaus, dass die Menge der Probleme, die mit einem Push-Down-Automaten gelöst werden kann, größer ist als die Menge, die mit einem endlichen Automaten (deterministisch oder nicht deterministisch) gelöst werden kann, aber kleiner als die Menge, die mit a gelöst werden kann Turing Maschine.
Supercat
8

Schauen wir uns neben den theoretischen Überlegungen an, wie Rekursionen und Schleifen aus der Sicht einer (Hardware- oder virtuellen) Maschine aussehen. Rekursion ist eine Kombination aus Kontrollfluss, mit der die Ausführung eines Codes gestartet und nach Abschluss (in einer vereinfachten Ansicht, wenn Signale und Ausnahmen ignoriert werden) und Daten, die an diesen anderen Code (Argumente) übergeben und von diesem zurückgegeben werden, zurückgegeben werden kann es (Ergebnis). In der Regel ist keine explizite Speicherverwaltung erforderlich, es wird jedoch implizit Stapelspeicher zugewiesen, um Rücksprungadressen, Argumente, Ergebnisse und lokale Zwischendaten zu speichern.

Eine Schleife ist eine Kombination aus Kontrollfluss und lokalen Daten. Vergleicht man dies mit einer Rekursion, so sieht man, dass die Datenmenge in diesem Fall festgelegt ist. Die einzige Möglichkeit, diese Einschränkung aufzuheben, ist die Verwendung von dynamischem Speicher (auch als Heap bezeichnet ), der bei Bedarf zugewiesen (und freigegeben) werden kann.

Zusammenfassen:

  • Rekursionsfall = Kontrollfluss + Stapel (+ Heap)
  • Loop case = Kontrollfluss + Heap

Unter der Annahme, dass der Steuerungsablaufteil einigermaßen leistungsfähig ist, besteht der einzige Unterschied in den verfügbaren Speichertypen. Wir haben also noch 4 Fälle (die Aussagekraft ist in Klammern angegeben):

  1. Kein Stapel, kein Haufen: Rekursion und dynamische Strukturen sind unmöglich. (Rekursion = Schleife)
  2. Stack, kein Heap: Rekursion ist in Ordnung, dynamische Strukturen sind unmöglich. (Rekursion> Schleife)
  3. Kein Stapel, Haufen: Rekursion ist unmöglich, dynamische Strukturen sind in Ordnung. (Rekursion = Schleife)
  4. Stack, Heap: Rekursion und dynamische Strukturen sind in Ordnung. (Rekursion = Schleife)

Wenn die Spielregeln etwas strenger sind und die rekursive Implementierung keine Schleifen verwenden darf, erhalten wir stattdessen Folgendes:

  1. Kein Stapel, kein Haufen: Rekursion und dynamische Strukturen sind unmöglich. (Rekursion <Schleife)
  2. Stack, kein Heap: Rekursion ist in Ordnung, dynamische Strukturen sind unmöglich. (Rekursion> Schleife)
  3. Kein Stapel, Haufen: Rekursion ist unmöglich, dynamische Strukturen sind in Ordnung. (Rekursion <Schleife)
  4. Stack, Heap: Rekursion und dynamische Strukturen sind in Ordnung. (Rekursion = Schleife)

Der Hauptunterschied zum vorherigen Szenario besteht darin, dass aufgrund des fehlenden Stapelspeichers bei einer Rekursion ohne Schleifen während der Ausführung nicht mehr Schritte ausgeführt werden können als in Codezeilen.

Alexander Kogtenkov
quelle
2

Ja. Es gibt mehrere allgemeine Aufgaben, die mit der Rekursion leicht zu erledigen sind, mit einfachen Schleifen jedoch nicht möglich sind:

  • Stapel läuft über.
  • Total verwirrende Anfängerprogrammierer.
  • Erstellen Sie schnell aussehende Funktionen, die tatsächlich O (n ^ n) sind.
jpa
quelle
3
Bitte, diese sind wirklich einfach mit Schleifen, ich sehe sie die ganze Zeit. Verdammt, mit ein bisschen Mühe brauchst du nicht einmal die Schleifen. Auch wenn Rekursion einfacher ist.
AviD
1
tatsächlich ist A (0, n) = n + 1; A (m, 0) = A (m - 1,1), wenn m> 0 ist; A (m, n) = A (m-1, A (m, n-1)) wenn m> 0, n> 0 wächst sogar ein bisschen schneller als O (n ^ n) (für m = n) :)
John Donn
1
@ JohnDonn Mehr als ein bisschen, es ist super exponentiell. für n = 3 n ^ n ^ n für n = 4 n ^ n ^ n ^ n ^ n und so weiter. n auf die n-fache Potenz.
Aaron McMillin
1

Es gibt einen Unterschied zwischen rekursiven Funktionen und primitiven rekursiven Funktionen. Primitive rekursive Funktionen sind solche, die unter Verwendung von Schleifen berechnet werden, wobei die maximale Iterationszahl jeder Schleife berechnet wird, bevor die Schleifenausführung beginnt. (Und "rekursiv" hat hier nichts mit der Verwendung von Rekursion zu tun).

Primitive rekursive Funktionen sind weniger leistungsfähig als rekursive Funktionen. Das gleiche Ergebnis würden Sie erhalten, wenn Sie Funktionen verwenden, die die Rekursion verwenden, wobei die maximale Tiefe der Rekursion im Voraus berechnet werden muss.

gnasher729
quelle
3
Ich bin nicht sicher, wie dies auf die Frage oben zutrifft? Können Sie diesen Zusammenhang bitte deutlicher machen?
Yakk
1
Ersetzen der ungenauen "Schleife" durch die wichtige Unterscheidung zwischen "Schleife mit begrenzter Iterationszahl" und "Schleife mit unbegrenzter Iterationszahl", von der ich dachte, dass sie jeder von CS 101 kennen würde.
gnasher729
sicher, aber es gilt immer noch nicht für die Frage. Die Frage ist nach Schleifen und Rekursionen, nicht nach primitiven Rekursionen und Rekursionen. Stellen Sie sich vor, jemand hätte nach C / C ++ - Unterschieden gefragt und Sie hätten nach dem Unterschied zwischen K & R C und Ansi C geantwortet. Das präzisiert zwar die Dinge, beantwortet aber nicht die Frage.
Yakk
1

Wenn Sie in c ++ programmieren und c ++ 11 verwenden, müssen Sie eine Sache mit Rekursionen erledigen: constexpr-Funktionen. Der Standard begrenzt dies jedoch auf 512, wie in dieser Antwort erläutert . Die Verwendung von Schleifen ist in diesem Fall nicht möglich, da in diesem Fall die Funktion nicht constexpr sein kann, dies wird jedoch in c ++ 14 geändert.

BЈовић
quelle
0
  • Wenn der rekursive Aufruf die allererste oder allerletzte Anweisung (mit Ausnahme der Bedingungsprüfung) einer rekursiven Funktion ist, ist die Übersetzung in eine Schleifenstruktur ziemlich einfach.
  • Wenn die Funktion jedoch vor und nach dem rekursiven Aufruf noch einige andere Aufgaben ausführt , ist es umständlich, sie in Schleifen umzuwandeln.
  • Wenn die Funktion mehrere rekursive Aufrufe hat, ist das Konvertieren in Code, der nur Schleifen verwendet, so gut wie unmöglich. Einige Stapel werden benötigt, um mit den Daten Schritt zu halten. In der Rekursion fungiert der Aufrufstapel selbst als Datenstapel.
Gulshan
quelle
Tree Walking hat mehrere rekursive Aufrufe (einen für jedes Kind), wird jedoch mithilfe eines expliziten Stapels trivial in eine Schleife umgewandelt. Parser hingegen sind oftmals nervig zu transformieren.
CodesInChaos
@CodesInChaos Bearbeitet.
Gulshan
-6

Ich stimme den anderen Fragen zu. Es gibt nichts, was Sie mit Rekursion tun können, was Sie mit einer Schleife nicht tun können.

ABER meiner Meinung nach kann eine Rekursion sehr gefährlich sein. Erstens ist es für einige schwieriger zu verstehen, was tatsächlich im Code passiert. Zweitens hat jeder Rekursionsschritt, zumindest für C ++ (ich bin mir nicht sicher, ob Java), eine Auswirkung auf den Speicher, da jeder Methodenaufruf eine Speicherakkumulation und Initialisierung des Methodenkopfs verursacht. Auf diese Weise können Sie Ihren Stapel sprengen. Versuchen Sie einfach die Rekursion der Fibonacci-Zahlen mit einem hohen Eingabewert.

Ben1980
quelle
2
Bei einer naiven rekursiven Implementierung von Fibonacci-Zahlen mit Rekursion wird die "Zeit knapp", bevor der Stapelspeicherplatz knapp wird. Ich denke, es gibt andere Probleme, die für dieses Beispiel besser sind. Bei vielen Problemen wirkt sich eine Schleifenversion genauso auf den Speicher aus wie eine rekursive, und zwar nur auf dem Heap anstelle des Stacks (sofern Ihre Programmiersprache diese unterscheidet).
Paŭlo Ebermann
6
Schleife kann auch "sehr gefährlich" sein, wenn Sie nur vergessen, die Schleifenvariable zu erhöhen ...
h22
2
Das absichtliche Erzeugen eines Stapelüberlaufs ist in der Tat eine Aufgabe, die ohne Verwendung von Rekursion sehr schwierig wird.
5gon12eder
@ 5gon12eder das bringt uns zu Welche Methoden gibt es, um einen Stapelüberlauf in einem rekursiven Algorithmus zu vermeiden? - Schreiben, um TCO zu aktivieren, oder Memoisieren können nützlich sein. Iterative vs. rekursive Ansätze sind ebenfalls interessant, da es sich um zwei verschiedene rekursive Ansätze für Fibonacci handelt.
1
Wenn bei der Rekursion ein Stapelüberlauf auftritt, hat sich die iterative Version in den meisten Fällen verändert. Zumindest der erstere wirft mit einem Stack-Trace.
Jon Hanna