it-swarm-eu.dev

Was ist Rekursion im Klartext?

Die Idee der Rekursion ist in der realen Welt nicht sehr verbreitet. Für die unerfahrenen Programmierer scheint es also etwas verwirrend. Ich denke, sie gewöhnen sich allmählich an das Konzept. Was kann eine nette Erklärung für sie sein, um die Idee leicht zu verstehen?

76
Gulshan

Um die Rekursion zu erklären, verwende ich eine Kombination verschiedener Erklärungen, normalerweise um beide zu versuchen:

  • erklären Sie das Konzept,
  • erklären, warum es wichtig ist,
  • erklären, wie man es bekommt.

Für den Anfang definiert Wolfram | Alpha es in einfacheren Begriffen als Wikipedia :

Ein Ausdruck, bei dem jeder Term durch Wiederholen einer bestimmten mathematischen Operation erzeugt wird.


Mathe

Wenn Ihr Schüler (oder die Person, die Sie auch erklären, von nun an sage ich Schüler) zumindest einen mathematischen Hintergrund hat, ist er offensichtlich bereits auf eine Rekursion gestoßen, indem er Serien studiert hat, und seine Vorstellung von Rekursivität und ihre Wiederholungsrelation .

Ein sehr guter Anfang ist es, mit einer Serie zu demonstrieren und zu sagen, dass es ganz einfach um Rekursion geht:

  • eine mathematische Funktion ...
  • ... das sich selbst aufruft, um einen Wert zu berechnen, der einem n-ten Element entspricht ...
  • ... und die einige Grenzen definiert.

Normalerweise bekommt man entweder bestenfalls ein "huh huh, was auch immer", weil sie es immer noch nicht benutzen, oder eher nur ein sehr tiefes Schnarchen.


Codierungsbeispiele

Im Übrigen handelt es sich tatsächlich um eine detaillierte Version dessen, was ich im Nachtrag von meiner Antwort für vorgestellt habe die Frage, auf die Sie bezüglich der Zeiger hingewiesen haben (schlechtes Wortspiel).

In dieser Phase wissen meine Schüler normalerweise, wie man etwas auf den Bildschirm druckt. Angenommen, wir verwenden C, wissen sie, wie man ein einzelnes Zeichen mit write oder printf druckt. Sie kennen auch Regelkreise.

Normalerweise greife ich auf ein paar sich wiederholende und einfache Programmierprobleme zurück, bis sie es bekommen:

Factorial

Factorial ist ein sehr einfach zu verstehendes mathematisches Konzept, und die Implementierung kommt seiner mathematischen Darstellung sehr nahe. Sie könnten es jedoch zunächst nicht bekommen.

Recursive Definition of the Factorial Operation

Alphabete

Die Alphabet-Version ist interessant, um ihnen beizubringen, über die Reihenfolge ihrer rekursiven Aussagen nachzudenken. Wie bei Zeigern werfen sie nur zufällig Linien auf Sie. Der Punkt ist, sie zu der Erkenntnis zu bringen, dass eine Schleife invertiert werden kann, indem entweder die Bedingungen [~ # ~] oder [~ # ~] durch geändert werden invertieren Sie einfach die Reihenfolge der Anweisungen in Ihrer Funktion. Hier hilft das Drucken des Alphabets, da es für sie etwas Visuelles ist. Lassen Sie sie einfach eine Funktion schreiben, die für jeden Aufruf ein Zeichen druckt und sich rekursiv aufruft, um das nächste (oder vorherige) zu schreiben.

FP-Fans, überspringen Sie die Tatsache, dass das Drucken von Inhalten in den Ausgabestream vorerst ein Nebeneffekt ist ... Lassen Sie uns an der FP-Front nicht zu nervig werden. (Wenn Sie jedoch eine Sprache mit Listenunterstützung verwenden, können Sie diese bei jeder Iteration mit einer Liste verknüpfen und nur das Endergebnis ausdrucken. Normalerweise beginne ich sie jedoch mit C, was für diese Art von Problemen und Konzepten leider nicht das Beste ist.) .

Potenzierung

Das Exponentiationsproblem ist etwas schwieriger ( zu diesem Zeitpunkt des Lernens). Offensichtlich ist das Konzept genau das gleiche wie für eine Fakultät und es gibt keine zusätzliche Komplexität ... außer dass Sie mehrere Parameter haben. Und das ist normalerweise genug, um die Leute zu verwirren und sie am Anfang abzuwerfen.

Seine einfache Form:

Simple Form of the Exponentiation Operation

kann durch Wiederholung so ausgedrückt werden:

Recurrence Relation for the Exponentiation Operation

Härter

Sobald diese einfachen Probleme gezeigt UND in Tutorials erneut implementiert wurden, können Sie etwas schwierigere (aber sehr klassische) Übungen geben:

Hinweis: Auch hier sind einige davon nicht wirklich schwieriger ... Sie nähern sich dem Problem nur aus genau demselben oder einem etwas anderen Blickwinkel. Aber Übung macht den Meister.


Helfer

Eine Referenz

Einiges Lesen tut nie weh. Nun, es wird zuerst und sie werden sich noch verlorener fühlen. So etwas wächst auf dir und sitzt im Hinterkopf, bis du eines Tages merkst, dass du es endlich bekommst. Und dann denkst du an diese Sachen zurück, die du gelesen hast. Die Rekursion , Rekursion in Informatik und Wiederholungsrelation Seiten auf Wikipedia würde für jetzt tun.

Level/Tiefe

Angenommen, Ihre Schüler haben nicht viel Erfahrung mit dem Codieren, stellen Sie Code-Stubs bereit. Geben Sie ihnen nach den ersten Versuchen eine Druckfunktion, mit der die Rekursionsstufe angezeigt werden kann. Das Drucken des numerischen Werts der Ebene hilft.

Das Stapel-als-Schubladen-Diagramm

Das Einrücken eines gedruckten Ergebnisses (oder der Ausgabe der Ebene) ist ebenfalls hilfreich, da es eine weitere visuelle Darstellung der Funktionsweise Ihres Programms bietet und Stapelkontexte wie Schubladen oder Ordner in einem Dateisystem-Explorer öffnet und schließt.

Rekursive Akronyme

Wenn Ihr Schüler bereits ein wenig mit Computerkultur vertraut ist, verwendet er möglicherweise bereits einige Projekte/Software mit Namen, die rekursive Akronyme verwenden. Es ist seit einiger Zeit eine Tradition, insbesondere in GNU - Projekten. Einige Beispiele sind:

Rekursiv:

  • GNU - "GNU ist nicht Unix"
  • Nagios - "Nagios wird nicht auf Heiligkeit bestehen"
  • PHP - "PHP Hypertext Preprocessor" (und ursprünglich "Personal Home Page")
  • Wein - "Wein ist kein Emulator"
  • Zile - "Zile ist verlust Emacs"

Gegenseitig rekursiv:

  • HURD - "HIRD von Unix-ersetzenden Daemons" (wobei HIRD "HURD von Schnittstellen, die die Tiefe darstellen" ist)

Lassen Sie sie versuchen, ihre eigenen zu finden.

In ähnlicher Weise gibt es viele Fälle von rekursivem Humor, wie Googles rekursive Suchkorrektur . Weitere Informationen zur Rekursion finden Sie in dieser Antwort .


Fallstricke und weiteres Lernen

Einige Probleme, mit denen Menschen normalerweise zu kämpfen haben und auf die Sie Antworten wissen müssen.

Warum, oh Gott, warum ???

Warum würdest du das tun? Ein guter, aber nicht offensichtlicher Grund ist, dass es oft einfacher ist, ein Problem auf diese Weise auszudrücken. Ein nicht so guter, aber offensichtlicher Grund ist, dass es oft weniger Eingabe erfordert (lassen Sie sie sich nicht soooo fühlen, wenn sie nur Rekursion verwenden ...).

Einige Probleme sind definitiv einfacher zu lösen, wenn ein rekursiver Ansatz verwendet wird. Normalerweise passt jedes Problem, das Sie mit einem Divide and Conquer -Paradigma lösen können, zu einem mehrfach verzweigten Rekursionsalgorithmus.

Was ist wieder N?

Warum ist mein n oder (wie auch immer der Name Ihrer Variablen lautet) jedes Mal anders? Anfänger haben normalerweise ein Problem damit, zu verstehen, was eine Variable und ein Parameter sind und wie Dinge mit dem Namen n in Ihrem Programm unterschiedliche Werte haben können. Wenn sich dieser Wert nun im Regelkreis oder in der Rekursion befindet, ist das noch schlimmer! Seien Sie nett und verwenden Sie nicht überall dieselben Variablennamen und machen Sie deutlich, dass Parameter nur Variablen sind .

Endbedingungen

Wie bestimme ich meinen Endzustand? Das ist einfach, lassen Sie sie einfach die Schritte laut aussprechen. Zum Beispiel für den Fakultätsstart von 5, dann 4, dann ... bis 0.

Der Teufel steckt im Detail

Sprechen Sie nicht mit frühen Dingen wie Tail Call Optimization . Ich weiß, ich weiß, TCO ist nett, aber es ist ihnen zunächst egal. Geben Sie ihnen etwas Zeit, um ihre Köpfe so um den Prozess zu wickeln, wie es für sie funktioniert. Fühlen Sie sich frei, ihre Welt später wieder zu zerstören, aber geben Sie ihnen eine Pause.

Sprechen Sie auch nicht direkt aus der ersten Vorlesung über den Aufrufstapel und seinen Speicherverbrauch und ... nun ... den Stapelüberlauf . Ich unterrichte Schüler oft privat, die mir Vorlesungen zeigen, in denen sie 50 Folien über alles haben. Es gibt etwas über Rekursion zu wissen, wenn sie zu diesem Zeitpunkt kaum eine Schleife richtig schreiben können. Das ist ein gutes Beispiel dafür, wie eine Referenz helfen wird später aber im Moment nur verwirrt Sie zutiefst.

Bitte machen Sie jedoch zu gegebener Zeit klar, dass es Gründe gibt, den iterativen oder rekursiven Weg zu gehen .

Gegenseitige Rekursion

Wir haben gesehen, dass Funktionen rekursiv sein können und sogar mehrere Call Points haben können (8-Königinnen, Hanoi, Fibonacci oder sogar ein Explorationsalgorithmus für einen Minensuchboot). Aber was ist mit gegenseitig rekursiven Aufrufen ? Beginnen Sie auch hier mit Mathematik. f(x) = g(x) + h(x) wobei g(x) = f(x) + l(x) und h und l einfach Sachen machen.

Das Beginnen mit nur mathematischen Reihen erleichtert das Schreiben und Implementieren, da der Vertrag durch die Ausdrücke klar definiert ist. Zum Beispiel die Hofstadter-Sequenzen für Frauen und Männer :

Hofstadter's Male and Female Sequences

In Bezug auf Code ist jedoch zu beachten, dass die Implementierung einer gegenseitig rekursiven Lösung häufig zu einer Codeduplizierung führt und eher in eine einzige rekursive Form optimiert werden sollte (siehe Peter Norvig 's Lösen jedes Sudoku-Puzzles .

111
haylem

Das Aufrufen einer Funktion aus derselben Funktion heraus.

59
ChaosPandion

Rekursion ist eine Funktion, die sich selbst aufruft.

Es ist wichtig zu wissen, wie man es benutzt, wann man es benutzt und wie man schlechtes Design vermeidet. Dazu muss man es selbst ausprobieren und verstehen, was passiert.

Das Wichtigste, was Sie wissen müssen, ist, sehr vorsichtig zu sein, um keine Schleife zu erhalten, die niemals endet. Die Antwort von pramodc84 auf Ihre Frage hat diesen Fehler: Es endet nie ...
Eine rekursive Funktion muss immer nach einer Bedingung suchen, um festzustellen, ob sie sich erneut aufrufen soll oder nicht.

Das klassischste Beispiel für die Verwendung der Rekursion ist die Arbeit mit einem Baum ohne statische Tiefenbeschränkungen. Dies ist eine Aufgabe, die Sie mit Rekursion ausführen müssen.

27
awe

Rekursive Programmierung ist der Prozess, bei dem ein Problem schrittweise reduziert wird, um Versionen von sich selbst leichter zu lösen.

Jede rekursive Funktion neigt dazu:

  1. nehmen Sie eine zu verarbeitende Liste oder eine andere Struktur oder Problemdomäne
  2. beschäftige dich mit dem aktuellen Punkt/Schritt
  3. rufen Sie sich auf den Rest (en)/Subdomain (s) auf
  4. kombinieren oder verwenden Sie die Ergebnisse der Subdomain-Arbeit

Wenn Schritt 2 vor 3 liegt und wenn Schritt 4 trivial ist (eine Verkettung, Summe oder nichts), wird Schwanzrekursion aktiviert. Schritt 2 muss häufig nach Schritt 3 erfolgen, da die Ergebnisse der Unterdomäne (n) des Problems möglicherweise erforderlich sind, um den aktuellen Schritt abzuschließen.

Nehmen Sie die Durchquerung eines geradlinigen Binärbaums. Die Durchquerung kann je nach Bedarf in Vorbestellung, Reihenfolge oder Nachbestellung erfolgen.

   B
A     C

Vorbestellung: B A C

traverse(tree):
    visit the node
    traverse(left)
    traverse(right)

In der Reihenfolge: A B C

traverse(tree):
    traverse(left)
    visit the node
    traverse(right)

Nachbestellung: A C B

traverse(tree):
    traverse(left)
    traverse(right)
    visit the node

Sehr viele rekursive Probleme sind spezifische Fälle einer map -Operation oder einer fold - das Verstehen nur dieser beiden Operationen kann zu einem signifikanten Verständnis guter Anwendungsfälle für die Rekursion führen.

21
Orbling

Das OP sagte, dass es in der realen Welt keine Rekursion gibt, aber ich bin anderer Meinung.

Nehmen wir die reale Operation, eine Pizza zu zerschneiden. Sie haben die Pizza aus dem Ofen genommen und um sie zu servieren, müssen Sie sie halbieren, dann die Hälften halbieren und die resultierenden Hälften erneut halbieren.

Der Vorgang des Schneidens der Pizza, die Sie immer wieder ausführen, bis Sie das gewünschte Ergebnis erhalten (die Anzahl der Scheiben). Und aus Gründen der Argumentation sagen wir, dass eine ungeschnittene Pizza selbst ein Stück ist.

Hier ist ein Beispiel in Ruby:

 def cut_pizza (vorhandene_Slices, gewünschte_Slices) 
 Wenn vorhandene_Slices! = gewünschte_Slices 
 # Wir haben noch nicht genug Slices, um alle zu füttern, also 
 # sind wir Schneiden Sie die Pizzastücke und verdoppeln Sie so ihre Anzahl 
 new_slices = existierende_Slices * 2 
 # .____.] # Wir haben die gewünschte Anzahl von Slices, also geben wir 
 # hierher zurück, anstatt weiter 
 zu rekursieren. Geben Sie vorhandene_Slices zurück. 
 Ende 
 Ende 
 
 pizza = 1 # eine ganze Pizza, 'ein Stück' 
 cut_pizza (Pizza, 8) # => wir bekommen 8 

Die Operation in der realen Welt schneidet also eine Pizza, und die Rekursion macht immer wieder dasselbe, bis Sie das haben, was Sie wollen.

Zu den Operationen, die Sie mit rekursiven Funktionen implementieren können, gehören:

  • Berechnung des Zinseszinses über mehrere Monate.
  • Suchen nach einer Datei in einem Dateisystem (da Dateisysteme aufgrund von Verzeichnissen Bäume sind).
  • Alles, was mit der Arbeit mit Bäumen im Allgemeinen zu tun hat, denke ich.

Ich empfehle, ein Programm zu schreiben, um anhand des Dateinamens nach einer Datei zu suchen, und zu versuchen, eine Funktion zu schreiben, die sich selbst aufruft, bis sie gefunden wird. Die Signatur würde folgendermaßen aussehen:

find_file_by_name(file_name_we_are_looking_for, path_to_look_in)

Man könnte es also so nennen:

find_file_by_name('httpd.conf', '/etc') # damn it i can never find Apache's conf

Meiner Meinung nach ist es einfach Programmiermechanik, eine Möglichkeit, Duplikate geschickt zu entfernen. Sie können dies mithilfe von Variablen umschreiben, dies ist jedoch eine "schönere" Lösung. Es ist nichts Geheimnisvolles oder Schwieriges daran. Sie werden ein paar rekursive Funktionen schreiben, es wird klicken und huzzah einen weiteren mechanischen Trick in Ihrer Programmier-Toolbox.

Extra Credit Das cut_pizza Das obige Beispiel gibt Ihnen einen zu tiefen Fehler auf Stapelebene, wenn Sie nach einer Anzahl von Slices fragen, die keine Potenz von 2 sind (d. h. 2 oder 4 oder 8 oder 16). Können Sie es so ändern, dass es nicht für immer ausgeführt wird, wenn jemand nach 10 Slices fragt?

20
Ryan Allen

Okay, ich werde versuchen, dies einfach und prägnant zu halten.

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen. Die rekursive Funktion besteht aus drei Dingen:

  1. Logik
  2. Ein Anruf für sich
  3. Wann zu beenden.

Die beste Möglichkeit, rekursive Methoden zu schreiben, besteht darin, sich die Methode, die Sie schreiben möchten, als einfaches Beispiel vorzustellen, das nur eine Schleife des Prozesses behandelt, über den Sie iterieren möchten. Fügen Sie dann den Aufruf der Methode selbst hinzu und fügen Sie ihn hinzu, wenn Sie möchten beenden. Der beste Weg zu lernen ist, wie alle Dinge zu üben.

Da dies eine Programmierer-Website ist, werde ich keinen Code schreiben, aber hier ist ein guter Link

wenn du diesen Witz hast, hast du verstanden, was Rekursion bedeutet.

16
dustyprogrammer

Rekursion ist ein Werkzeug, mit dem ein Programmierer einen Funktionsaufruf für sich selbst aufrufen kann. Die Fibonacci-Sequenz ist das Lehrbuchbeispiel für die Verwendung der Rekursion.

Der meiste rekursive Code, wenn nicht alle, kann als iterative Funktion ausgedrückt werden, ist aber normalerweise chaotisch. Gute Beispiele für andere rekursive Programme sind Datenstrukturen wie Bäume, binärer Suchbaum und sogar Quicksort.

Die Rekursion wird verwendet, um den Code weniger schlampig zu machen. Beachten Sie jedoch, dass er normalerweise langsamer ist und mehr Speicher benötigt.

6

Ich benutze dieses gerne:

Wie gehst du zum Laden?

Wenn Sie am Eingang des Ladens sind, gehen Sie einfach durch. Andernfalls machen Sie einen Schritt und gehen Sie dann den Rest des Weges zum Geschäft.

Es ist wichtig, drei Aspekte zu berücksichtigen:

  • Ein trivialer Basisfall
  • Ein kleines Stück des Problems lösen
  • Den Rest des Problems rekursiv lösen

Tatsächlich verwenden wir im täglichen Leben häufig Rekursionen. wir sehen das einfach nicht so.

5
Barry Brown

Das beste Beispiel, auf das ich Sie hinweisen möchte, ist C Programming Language von K & R. In diesem Buch (und ich zitiere aus dem Speicher) listet der Eintrag auf der Indexseite für die Rekursion (allein) die tatsächliche Seite auf, auf der über Rekursion und Rekursion gesprochen wird auch die Indexseite.

3
Kanini

Josh K erwähnte bereits die Matroshka Puppen. Angenommen, Sie möchten etwas lernen, das nur die kürzeste Puppe kennt. Das Problem ist, dass man nicht direkt mit ihr sprechen kann, weil sie ursprünglich lebt innen die größere Puppe, die auf dem ersten Bild links von ihr platziert ist. Diese Struktur geht so (eine Puppe lebt in der größeren Puppe), bis sie nur noch die höchste ist.

Sie können also nur Ihre Frage an die größte Puppe stellen. Die größte Puppe (die die Antwort nicht kennt) muss Ihre Frage an die kürzere Puppe weitergeben (die sich auf dem ersten Bild rechts von ihr befindet). Da sie auch keine Antwort hat, muss sie die nächste kürzere Puppe fragen. Dies wird so weitergehen, bis die Nachricht die kürzeste Puppe erreicht. Die kürzeste Puppe (die als einzige die geheime Antwort kennt) gibt die Antwort an die nächsthöhere Puppe weiter (links von ihr), die sie an die nächsthöhere Puppe weitergibt ... und dies wird bis zur Antwort fortgesetzt erreicht sein endgültiges Ziel, das die höchste Puppe ist und schließlich ... du :)

Das macht Rekursion wirklich. Eine Funktion/Methode ruft sich selbst auf, bis die erwartete Antwort erhalten wird. Deshalb ist es beim Schreiben von rekursivem Code sehr wichtig zu entscheiden, wann die Rekursion beendet werden soll.

Nicht die beste Erklärung, aber es hilft hoffentlich.

2
sakisk

Rekursion n. - Ein Muster des Algorithmusdesigns, bei dem eine Operation in Bezug auf sich selbst definiert wird.

Das klassische Beispiel ist das Finden der Fakultät einer Zahl, n!. 0! = 1, und für jede andere natürliche Zahl N ist die Fakultät von N das Produkt aller natürlichen Zahlen kleiner oder gleich N. Also 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720. Mit dieser grundlegenden Definition können Sie eine einfache iterative Lösung erstellen:

int Fact(int degree)
{
    int result = 1;
    for(int i=degree; i>1; i--)
       result *= i;

    return result;
}

Überprüfen Sie den Vorgang jedoch erneut. 6! = 6 * 5 * 4 * 3 * 2 * 1. Nach der gleichen Definition ist 5! = 5 * 4 * 3 * 2 * 1, was bedeutet, dass wir 6 sagen können! = 6 * (5!). Im Gegenzug 5! = 5 * (4!) Und so weiter. Auf diese Weise reduzieren wir das Problem auf eine Operation, die für das Ergebnis aller vorherigen Operationen ausgeführt wird. Dies reduziert sich schließlich auf einen Punkt, der als Basisfall bezeichnet wird und bei dem das Ergebnis per Definition bekannt ist. In unserem Fall ist 0! = 1 (wir könnten in den meisten Fällen auch sagen, dass 1! = 1). Beim Rechnen können wir Algorithmen häufig auf sehr ähnliche Weise definieren, indem wir die Methode selbst aufrufen und eine kleinere Eingabe übergeben, wodurch das Problem durch viele Rekursionen auf einen Basisfall reduziert wird:

int Fact(int degree)
{
    if(degree==0) return 1; //the base case; 0! = 1 by definition
    else return degree * Fact(degree -1); //the recursive case; N! = N*(N-1)!
}

Dies kann in vielen Sprachen mithilfe des ternären Operators weiter vereinfacht werden (manchmal als Iif-Funktion in Sprachen angesehen, die den Operator nicht als solchen bereitstellen):

int Fact(int degree)
{
    //reads equivalently to the above, but is concise and often optimizable
    return degree==0 ? 1: degree * Fact(degree -1);
}

Vorteile:

  • Natürlicher Ausdruck - Für viele Arten von Algorithmen ist dies eine sehr natürliche Art, die Funktion auszudrücken.
  • Reduzierter LOC - Es ist oft viel prägnanter, eine Funktion rekursiv zu definieren.
  • Geschwindigkeit - In bestimmten Fällen ist die Rekursion eines Algorithmus je nach Sprache und Computerarchitektur schneller als die entsprechende iterative Lösung. In der Regel ist das Ausführen eines Funktionsaufrufs auf Hardwareebene eine schnellere Operation als die Operationen und der Speicherzugriff, die für eine iterative Schleife erforderlich sind.
  • Teilbarkeit - Viele rekursive Algorithmen haben die Mentalität "Teilen und Erobern". Das Ergebnis der Operation ist eine Funktion des Ergebnisses derselben Operation, die an jeder der beiden Hälften der Eingabe ausgeführt wird. Auf diese Weise können Sie die Arbeit auf jeder Ebene in zwei Teile teilen und, falls verfügbar, die andere Hälfte einer anderen "Ausführungseinheit" zur Verarbeitung geben. Dies ist mit einem iterativen Algorithmus normalerweise schwieriger oder unmöglich.

Nachteile:

  • Erfordert Verständnis - Sie müssen einfach das Konzept der Rekursion "verstehen", um zu verstehen, was vor sich geht, und daher effektive rekursive Algorithmen schreiben und beibehalten. Ansonsten sieht es nur nach schwarzer Magie aus.
  • Kontextabhängig - Ob Rekursion eine gute Idee ist oder nicht, hängt davon ab, wie elegant der Algorithmus in Bezug auf sich selbst definiert werden kann. Während es beispielsweise möglich ist, eine rekursive SelectionSort zu erstellen, ist der iterative Algorithmus in der Regel verständlicher.
  • Trades RAM Zugriff für den Aufrufstapel - In der Regel sind Funktionsaufrufe billiger als der Cache-Zugriff, wodurch die Rekursion schneller als die Iteration erfolgen kann. In der Regel ist jedoch die Tiefe des Aufrufstapels begrenzt, die dazu führen kann Rekursion zum Fehler, wenn ein iterativer Algorithmus funktioniert.
  • Unendliche Rekursion - Sie müssen wissen, wann Sie aufhören müssen. Eine unendliche Iteration ist ebenfalls möglich, aber die beteiligten Schleifenkonstrukte sind normalerweise leichter zu verstehen und somit zu debuggen.
2
KeithS

Das Beispiel, das ich benutze, ist ein Problem, mit dem ich im wirklichen Leben konfrontiert war. Sie haben einen Container (z. B. einen großen Rucksack, den Sie mitnehmen möchten) und möchten das Gesamtgewicht wissen. Sie haben zwei oder drei lose Gegenstände im Behälter und einige andere Behälter (z. B. Packsäcke). Das Gewicht des Gesamtbehälters ist offensichtlich das Gewicht des leeren Behälters plus das Gewicht von allem darin. Für die losen Gegenstände können Sie sie einfach wiegen, und für die Packsäcke können Sie sie einfach wiegen oder Sie können sagen "Nun, das Gewicht jedes Packsacks ist das Gewicht des leeren Behälters plus das Gewicht von allem darin". Und dann gehen Sie weiter in Container in Container und so weiter, bis Sie zu einem Punkt kommen, an dem sich nur noch lose Gegenstände in einem Container befinden. Das ist Rekursion.

Sie mögen denken, dass dies im wirklichen Leben niemals passiert, aber stellen Sie sich vor, Sie würden versuchen, die Gehälter von Personen in einem bestimmten Unternehmen oder einer bestimmten Abteilung zu zählen oder zu addieren, die eine Mischung aus Personen haben, die nur für das Unternehmen arbeiten, Personen in Abteilungen, dann in Die Abteilungen dort sind Abteilungen und so weiter. Oder Verkäufe in einem Land mit Regionen, von denen einige Unterregionen usw. usw. haben. Diese Art von Problemen tritt im Geschäftsleben ständig auf.

1
Kate Gregory

Rekursion kann verwendet werden, um viele Zählprobleme zu lösen. Angenommen, Sie haben eine Gruppe von n Personen auf einer Party (n> 1), und jeder schüttelt allen anderen genau einmal die Hand. Wie viele Handshakes finden statt? Sie wissen vielleicht, dass die Lösung C (n, 2) = n (n-1)/2 ist, aber Sie können rekursiv wie folgt lösen:

Angenommen, es gibt nur zwei Personen. Dann (durch Inspektion) ist die Antwort offensichtlich 1.

Angenommen, Sie haben drei Personen. Wählen Sie eine Person aus und beachten Sie, dass sie zwei anderen Personen die Hand gibt. Danach müssen Sie nur noch die Handshakes zwischen den beiden anderen Personen zählen. Das haben wir gerade erst gemacht und es ist 1. Die Antwort lautet also 2 + 1 = 3.

Angenommen, Sie haben n Leute. Nach der gleichen Logik wie zuvor ist es (n-1) + (Anzahl der Handshakes zwischen n-1 Personen). Wenn wir uns erweitern, erhalten wir (n-1) + (n-2) + ... + 1.

Als rekursive Funktion ausgedrückt,

f (2) = 1
f (n) = n-1 + f (n-1), n> 2

0
Mitch Schwartz

Hier ist ein Beispiel aus der Praxis für die Rekursion.

Lassen Sie sie sich vorstellen, dass sie eine Comic-Sammlung haben und Sie alles zu einem großen Haufen vermischen werden. Vorsicht - wenn sie wirklich eine Sammlung haben, können sie Sie sofort töten, wenn Sie nur die Idee dazu erwähnen.

Lassen Sie sie nun diesen großen, unsortierten Stapel Comics mithilfe dieses Handbuchs sortieren:

Manual: How to sort a pile of comics

Check the pile if it is already sorted. If it is, then done.

As long as there are comics in the pile, put each one on another pile, 
ordered from left to right in ascending order:

    If your current pile contains different comics, pile them by comic.
    If not and your current pile contains different years, pile them by year.
    If not and your current pile contains different tenth digits, pile them 
    by this digit: Issue 1 to 9, 10 to 19, and so on.
    If not then "pile" them by issue number.

Refer to the "Manual: How to sort a pile of comics" to separately sort each
of the new piles.

Collect the piles back to a big pile from left to right.

Done.

Das Schöne hier ist: Wenn es um einzelne Probleme geht, haben sie den vollen "Stapelrahmen" mit den lokalen Haufen, die vor ihnen auf dem Boden sichtbar sind. Geben Sie ihnen mehrere Ausdrucke des Handbuchs und legen Sie einen beiseite auf jede Stapelebene mit einer Markierung, an der Sie sich gerade auf dieser Ebene befinden (dh dem Status der lokalen Variablen), damit Sie dort bei jedem Fertigfahren fortfahren können.

Das ist es, worum es bei der Rekursion im Grunde geht: Den gleichen Prozess ausführen, nur auf einer feineren Detailebene, je mehr Sie sich damit beschäftigen.

0
Secure

Im Leben (im Gegensatz zu einem Computerprogramm) tritt Rekursion selten unter unserer direkten Kontrolle auf, da es verwirrend sein kann, dies zu erreichen. Außerdem geht es bei der Wahrnehmung eher um die Nebenwirkungen als um funktionale Reinheit. Wenn also eine Rekursion auftritt, werden Sie dies möglicherweise nicht bemerken.

Hier draußen auf der Welt kommt es jedoch zu Rekursionen. Viel.

Ein gutes Beispiel ist (eine vereinfachte Version von) der Wasserkreislauf:

  • Die Sonne heizt den See
  • Das Wasser steigt in den Himmel und bildet Wolken
  • Die Wolken ziehen zu einem Berg
  • Am Berg wird die Luft zu kalt, als dass ihre Feuchtigkeit zurückgehalten werden könnte
  • Regen fällt
  • Ein Fluss bildet sich
  • Das Wasser im Fluss fließt in den See

Dies ist ein Zyklus, der bewirkt, dass sein Selbst wieder vorkommt. Es ist rekursiv.

Ein weiterer Ort, an dem Sie eine Rekursion erhalten können, ist Englisch (und die menschliche Sprache im Allgemeinen). Sie werden es vielleicht zuerst nicht erkennen, aber die Art und Weise, wie wir einen Satz erzeugen können, ist rekursiv, da die Regeln es uns ermöglichen, eine Instanz eines Symbols neben einer anderen Instanz desselben Symbols einzubetten.

Aus Steven Pinkers The Language Instinct:

wenn entweder das Mädchen Eis isst oder das Mädchen Süßigkeiten isst, dann isst der Junge Hot Dogs

Das ist ein ganzer Satz, der andere ganze Sätze enthält:

das Mädchen isst Eis

das Mädchen isst Süßigkeiten

der Junge isst Hot Dogs

Das Verstehen des vollständigen Satzes beinhaltet das Verstehen kleinerer Sätze, die die gleichen mentalen Tricks anwenden, um als vollständiger Satz verstanden zu werden.

Um die Rekursion aus Programmiersicht zu verstehen, ist es am einfachsten, ein Problem zu betrachten, das mit der Rekursion gelöst werden kann, und zu verstehen, warum dies der Fall sein sollte und was dies bedeutet, dass Sie dies tun müssen.

Für das Beispiel werde ich die größte gemeinsame Teilerfunktion verwenden, kurz gcd.

Sie haben Ihre beiden Zahlen a und b. Um ihre gcd zu finden (vorausgesetzt, keine ist 0), müssen Sie überprüfen, ob a gleichmäßig in b teilbar ist. Wenn dies der Fall ist, ist b die gcd, andernfalls müssen Sie nach der gcd von b und dem Rest von a/b Prüfen.

Sie sollten bereits erkennen können, dass dies eine rekursive Funktion ist, da die Funktion gcd die Funktion gcd aufruft. Nur um es nach Hause zu hämmern, hier ist es in c # (wieder unter der Annahme, dass 0 nie als Parameter übergeben wird):

int gcd(int a, int b)
{   
    if (a % b == 0) //this is a stopping condition
    {
        return b;
    }

    return (gcd(b, a % b)); //the call to gcd here makes this function recursive
}

In einem Programm ist es wichtig, eine Stoppbedingung zu haben, da sonst Ihre Funktion für immer wieder auftritt, was schließlich zu einem Stapelüberlauf führen kann!

Der Grund für die Verwendung der Rekursion anstelle einer while-Schleife oder eines anderen iterativen Konstrukts besteht darin, dass Sie beim Lesen des Codes erfahren, was er tut und was als Nächstes passieren wird, sodass Sie leichter herausfinden können, ob er ordnungsgemäß funktioniert .

0
Matt Ellen