Was ist Rekursion und wann sollte ich sie verwenden?

Question

Eines der Themen, das in Mailinglisten und Online-Diskussionen regelmäßig auftaucht, ist die Frage nach den Vorzügen (oder dem Fehlen davon) eines Informatikstudiums.Ein Argument, das für die negative Seite immer wieder auftaucht, ist, dass sie schon seit einigen Jahren programmieren und nie Rekursion verwendet haben.

Die Frage ist also:

1. Was ist Rekursion?
2. Wann würde ich Rekursion verwenden?
3. Warum verwenden die Leute keine Rekursion?

Answer 1

Es gibt eine Reihe guter Erklärungen dazu Rekursion In diesem Thread geht es in dieser Antwort darum, warum Sie es in den meisten Sprachen nicht verwenden sollten.* In den meisten wichtigen imperativen Sprachimplementierungen (d. h.jede größere Implementierung von C, C++, Basic, Python, Ruby, Java und C#) Wiederholung ist der Rekursion weitaus vorzuziehen.

Um herauszufinden, warum, gehen Sie die Schritte durch, die die oben genannten Sprachen zum Aufrufen einer Funktion verwenden:

1. Platz ist herausgearbeitet der Stapel für die Argumente und lokalen Variablen der Funktion
2. Die Argumente der Funktion werden in diesen neuen Bereich kopiert
3. Die Steuerung springt zur Funktion
4. Der Code der Funktion wird ausgeführt
5. Das Ergebnis der Funktion wird in einen Rückgabewert kopiert
6. Der Stapel wird in seine vorherige Position zurückgespult
7. Die Steuerung springt dorthin zurück, wo die Funktion aufgerufen wurde

Die Durchführung all dieser Schritte nimmt Zeit in Anspruch, normalerweise etwas mehr als das Durchlaufen einer Schleife.Das eigentliche Problem liegt jedoch in Schritt 1.Wenn viele Programme starten, weisen sie ihrem Stapel einen einzigen Speicherblock zu, und wenn ihnen dieser Speicher ausgeht (häufig, aber nicht immer aufgrund von Rekursion), stürzt das Programm aufgrund eines ab Paketüberfluss.

Daher ist die Rekursion in diesen Sprachen langsamer und anfällig für Abstürze.Es gibt jedoch immer noch einige Argumente für die Verwendung.Im Allgemeinen ist rekursiv geschriebener Code kürzer und etwas eleganter, wenn Sie erst einmal wissen, wie man ihn liest.

Es gibt eine Technik, die Sprachimplementierer verwenden können: Tail-Call-Optimierung Dadurch können einige Klassen von Stapelüberläufen beseitigt werden.Kurz gesagt:Wenn der Rückgabeausdruck einer Funktion einfach das Ergebnis eines Funktionsaufrufs ist, müssen Sie dem Stapel keine neue Ebene hinzufügen, sondern können die aktuelle Ebene für die aufgerufene Funktion wiederverwenden.Bedauerlicherweise verfügen nur wenige imperative Sprachimplementierungen über eine integrierte Tail-Call-Optimierung.

* Ich liebe Rekursion. Meine liebste statische Sprache verwendet überhaupt keine Schleifen, Rekursion ist die einzige Möglichkeit, etwas wiederholt zu tun.Ich glaube einfach nicht, dass Rekursion in Sprachen, die nicht darauf abgestimmt sind, generell eine gute Idee ist.

** Übrigens, Mario, der typische Name für Ihre ArrangeString-Funktion ist „join“, und ich wäre überrascht, wenn die Sprache Ihrer Wahl nicht bereits über eine Implementierung davon verfügt.

Answer 2

Einfaches englisches Beispiel für Rekursion.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her a story about a little weasel... 
            who fell asleep.
         ...and the little bear fell asleep;
    ...and the little frog fell asleep;
...and the child fell asleep.

Answer 3

Im grundlegendsten Sinne der Informatik ist Rekursion eine Funktion, die sich selbst aufruft.Angenommen, Sie haben eine verknüpfte Listenstruktur:

struct Node {
    Node* next;
};

Und wenn Sie herausfinden möchten, wie lang eine verknüpfte Liste ist, können Sie dies mit der Rekursion tun:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Dies könnte natürlich auch mit einer for-Schleife erfolgen, ist aber zur Veranschaulichung des Konzepts nützlich.)

Answer 4

Immer wenn eine Funktion sich selbst aufruft und eine Schleife erzeugt, dann ist das eine Rekursion.Wie bei allem gibt es gute und schlechte Verwendungsmöglichkeiten für die Rekursion.

Das einfachste Beispiel ist die Schwanzrekursion, bei der die allerletzte Zeile der Funktion ein Aufruf an sich selbst ist:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

Dies ist jedoch ein lahmes, fast sinnloses Beispiel, da es leicht durch eine effizientere Iteration ersetzt werden kann.Schließlich leidet die Rekursion unter dem Funktionsaufruf-Overhead, der im obigen Beispiel im Vergleich zur Operation innerhalb der Funktion selbst erheblich sein könnte.

Der ganze Grund für die Rekursion statt der Iteration sollte also darin bestehen, die Vorteile zu nutzen Aufrufstapel um ein paar clevere Sachen zu machen.Wenn Sie beispielsweise eine Funktion mehrmals mit unterschiedlichen Parametern innerhalb derselben Schleife aufrufen, ist dies eine Möglichkeit, dies zu erreichen Verzweigung.Ein klassisches Beispiel ist das Sierpinski-Dreieck.

Sie können eines davon ganz einfach mit Rekursion zeichnen, bei dem der Aufrufstapel in drei Richtungen verzweigt:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

Wenn Sie versuchen, dasselbe mit der Iteration zu erreichen, werden Sie meiner Meinung nach feststellen, dass dafür viel mehr Code erforderlich ist.

Andere häufige Anwendungsfälle könnten das Durchqueren von Hierarchien umfassen, z.Website-Crawler, Verzeichnisvergleiche usw.

Abschluss

In der Praxis ist die Rekursion immer dann am sinnvollsten, wenn Sie eine iterative Verzweigung benötigen.

Answer 5

Rekursion ist eine Methode zur Lösung von Problemen, die auf der Teile-und-herrsche-Mentalität basiert.Die Grundidee besteht darin, dass Sie das ursprüngliche Problem in kleinere (leichter lösbare) Instanzen von sich selbst aufteilen, diese kleineren Instanzen lösen (normalerweise unter erneuter Verwendung desselben Algorithmus) und sie dann zur endgültigen Lösung wieder zusammensetzen.

Das kanonische Beispiel ist eine Routine zum Generieren der Fakultät von n.Die Fakultät von n wird durch Multiplikation aller Zahlen zwischen 1 und n berechnet.Eine iterative Lösung in C# sieht so aus:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Die iterative Lösung ist nicht überraschend und sollte für jeden, der mit C# vertraut ist, Sinn ergeben.

Die rekursive Lösung wird gefunden, indem man erkennt, dass die n-te Fakultät n * Fact(n-1) ist.Oder anders ausgedrückt: Wenn Sie wissen, was eine bestimmte Faktorzahl ist, können Sie die nächste berechnen.Hier ist die rekursive Lösung in C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

Der erste Teil dieser Funktion ist als a bekannt Basisfall (oder manchmal Schutzklausel) und verhindert, dass der Algorithmus ewig läuft.Es gibt lediglich den Wert 1 zurück, wenn die Funktion mit einem Wert von 1 oder weniger aufgerufen wird.Der zweite Teil ist interessanter und heißt Rekursiver Schritt.Hier rufen wir dieselbe Methode mit einem leicht modifizierten Parameter auf (wir dekrementieren ihn um 1) und multiplizieren dann das Ergebnis mit unserer Kopie von n.

Beim ersten Anblick kann es etwas verwirrend sein, daher ist es aufschlussreich, zu untersuchen, wie es funktioniert, wenn es ausgeführt wird.Stellen Sie sich vor, wir rufen FactRec(5) auf.Wir steigen in die Routine ein, werden vom Basisfall nicht abgeholt und am Ende sieht es so aus:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

Wenn wir die Methode mit dem Parameter 4 erneut eingeben, werden wir erneut nicht durch die Guard-Klausel gestoppt und landen bei:

// In FactRec(4)
return 4 * FactRec(3);

Wenn wir diesen Rückgabewert in den obigen Rückgabewert einsetzen, erhalten wir

// In FactRec(5)
return 5 * (4 * FactRec(3));

Dies sollte Ihnen einen Anhaltspunkt dafür geben, wie die endgültige Lösung zustande kommt, sodass wir jeden Schritt auf dem Weg nach unten schnell verfolgen und zeigen können:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Diese endgültige Ersetzung erfolgt, wenn der Basisfall ausgelöst wird.An diesem Punkt müssen wir eine einfache algrebraische Formel lösen, die in erster Linie direkt der Definition von Fakultäten entspricht.

Es ist aufschlussreich zu beachten, dass jeder Aufruf der Methode dazu führt, dass entweder ein Basisfall ausgelöst wird oder dass dieselbe Methode aufgerufen wird, bei der die Parameter näher an einem Basisfall liegen (oft als rekursiver Aufruf bezeichnet).Ist dies nicht der Fall, läuft die Methode ewig.

Answer 6

Bei der Rekursion wird ein Problem mit einer Funktion gelöst, die sich selbst aufruft.Ein gutes Beispiel hierfür ist eine Fakultätsfunktion.Fakultät ist ein mathematisches Problem, bei dem die Fakultät von 5 beispielsweise 5 * 4 * 3 * 2 * 1 ist.Diese Funktion löst dieses Problem in C# für positive Ganzzahlen (nicht getestet – möglicherweise liegt ein Fehler vor).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Answer 7

Rekursion bezieht sich auf eine Methode, die ein Problem löst, indem sie eine kleinere Version des Problems löst und dann dieses Ergebnis zusammen mit einer anderen Berechnung verwendet, um die Antwort auf das ursprüngliche Problem zu formulieren.Oft löst die Methode im Prozess der Lösung der kleineren Version eine noch kleinere Version des Problems usw., bis sie einen „Basisfall“ erreicht, der trivial zu lösen ist.

Zum Beispiel, um eine Fakultät für die Zahl zu berechnen X, man kann es darstellen als X times the factorial of X-1.Daher führt die Methode eine „Rekursion“ durch, um die Fakultät von zu ermitteln X-1, und multipliziert dann alles, was dabei herausgekommen ist X um eine abschließende Antwort zu geben.Natürlich, um die Fakultät von zu finden X-1, wird zunächst die Fakultät von berechnet X-2, und so weiter.Der Basisfall wäre wann X ist 0 oder 1, in diesem Fall weiß es, dass es zurückkehren muss 1 seit 0! = 1! = 1.

Answer 8

Betrachten Sie eine altes, bekanntes Problem:

In der Mathematik ist die größter gemeinsamer Teiler (gcd) … von zwei oder mehr ganzen Zahlen ungleich Null ist die größte positive ganze Zahl, die die Zahlen ohne Rest dividiert.

Die Definition von gcd ist überraschend einfach:

Wo ist Mod? Modulo-Operator (d. h. der Rest nach der Ganzzahldivision).

Auf Englisch besagt diese Definition, dass der größte gemeinsame Teiler einer beliebigen Zahl und Null diese Zahl und der größte gemeinsame Teiler zweier Zahlen ist M Und N ist der größte gemeinsame Teiler von N und der Rest nach der Division M von N.

Wenn Sie wissen möchten, warum das funktioniert, lesen Sie den Wikipedia-Artikel zum Thema Euklidischer Algorithmus.

Lassen Sie uns als Beispiel gcd(10, 8) berechnen.Jeder Schritt entspricht dem unmittelbar davor:

1. gcd(10, 8)
2. gcd(10, 10 mod 8)
3. gcd(8, 2)
4. gcd(8, 8 mod 2)
5. gcd(2, 0)
6. 2

Im ersten Schritt ist 8 nicht gleich Null, daher gilt der zweite Teil der Definition.10 mod 8 = 2, weil 8 einmal in 10 geht mit einem Rest von 2.Bei Schritt 3 gilt erneut der zweite Teil, dieses Mal jedoch 8 mod 2 = 0, da 2 8 ohne Rest teilt.In Schritt 5 ist das zweite Argument 0, also ist die Antwort 2.

Ist Ihnen aufgefallen, dass gcd sowohl auf der linken als auch auf der rechten Seite des Gleichheitszeichens erscheint?Ein Mathematiker würde sagen, dass diese Definition rekursiv ist, weil der Ausdruck, den Sie definieren wiederholt sich innerhalb seiner Definition.

Rekursive Definitionen sind in der Regel elegant.Eine rekursive Definition für die Summe einer Liste ist beispielsweise

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

Wo head ist das erste Element in einer Liste und tail ist der Rest der Liste.Beachten Sie, dass sum kehrt am Ende innerhalb seiner Definition zurück.

Vielleicht bevorzugen Sie stattdessen den Maximalwert in einer Liste:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Sie können die Multiplikation nicht negativer Ganzzahlen rekursiv definieren, um sie in eine Reihe von Additionen umzuwandeln:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

Wenn der Teil über die Umwandlung einer Multiplikation in eine Reihe von Additionen keinen Sinn ergibt, versuchen Sie, ein paar einfache Beispiele zu erweitern, um zu sehen, wie es funktioniert.

Zusammenführen, sortieren hat eine schöne rekursive Definition:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Rekursive Definitionen gibt es überall, wenn Sie wissen, wonach Sie suchen müssen.Beachten Sie, dass alle diese Definitionen sehr einfache Basisfälle haben. z.B., ggT(m, 0) = m.Die rekursiven Fälle reduzieren das Problem, um zu einfachen Antworten zu gelangen.

Mit diesem Verständnis können Sie nun die anderen Algorithmen in verstehen Wikipedia-Artikel zur Rekursion!

Answer 9

1. Eine Funktion, die sich selbst aufruft
2. Wenn eine Funktion (einfach) in eine einfache Operation und dieselbe Funktion für einen kleineren Teil des Problems zerlegt werden kann.Ich sollte eher sagen, dass dies es zu einem guten Kandidaten für eine Rekursion macht.
3. Tun sie!

Das kanonische Beispiel ist die Fakultät, die wie folgt aussieht:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

Im Allgemeinen ist die Rekursion nicht unbedingt schnell (der Funktionsaufruf-Overhead ist tendenziell hoch, da rekursive Funktionen tendenziell klein sind, siehe oben) und kann unter einigen Problemen leiden (jemand hat einen Stapelüberlauf?).Einige sagen, dass es in nicht trivialen Fällen schwierig sei, sie „richtig“ zu machen, aber ich glaube das nicht wirklich.In manchen Situationen ist die Rekursion am sinnvollsten und die eleganteste und klarste Art, eine bestimmte Funktion zu schreiben.Es ist zu beachten, dass einige Sprachen rekursive Lösungen bevorzugen und diese viel stärker optimieren (ich denke da an LISP).

Answer 10

Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft.Der häufigste Grund, warum ich es verwende, ist das Durchlaufen einer Baumstruktur.Wenn ich zum Beispiel eine Baumansicht mit Kontrollkästchen habe (denken Sie an die Installation eines neuen Programms, Seite „Zu installierende Funktionen auswählen“), möchte ich möglicherweise eine Schaltfläche „Alle markieren“, die etwa so aussieht (Pseudocode):

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

Sie können also sehen, dass checkRecursively zuerst den Knoten überprüft, an den es übergeben wird, und sich dann selbst für jedes untergeordnete Element dieses Knotens aufruft.

Bei der Rekursion muss man allerdings etwas vorsichtig sein.Wenn Sie in eine rekursive Endlosschleife geraten, erhalten Sie eine Stapelüberlauf-Ausnahme :)

Ich kann mir keinen Grund vorstellen, warum Leute es nicht verwenden sollten, wenn es angebracht ist.Unter bestimmten Umständen ist es nützlich, unter anderen jedoch nicht.

Da es sich um eine interessante Technik handelt, denke ich, dass manche Programmierer sie am Ende vielleicht öfter verwenden, als sie sollten, ohne wirkliche Begründung.Dies hat der Rekursion in manchen Kreisen einen schlechten Ruf eingebracht.

Answer 11

Rekursion ist ein Ausdruck, der direkt oder indirekt auf sich selbst verweist.

Betrachten Sie rekursive Akronyme als einfaches Beispiel:

• GNU steht für GNU ist kein Unix
• PHP steht für PHP:Hypertext Preprocessor
• YAML steht für YAML ist keine Auszeichnungssprache
• WEIN steht für Wein ist kein Emulator
• VISA steht für Visa International Service Association

Weitere Beispiele auf Wikipedia

Answer 12

Rekursion funktioniert am besten bei dem, was ich gerne „fraktale Probleme“ nenne, bei denen man es mit einem großen Ding zu tun hat, das aus kleineren Versionen dieses großen Dings besteht, von denen jede eine noch kleinere Version des großen Dings ist und so weiter.Wenn Sie jemals etwas wie einen Baum oder verschachtelte identische Strukturen durchqueren oder durchsuchen müssen, haben Sie ein Problem, das ein guter Kandidat für eine Rekursion sein könnte.

Menschen vermeiden eine Rekursion aus mehreren Gründen:

1. Die meisten Leute (ich eingeschlossen) haben ihre Programmierkenntnisse bei der prozeduralen oder objektorientierten Programmierung im Gegensatz zur funktionalen Programmierung erworben.Für solche Leute fühlt sich der iterative Ansatz (normalerweise mit Schleifen) natürlicher an.

2. Denjenigen von uns, die sich mit prozeduraler oder objektorientierter Programmierung auskennen, wurde oft gesagt, sie sollten die Rekursion vermeiden, weil sie fehleranfällig sei.

3. Uns wird oft gesagt, dass die Rekursion langsam ist.Das wiederholte Aufrufen und Zurückkehren aus einer Routine erfordert viel Stack-Pushing und -Popping, was langsamer ist als das Schleifen.Ich denke, einige Sprachen bewältigen dies besser als andere, und bei diesen Sprachen handelt es sich höchstwahrscheinlich nicht um diejenigen, bei denen das vorherrschende Paradigma prozedural oder objektorientiert ist.

4. Ich erinnere mich, dass ich bei mindestens einigen Programmiersprachen, die ich verwendet habe, Empfehlungen gehört habe, die Rekursion nicht zu verwenden, wenn sie eine bestimmte Tiefe überschreitet, weil der Stapel nicht so tief ist.

Answer 13

Eine rekursive Anweisung ist eine Anweisung, in der Sie den Prozess dessen, was als nächstes zu tun ist, als Kombination aus den Eingaben und dem, was Sie bereits getan haben, definieren.

Nehmen wir zum Beispiel die Fakultät:

factorial(6) = 6*5*4*3*2*1

Es ist jedoch leicht zu erkennen, dass es sich bei der Fakultät(6) auch um Folgendes handelt:

6 * factorial(5) = 6*(5*4*3*2*1).

Also allgemein:

factorial(n) = n*factorial(n-1)

Das Schwierige an der Rekursion ist natürlich, dass es einen Ausgangspunkt geben muss, wenn Sie Dinge im Hinblick auf das definieren möchten, was Sie bereits getan haben.

In diesem Beispiel machen wir einfach einen Sonderfall, indem wir „factorial(1) = 1“ definieren.

Jetzt sehen wir es von unten:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Da wir „factorial(1) = 1“ definiert haben, sind wir am „unten“ angelangt.

Im Allgemeinen bestehen rekursive Prozeduren aus zwei Teilen:

1) Der rekursive Teil, der eine Prozedur im Hinblick auf neue Eingaben definiert, kombiniert mit dem, was Sie mit derselben Prozedur „bereits getan“ haben.(d. h. factorial(n) = n*factorial(n-1))

2) Ein Basisteil, das sicherstellt, dass sich der Prozess nicht ewig wiederholt, indem es ihm einen Ausgangspunkt gibt (z. B. factorial(1) = 1)

Es kann zunächst etwas verwirrend sein, sich zurechtzufinden, aber schauen Sie sich einfach ein paar Beispiele an, dann sollte alles zusammenpassen.Wenn Sie ein viel tieferes Verständnis des Konzepts wünschen, studieren Sie die mathematische Induktion.Beachten Sie außerdem, dass einige Sprachen für rekursive Aufrufe optimiert sind, andere jedoch nicht.Es ist ziemlich einfach, wahnsinnig langsame rekursive Funktionen zu erstellen, wenn man nicht aufpasst, aber es gibt auch Techniken, um sie in den meisten Fällen leistungsfähig zu machen.

Hoffe das hilft...

Answer 14

Mir gefällt diese Definition:
Bei der Rekursion löst eine Routine einen kleinen Teil eines Problems selbst, unterteilt das Problem in kleinere Teile und ruft sich dann selbst auf, um die einzelnen kleineren Teile zu lösen.

Mir gefällt auch Steve McConnells Diskussion der Rekursion in Code Complete, wo er die Beispiele kritisiert, die in Informatikbüchern zur Rekursion verwendet werden.

Verwenden Sie keine Rekursion für Fakultäten oder Fibonacci-Zahlen

Ein Problem mit Computerwissenschaftslehrbüchern ist, dass sie alberne Beispiele für Rekursion präsentieren.Die typischen Beispiele berechnen eine Fakultät oder eine Fibonacci -Sequenz.Rekursion ist ein leistungsstarkes Werkzeug, und es ist wirklich dumm, es in einem dieser Fälle zu verwenden.Wenn ein Programmierer, der für mich arbeitete, eine Rekursion hätte, um ein Faktor zu berechnen, würde ich jemand anderen einstellen.

Ich dachte, dass dies ein sehr interessanter Punkt wäre und möglicherweise ein Grund dafür ist, dass Rekursion oft missverstanden wird.

BEARBEITEN:Das war kein Seitenhieb auf Davs Antwort – ich hatte diese Antwort noch nicht gesehen, als ich das gepostet habe

Answer 15

1.) Eine Methode ist rekursiv, wenn sie sich selbst nennen kann;entweder direkt:

void f() {
   ... f() ... 
}

oder indirekt:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Wann Rekursion verwendet werden sollte

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Rekursion wird nur verwendet, wenn es sehr komplex ist, iterativen Code zu schreiben.Beispielsweise können Baumdurchquerungstechniken wie Preorder und Postorder sowohl iterativ als auch rekursiv gestaltet werden.Aber normalerweise verwenden wir rekursiv, weil es einfach ist.

Answer 16

Hier ist ein einfaches Beispiel:wie viele Elemente in einer Menge.(Es gibt bessere Möglichkeiten, Dinge zu zählen, aber dies ist ein schönes einfaches rekursives Beispiel.)

Zunächst benötigen wir zwei Regeln:

1. Wenn die Menge leer ist, ist die Anzahl der Elemente in der Menge Null (duh!).
2. Wenn die Menge nicht leer ist, beträgt die Anzahl eins plus die Anzahl der Elemente in der Menge, nachdem ein Element entfernt wurde.

Angenommen, Sie haben ein Set wie dieses:[x x x].Zählen wir, wie viele Artikel es sind.

1. Die Menge ist [x x x], die nicht leer ist, daher wenden wir Regel 2 an.Die Anzahl der Elemente ist eins plus die Anzahl der Elemente in [x x] (d. h.wir haben einen Artikel entfernt).
2. die Menge ist [x x], also wenden wir erneut Regel 2 an:eins + Anzahl der Elemente in [x].
3. die Menge ist [x], was immer noch Regel 2 entspricht:eins + Anzahl der Elemente in [].
4. Jetzt ist die Menge [], was Regel 1 entspricht:die Zählung ist Null!
5. Nachdem wir nun die Antwort in Schritt 4 (0) kennen, können wir Schritt 3 (1 + 0) lösen.
6. Da wir nun die Antwort in Schritt 3 (1) kennen, können wir auch Schritt 2 (1 + 1) lösen.
7. Und da wir nun endlich die Antwort in Schritt 2 (2) kennen, können wir Schritt 1 (1 + 2) lösen und die Anzahl der Elemente in [x x x] erhalten, die 3 beträgt.Hurra!

Wir können dies wie folgt darstellen:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

Bei der Anwendung einer rekursiven Lösung gelten normalerweise mindestens zwei Regeln:

• die Basis, der einfache Fall, der angibt, was passiert, wenn Sie alle Ihre Daten „aufgebraucht“ haben.Dies ist normalerweise eine Variation von „Wenn Sie keine zu verarbeitenden Daten haben, lautet Ihre Antwort X.“
• die rekursive Regel, die angibt, was passiert, wenn noch Daten vorhanden sind.Dies ist normalerweise eine Art Regel, die besagt: „Machen Sie etwas, um Ihren Datensatz zu verkleinern, und wenden Sie Ihre Regeln erneut auf den kleineren Datensatz an.“

Wenn wir das Obige in Pseudocode übersetzen, erhalten wir:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

Es gibt noch viele weitere nützliche Beispiele (zum Beispiel das Überqueren eines Baumes), die sicher andere Leute behandeln werden.

Answer 17

Nun, das ist eine ziemlich gute Definition, die Sie haben.Und Wikipedia hat auch eine gute Definition.Deshalb füge ich eine weitere (wahrscheinlich schlechtere) Definition für Sie hinzu.

Wenn von „Rekursion“ die Rede ist, meinen sie normalerweise eine von ihnen geschriebene Funktion, die sich selbst wiederholt aufruft, bis sie mit ihrer Arbeit fertig ist.Rekursion kann beim Durchlaufen von Hierarchien in Datenstrukturen hilfreich sein.

Answer 18

Ein Beispiel:Eine rekursive Definition einer Treppe ist:Eine Treppe besteht aus:- Ein einzelner Schritt und eine Treppe (Rekursion) - oder nur ein einzelner Schritt (Terminierung)

Answer 19

Um auf ein gelöstes Problem zurückzugreifen:Mach nichts, du bist fertig.
Um ein offenes Problem zu rekursieren:Machen Sie den nächsten Schritt und wiederholen Sie dann den Rest.

Answer 20

In reinem Englisch:Gehen Sie davon aus, dass Sie drei Dinge tun können:

1. Nimm einen Apfel
2. Notieren Sie die Strichpunkte
3. Zählen Sie die Striche

Sie haben viele Äpfel vor sich auf einem Tisch und möchten wissen, wie viele Äpfel es sind.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Der Vorgang, bei dem dasselbe wiederholt wird, bis man fertig ist, wird Rekursion genannt.

Ich hoffe, das ist die „einfache englische“ Antwort, nach der Sie suchen!

Answer 21

Eine rekursive Funktion ist eine Funktion, die einen Aufruf an sich selbst enthält.Eine rekursive Struktur ist eine Struktur, die eine Instanz von sich selbst enthält.Sie können beide als rekursive Klasse kombinieren.Der entscheidende Teil eines rekursiven Elements besteht darin, dass es eine Instanz/einen Aufruf von sich selbst enthält.

Stellen Sie sich zwei einander zugewandte Spiegel vor.Wir haben den tollen Unendlichkeitseffekt gesehen, den sie erzeugen.Jede Reflexion ist eine Instanz eines Spiegels, die in einer anderen Instanz eines Spiegels usw. enthalten ist.Der Spiegel, der ein Spiegelbild seiner selbst enthält, ist Rekursion.

A binärer Suchbaum ist ein gutes Programmierbeispiel für Rekursion.Die Struktur ist rekursiv, wobei jeder Knoten zwei Instanzen eines Knotens enthält.Funktionen zur Arbeit an einem binären Suchbaum sind ebenfalls rekursiv.

Answer 22

Dies ist eine alte Frage, aber ich möchte eine Antwort aus logistischer Sicht hinzufügen (d. h. nicht aus Sicht der Algorithmuskorrektheit oder der Leistung).

Ich verwende Java für die Arbeit und Java unterstützt keine verschachtelten Funktionen.Wenn ich also eine Rekursion durchführen möchte, muss ich möglicherweise eine externe Funktion definieren (die nur existiert, weil mein Code gegen die bürokratischen Regeln von Java verstößt), oder ich muss den Code möglicherweise komplett umgestalten (was ich wirklich hasse).

Daher vermeide ich oft eine Rekursion und verwende stattdessen eine Stapeloperation, da die Rekursion selbst im Wesentlichen eine Stapeloperation ist.

Answer 23

Sie möchten es immer dann verwenden, wenn Sie eine Baumstruktur haben.Es ist sehr nützlich beim Lesen von XML.

Answer 24

Bei der Rekursion in der Programmierung handelt es sich grundsätzlich um den Aufruf einer Funktion aus ihrer eigenen Definition (innerhalb von sich selbst) mit unterschiedlichen Parametern, um eine Aufgabe zu erfüllen.

Answer 25

„Wenn ich einen Hammer habe, lass alles wie einen Nagel aussehen.“

Rekursion ist eine Problemlösungsstrategie für riesig Probleme, bei denen man bei jedem Schritt einfach „zwei kleine Dinge in ein größeres Ding verwandelt“, jedes Mal mit demselben Hammer.

Beispiel

Angenommen, Ihr Schreibtisch ist mit einem ungeordneten Durcheinander von 1024 Papieren bedeckt.Wie macht man mithilfe der Rekursion aus dem Durcheinander einen ordentlichen, sauberen Stapel Papier?

1. Teilen: Verteilen Sie alle Blätter so, dass Sie in jedem „Stapel“ nur ein Blatt haben.
2. Erobern:
   2. Gehen Sie herum und legen Sie jedes Blatt auf ein anderes Blatt.Sie haben jetzt 2er-Stapel.
   3. Gehen Sie herum und legen Sie jeden 2er-Stapel auf einen anderen 2er-Stapel.Sie haben jetzt 4er-Stapel.
   4. Gehen Sie herum und legen Sie jeden 4er-Stapel auf einen anderen 4er-Stapel.Sie haben jetzt Stapel von 8 Stück.
   5. ...und weiter ...
   6. Sie haben jetzt einen riesigen Stapel mit 1024 Blatt!

Beachten Sie, dass dies ziemlich intuitiv ist, abgesehen davon, dass alles gezählt wird (was nicht unbedingt notwendig ist).In Wirklichkeit werden Sie vielleicht nicht ganz auf 1-Blatt-Stapel herunterkommen, aber Sie könnten und es würde trotzdem funktionieren.Der wichtige Teil ist der Hammer:Mit Ihren Armen können Sie jederzeit einen Stapel über den anderen legen, um einen größeren Stapel zu bilden, und es spielt (im Rahmen des Zumutbaren) keine Rolle, wie groß einer der beiden Stapel ist.

Answer 26

Rekursion ist der Prozess, bei dem eine Methode aufgerufen wird, um eine bestimmte Aufgabe ausführen zu können.Es reduziert die Redundanz des Codes.Die meisten rekursiven Funktionen oder Methoden müssen eine Bedingung haben, um den rekursiven Aufruf zu unterbrechen, d. h.Verhindern Sie, dass es sich selbst aufruft, wenn eine Bedingung erfüllt ist. Dadurch wird die Erstellung einer Endlosschleife verhindert.Nicht alle Funktionen sind für die rekursive Verwendung geeignet.

Answer 27

Hey, tut mir leid, wenn meine Meinung mit jemandem übereinstimmt, ich versuche nur, die Rekursion im Klartext zu erklären.

Angenommen, Sie haben drei Manager – Jack, John und Morgan.Jack leitet zwei Programmierer, John – 3 und Morgan – 5.Sie geben jedem Manager 300 $ und möchten wissen, was das kosten würde.Die Antwort liegt auf der Hand – aber was wäre, wenn zwei von Morgans Mitarbeitern auch Manager wären?

HIER kommt die Rekursion.Sie beginnen an der Spitze der Hierarchie.Die sommerlichen Kosten betragen 0$.Sie beginnen mit Jack und überprüfen dann, ob er Manager als Mitarbeiter hat.Wenn Sie feststellen, dass dies bei einem von ihnen der Fall ist, prüfen Sie, ob dort Manager als Angestellte usw. beschäftigt sind.Fügen Sie jedes Mal, wenn Sie einen Manager finden, 300 $ zu den Sommerkosten hinzu.Wenn Sie mit Jack fertig sind, gehen Sie zu John, seinen Mitarbeitern und dann zu Morgan.

Sie werden nie wissen, wie viele Zyklen Sie durchlaufen werden, bevor Sie eine Antwort erhalten, obwohl Sie wissen, wie viele Manager Sie haben und wie viel Budget Sie ausgeben können.

Rekursion ist ein Baum mit Zweigen und Blättern, die Eltern bzw. Kinder genannt werden.Wenn Sie einen Rekursionsalgorithmus verwenden, erstellen Sie mehr oder weniger bewusst einen Baum aus den Daten.

Answer 28

Im Klartext bedeutet Rekursion, etwas immer wieder zu wiederholen.

Ein Beispiel aus der Programmierung ist der Aufruf einer Funktion in sich selbst.

Schauen Sie sich das folgende Beispiel für die Berechnung der Fakultät einer Zahl an:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Answer 29

Jeder Algorithmus weist auf strukturell Rekursion auf einen Datentyp, wenn sie im Wesentlichen aus einer Switch-Anweisung mit einem Fall für jeden Fall des Datentyps besteht.

zum Beispiel, wenn Sie an einem Typ arbeiten

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

ein struktureller rekursiver Algorithmus hätte die Form

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

Dies ist wirklich die naheliegendste Art, einen Algorithmus zu schreiben, der mit einer Datenstruktur arbeitet.

Wenn Sie sich nun die ganzen Zahlen (naja, die natürlichen Zahlen) ansehen, wie sie anhand der Peano-Axiome definiert sind

 integer = 0 | succ(integer)

Sie sehen, dass ein struktureller rekursiver Algorithmus für ganze Zahlen so aussieht

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

In der zu well bekannten faktoriellen Funktion handelt es sich um das trivialste Beispiel dieser Form.

Answer 30

Rufen Sie die Funktion selbst auf oder verwenden Sie eine eigene Definition.