Was ist Rekursion im Klartext?

74

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

Gulshan
quelle
Weitere Informationen zu diesem Thema finden Sie unter Ressourcen, um Ihr Verständnis von Rekursion zu verbessern.
Kenneth
1
Rekursion ist, wenn eine Funktion sich selbst aufrufen kann. "Wenn Sie Namespaces und den Gültigkeitsbereich vollständig verstehen und wissen, wie Parameter an eine Funktion übergeben werden, kennen Sie die Rekursion bereits. Ich kann Beispiele zeigen, aber Sie sollten in der Lage sein, selbst herauszufinden, wie sie funktionieren." Die Schüler haben im Allgemeinen weniger Probleme mit der Rekursion, weil sie verwirrend sind, aber weil sie den variablen Bereich / Namespace nicht genau verstehen. Stellen Sie vor dem Eintauchen in die Rekursion sicher, dass die Schüler ein Programm ordnungsgemäß nachverfolgen können, in dem Sie Variablen in verschiedenen Bereichen absichtlich den gleichen Namen gegeben haben, um sie zu verwirren.
Dspyz
1
Um die Rekursion zu verstehen, müssen Sie zuerst die Rekursion verstehen
Goerman

Antworten:

110

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

  • das Konzept erklären,
  • erklären, warum es wichtig ist,
  • Erklären Sie, wie Sie es bekommen.

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 generiert wird.


Mathe

Wenn Ihr Schüler (oder die Person, die Sie erklären, von nun an Student) zumindest einen mathematischen Hintergrund hat, sind sie offensichtlich bereits auf eine Rekursion gestoßen, indem sie Serien studierten, und auf ihre Vorstellung von Rekursivität und ihre Wiederholungsrelation .

Ein sehr guter Anfang ist es dann, mit einer Serie zu demonstrieren und zu sagen, dass es ganz einfach darum geht, worum es bei der Rekursion geht:

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

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


Codierungsbeispiele

Im übrigen ist es tatsächlich eine detaillierte Version von dem, was ich im vorliegenden Addendum von meiner Antwort für die Frage , die Sie in Bezug auf Hinweise darauf (schlechtes Wortspiel).

Zu diesem Zeitpunkt wissen meine Schüler normalerweise, wie man etwas auf dem Bildschirm druckt. Angenommen, wir verwenden C, wissen sie, wie man ein einzelnes Zeichen mit writeoder druckt printf. Sie kennen sich auch mit Regelkreisen aus.

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

Fakultät

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.

Rekursive Definition der faktoriellen Operation

Alphabete

Die alphabetische Version ist interessant, um sie zu lehren, über die Reihenfolge ihrer rekursiven Anweisungen nachzudenken. Wie bei Zeigern werden Sie nur zufällig mit Linien beworfen. Der Punkt ist, sie zu der Erkenntnis zu bringen, dass eine Schleife invertiert werden kann, indem entweder die Bedingungen modifiziert werden ODER indem einfach die Reihenfolge der Anweisungen in Ihrer Funktion invertiert wird. 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 selbst rekursiv aufruft, um das nächste (oder vorherige) Zeichen zu schreiben.

FP-Fans, überspringen Sie die Tatsache, dass das Drucken von Inhalten in den Ausgabestream vorerst ein Nebeneffekt ist. (Wenn Sie jedoch eine Sprache mit Listenunterstützung verwenden, können Sie sie bei jeder Iteration zu einer Liste verketten 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 ( in dieser Lernphase). 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 wegzuwerfen.

Seine einfache Form:

Einfache Form der Exponentiationsoperation

kann wie folgt ausgedrückt werden:

Wiederholungsrelation für die Exponentiationsoperation

Schwerer

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

Hinweis: Wiederum sind einige davon nicht wirklich schwieriger ... Sie nähern sich dem Problem nur aus genau dem gleichen oder einem etwas anderen Winkel. Übung macht den Meister.


Helfer

Eine Referenz

Ein bisschen Lesen tut nie weh. Nun, das wird es zuerst und sie werden sich noch verlorener fühlen. So etwas wächst auf dir und sitzt in deinem Hinterkopf, bis dir eines Tages klar wird, dass du es endlich kapierst. Und dann denkst du an diese Sachen zurück, die du gelesen hast. Die Rekursion , Rekursion in der Informatik und Rekursionsbeziehungsseiten auf Wikipedia würden vorerst genügen.

Niveau / Tiefe

Unter der Annahme, dass Ihre Schüler nicht viel Erfahrung mit dem Programmieren haben, sollten Sie Code-Stubs bereitstellen. 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 Stack-as-Drawers-Diagramm

Das Einrücken eines gedruckten Ergebnisses (oder der Ausgabe der Ebene) ist ebenfalls hilfreich, da es eine weitere visuelle Darstellung der Aktionen Ihres Programms gibt 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 eine Tradition, die schon seit einiger Zeit besteht, 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 verlustreicher Emacs"

Gegenseitig rekursiv:

  • HURD - "HIRD of Unix-Replacing Daemons" (wobei HIRD "HURD of Interfaces" für Depth steht)

Lassen Sie sie versuchen, ihre eigenen zu finden.

Ebenso gibt es viele Fälle von rekursivem Humor, wie beispielsweise die rekursive Suchkorrektur von Google . Weitere Informationen zur Rekursion finden Sie in dieser Antwort .


Fallstricke und weiteres Lernen

Einige Probleme, mit denen Menschen normalerweise zu kämpfen haben und für 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 Tipparbeit erfordert (lassen Sie sie sich nicht soooo fühlen, wenn Sie nur die Rekursion verwenden ...).

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

Was ist N nochmal?

Warum ist mein noder (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 die nin Ihrem Programm genannten Dinge unterschiedliche Werte haben können. Wenn sich dieser Wert also im Regelkreis oder in der Rekursion befindet, ist das noch schlimmer! Seien Sie nett und verwenden Sie nicht überall dieselben Variablennamen. Machen Sie deutlich, dass Parameter nur Variablen sind .

Endebedingungen

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

Der Teufel steckt im Detail

Sprechen Sie nicht zu früh über Dinge wie die Optimierung von Tail Calls . Ich weiß, ich weiß, TCO ist nett, aber es interessiert sie zuerst nicht. Geben Sie ihnen etwas Zeit, um den Prozess so zu gestalten, 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 in ähnlicher Weise nicht direkt von der ersten Vorlesung an über den Aufrufstapel und seinen Speicherverbrauch und ... nun ... den Stapelüberlauf . Ich unterrichte oft Privatschüler, die mir Vorlesungen zeigen, in denen sie 50 Folien über alles haben, was man über Rekursion wissen muss, wenn sie zu diesem Zeitpunkt kaum eine Schleife richtig schreiben können. Das ist ein gutes Beispiel dafür , wie eine Referenz helfen später aber im Moment nur verwirrt Sie tief.

Machen Sie aber bitte rechtzeitig 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 Aufrufpunkte haben können (8-Königinnen, Hanoi, Fibonacci oder sogar ein Erkundungsalgorithmus für einen Minensucher). Aber was ist mit gegenseitig rekursiven Aufrufen ? Beginnen Sie auch hier mit Mathe. f(x) = g(x) + h(x)wo g(x) = f(x) + l(x)und hund lnur 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 weiblichen und männlichen Sequenzen :

Hofstädters männliche und weibliche Sequenzen

Jedoch in Bezug auf Code, es zu beachten ist , dass die Umsetzung einer für beide Seiten rekursive Lösung häufig Doppelarbeit zu codieren führt und sollte eher in eine einzige rekursive Form rationalisiert werden (siehe Peter Norvig ‚s Solving Jedes Sudoku Puzzle .

14 Umdrehungen
quelle
5
Ich lese Ihre Antwort, nachdem ich sie fast zum 5. oder 6. Mal gesehen habe. Es war schön, aber zu lang, um andere Benutzer hierher zu locken, denke ich. Ich habe hier viel über das Unterrichten von Rekursion gelernt. Als Lehrer, würden Sie bitte meine Idee für den Unterricht recursion- bewerten programmers.stackexchange.com/questions/25052/...
Gulshan
9
@ Gulshan, ich denke, diese Antwort ist ungefähr so ​​umfassend wie jede andere und wird von einem Gelegenheitsleser leicht überflogen. Daher bekommt es eine static unsigned int vote = 1;von mir. Verzeihen Sie den statischen Humor, wenn Sie wollen :) Dies ist die bisher beste Antwort.
Tim Post
1
@Gulsan: Nur wer lernen will, ist bereit, sich die Zeit dafür zu nehmen, ist richtig :) Es macht mir nichts aus. Manchmal ist eine kurze Antwort elegant und vermittelt viele nützliche und notwendige Informationen, um zu beginnen oder ein allgemeines Konzept zu erklären. Ich wollte nur eine längere Antwort auf diese Frage, und da das OP eine Frage erwähnt, für die ich die "richtige" Antwort erhalten habe und eine ähnliche Frage stelle, hielt ich es für angebracht, dieselbe Antwort zu geben. Ich bin froh, dass du etwas gelernt hast.
Haylem
@ Gulshan: Nun zu deiner Antwort: Der erste Punkt hat mich sehr verwirrt, muss ich sagen. Ich finde es gut, dass Sie das Konzept der rekursiven Funktionen als etwas bezeichnen, das den Zustand im Laufe der Zeit schrittweise ändert, aber ich finde, dass Ihre Art der Darstellung etwas seltsam ist. Nachdem ich Ihre 3 Punkte gelesen habe, würde ich nicht erwarten, dass viele Schüler plötzlich in der Lage sind, Hanoi zu lösen. Aber es könnte nur eine Formulierung sein.
Haylem
Ich habe eine gute Möglichkeit gefunden zu zeigen, dass dieselbe Variable in unterschiedlichen Rekursionstiefen unterschiedliche Werte haben kann: Lassen Sie die Schüler die Schritte, die sie ausführen, und die Werte der Variablen aufschreiben, indem sie einem rekursiven Code folgen. Wenn sie eine Rekursion erreichen, lassen Sie sie erneut mit einem neuen Stück beginnen. Sobald sie eine Ausgangsbedingung erreicht haben, lassen Sie sie zum vorherigen Teil zurückkehren. Dies emuliert im Wesentlichen einen Aufrufstapel, ist jedoch eine gute Möglichkeit, diese Unterschiede aufzuzeigen.
Andy Hunt
58

Der Aufruf einer Funktion aus derselben Funktion heraus.

ChaosPandion
quelle
2
Dies ist die beste Erklärung, um wirklich anzufangen. Einfach und auf den Punkt; Sobald Sie diese Zusammenfassung erstellt haben, gehen Sie auf alle Details der Hauptreise ein.
jhocking
27

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: Sie endet nie ...
Eine rekursive Funktion muss immer nach einer Bedingung suchen , um festzustellen, ob sie sich selbst erneut aufrufen soll oder nicht.

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

Ehrfurcht
quelle
Sie können Ihren letzten Absatz immer noch iterativ implementieren, obwohl dies natürlich rekursiv besser wäre. "Wie man es benutzt, wann man es benutzt und wie man schlechtes Design vermeidet, ist wichtig zu wissen, was erfordert, dass man es selbst ausprobiert und versteht, was passiert." diese Art von Dingen.
Haylem
@haylem: Sie haben Recht mit der Antwort auf die Frage "Wie man es benutzt, wann man es benutzt und wie man schlechtes Design vermeidet" "wie gesagt), aber das würde einen umfangreichen Vortrag der eher unterrichtenden Art erfordern, als eine schnelle Antwort auf eine Frage hier. Sie haben mit Ihrer Antwort sehr gute Arbeit geleistet . +1 für das ... Wer wirklich ein besseres Verständnis des Konzepts haben will, wird davon profitieren, wenn er seine Antwort liest.
Ehrfurcht
Was ist mit einem Paar von Funktionen, die sich gegenseitig aufrufen? A ruft B auf und ruft A erneut auf, bis eine Bedingung erreicht ist. Wird dies immer noch als Rekursion betrachtet?
Santiagozky
Ja, die Funktion aruft sich immer noch selbst auf, nur indirekt (durch Aufrufen b).
Kindall
1
@santiagozky: Wie schon gesagt, es ist immer noch eine Rekursion. Ich würde jedoch empfehlen, dies nicht zu tun. Wenn Sie die Rekursion verwenden, sollte im Code klar sein, dass die Rekursion vorhanden ist. Wenn er sich indirekt über eine andere Funktion aufruft, ist es viel schwieriger zu sehen, was los ist. Wenn Sie nicht wissen, dass eine Funktion sich selbst effektiv aufruft, können Sie in die Situation geraten, in der Sie (oder jemand anderes, der diese Funktion nicht erstellt hat) eine Bedingung für die Rekursion brechen (während Sie die Funktionalität im Code ändern), und Sie enden in einer Sackgasse mit einer endlosen Schleife.
Ehrfurcht
21

Rekursives Programmieren ist der Prozess, ein Problem schrittweise zu reduzieren, um Versionen von sich selbst leichter zu lösen.

Jede rekursive Funktion tendiert dazu:

  1. Nimm eine Liste zum Verarbeiten oder eine andere Struktur oder Problemdomäne
  2. beschäftige dich mit dem aktuellen Punkt / Schritt
  3. Rufen Sie sich auf den Rest (n) / Subdomain (s)
  4. Kombinieren oder verwenden Sie die Ergebnisse der Subdomain-Arbeit

Wenn Schritt 2 vor 3 liegt und Schritt 4 trivial ist (Verkettung, Summe oder nichts), wird die 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.

Nimm die Durchquerung eines geradlinigen Binärbaums. Die Überquerung kann je nach Bedarf in Vorbestellung, Bestellung oder Nachbestellung erfolgen.

   B
A     C

Vorbestellung: BAC

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

Bestellung: ABC

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

Nachbestellung: ACB

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

Sehr viele rekursive Probleme sind bestimmte Fälle einer Kartenoperation oder eine Falte. Wenn Sie nur diese beiden Operationen verstehen, können Sie wichtige Anwendungsfälle für die Rekursion verstehen.

Orbling
quelle
Die Schlüsselkomponente für die praktische Rekursion ist die Idee, die Lösung eines etwas kleineren Problems zur Lösung eines größeren Problems zu verwenden. Ansonsten haben Sie nur eine unendliche Rekursion.
Barry Brown
@ Barry Brown: Ganz richtig. Daher meine Aussage "... ein Problem zu reduzieren, um Versionen von sich selbst leichter zu lösen"
Orbling
Das würde ich nicht unbedingt sagen ... Dies ist häufig der Fall, insbesondere bei Teilen und Erobern von Problemen oder in Situationen, in denen Sie wirklich eine Wiederholungsbeziehung definieren, die auf einen einfachen Fall hinausläuft. Aber ich würde sagen, es geht mehr darum zu beweisen, dass es für jede Iteration N Ihres Problems einen berechenbaren Fall N + 1 gibt.
Haylem
1
@ Sean McMillan: Rekursion ist ein leistungsfähiges Werkzeug, wenn es in Domänen verwendet wird, die dazu passen. Allzu oft betrachte ich es als eine clevere Methode, um mit relativ trivialen Problemen umzugehen, die die wahre Natur der anstehenden Aufgabe massiv verschleiern.
Orbling
20

Das OP sagte, dass Rekursion in der realen Welt nicht existiert, aber ich bitte, mich zu unterscheiden.

Nehmen wir die "Operation" der realen Welt, eine Pizza zu schneiden. Sie haben die Pizza aus dem Ofen genommen, und um sie zu servieren, müssen Sie sie halbieren, dann halbieren und dann wieder halbieren.

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

Hier ist ein Beispiel in Ruby:

def cut_pizza (vorhandene_scheiben, gewünschte_scheiben)
  if existing_slices! = desired_slices
    # Wir haben noch nicht genug Scheiben, um alle zu füttern
    # Wir schneiden die Pizzastücke und verdoppeln so ihre Anzahl
    new_slices = existing_slices * 2 
    # und das hier ist der rekursive Aufruf
    Pizza schneiden (New_Slices, Gewünschte_Slices)
  sonst
    # Wir haben die gewünschte Anzahl Scheiben, also kehren wir zurück
    # hier statt weiter zu rekursieren
    return existing_slices
  Ende
Ende

pizza = 1 # eine ganze pizza, 'one slice'
cut_pizza (pizza, 8) # => wir bekommen 8

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

Folgende Operationen können Sie mit rekursiven Funktionen implementieren:

  • 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 die Programmierung der Mechanik, eine Methode, um Duplikate auf clevere Weise 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 schreiben ein paar rekursive Funktionen, es klickt und huzzah einen weiteren mechanischen Trick in Ihrer Programmier- Toolbox .

Zusätzliches Guthaben Das cut_pizzaobige Beispiel gibt Ihnen einen zu tiefen Fehler, wenn Sie nach einer Anzahl von Slices fragen, die keine Potenz von 2 sind (dh 2 oder 4 oder 8 oder 16). Können Sie es so ändern, dass es nicht für immer läuft, wenn jemand nach 10 Scheiben fragt?

Ryan Allen
quelle
16

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

Rekursive Funktionen sind Funktionen, die sich selbst aufrufen. Rekursive Funktionen bestehen aus drei Dingen:

  1. Logik
  2. Ein Ruf an sich
  3. Wann kündigen?

Die beste Möglichkeit, rekursive Methoden zu schreiben, besteht darin, sich die Methode, die Sie schreiben möchten, als einfaches Beispiel vorzustellen und nur eine Schleife des Prozesses zu behandeln, über den Sie iterieren möchten. Anschließend fügen Sie den Aufruf der Methode selbst hinzu und fügen ihn hinzu, wann immer Sie möchten kündigen. Der beste Weg zu lernen ist, wie alle Dinge zu üben.

Da es sich um eine Programmierseite handelt, schreibe ich keinen Code, aber hier ist ein guter Link

Wenn Sie diesen Witz haben, wissen Sie, was Rekursion bedeutet.

Staubprogrammierer
quelle
Siehe auch diese Antwort: programmers.stackexchange.com/questions/25052/… (-:
Murph
4
Streng genommen benötigt die Rekursion keine Abbruchbedingung. Die Garantie, dass die Rekursion beendet wird, schränkt die Arten von Problemen ein, die die rekursive Funktion lösen kann, und es gibt einige Arten von semantischen Präsentationen, die überhaupt nicht beendet werden müssen.
Donal Fellows
6

Rekursion ist ein Tool, 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 jedoch normalerweise unübersichtlich. Gute Beispiele für andere rekursive Programme sind Datenstrukturen wie Bäume, Binärsuchbaum und sogar Quicksort.

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

Bryan Harrington
quelle
Ob es langsamer ist oder mehr Speicher benötigt, hängt von der jeweiligen Verwendung ab.
Orbling
5
Die Fibonacci-Sequenzberechnung ist eine schreckliche Sache, die man rekursiv machen kann. Baumdurchquerung ist eine viel natürlichere Verwendung der Rekursion. Wenn die Rekursion ordnungsgemäß verwendet wird, ist sie in der Regel nicht langsamer und benötigt keinen zusätzlichen Speicher, da Sie anstelle des Aufrufstapels einen eigenen Stapel verwalten müssen.
David Thornley
1
@ Dave: Das würde ich nicht bestreiten, aber ich denke, Fibonacci ist ein gutes Beispiel für den Anfang.
Bryan Harrington
5

Ich benutze diesen gerne:

Wie gehst du zum Laden?

Wenn Sie am Eingang des Ladens sind, gehen Sie einfach durch. Machen Sie andernfalls 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
  • Lösen Sie den Rest des Problems rekursiv

Tatsächlich verwenden wir im täglichen Leben viel Rekursion. wir denken einfach nicht so darüber.

Barry Brown
quelle
Das ist keine Rekursion. Es wäre, wenn Sie es in zwei Teile aufteilen würden: Gehen Sie den halben Weg zum Laden, gehen Sie die andere Hälfte. Recurse.
2
Das ist Rekursion. Dies ist keine Teilung und Eroberung, sondern nur eine Art der Rekursion. Graph-Algorithmen (wie das Finden von Pfaden) stecken voller rekursiver Konzepte.
Deadalnix
2
Dies ist eine Rekursion, aber ich halte es für ein schlechtes Beispiel, da es zu einfach ist, "einen Schritt zu machen und dann den Rest des Weges zum Geschäft zu gehen" in einen iterativen Algorithmus zu übersetzen. Ich denke, dies ist gleichbedeutend mit der Umwandlung einer schön geschriebenen forSchleife in eine sinnlose rekursive Funktion.
Brian
3

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 Gedächtnis) listet der Eintrag auf der Indexseite für Rekursion (allein) die tatsächliche Seite auf, auf der über Rekursion und Rekursion gesprochen wird die Indexseite auch.

Kanini
quelle
2

Josh K erwähnte bereits die Matroschka- 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 in der größeren Puppe lebt, die auf dem ersten Bild links von ihr steht. Diese Struktur funktioniert so (eine Puppe lebt in der größeren Puppe), bis sie nur noch die größte enthält.

Das Einzige, was Sie tun können, ist, Ihre Frage an die größte Puppe zu richten. Die größte Puppe (die die Antwort nicht kennt) muss Ihre Frage an die kürzere Puppe (die auf dem ersten Bild rechts zu sehen ist) weiterleiten. Da sie auch keine Antwort hat, muss sie die nächste kürzere Puppe fragen. Dies wird so lange gehen, bis die Nachricht die kürzeste Puppe erreicht. Die kürzeste Puppe (die einzige, die die geheime Antwort kennt) gibt die Antwort an die nächstgrößere Puppe (links zu finden) weiter, die sie an die nächstgrößere Puppe weitergibt ... und dies wird bis zur Antwort fortgesetzt erreicht sein endgültiges Ziel, welches die größte Puppe ist und endlich ... du :)

Dies ist, was Rekursion wirklich tut. Eine Funktion / Methode ruft sich selbst auf, bis sie die erwartete Antwort erhält. Wenn Sie rekursiven Code schreiben, ist es daher sehr wichtig zu entscheiden, wann die Rekursion beendet werden soll.

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

Sakisk
quelle
2

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

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, die kleiner oder gleich N sind. 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;
}

Untersuchen Sie den Vorgang jedoch erneut. 6! = 6 * 5 * 4 * 3 * 2 * 1. Nach der gleichen Definition, 5! = 5 * 4 * 3 * 2 * 1, was bedeutet, dass wir 6 sagen können! = 6 * (5!). 5! = 5 * (4!) Und so weiter. Auf diese Weise reduzieren wir das Problem auf eine Operation, die mit dem Ergebnis aller vorherigen Operationen ausgeführt wird. Dies reduziert sich schließlich auf einen Punkt, der als Basisfall bezeichnet wird und dessen Ergebnis per Definition bekannt ist. In unserem Fall ist 0! = 1 (wir könnten in den meisten Fällen auch 1! = 1 sagen). Beim Rechnen dürfen wir Algorithmen oft 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äziser, eine Funktion rekursiv zu definieren.
  • Geschwindigkeit - In bestimmten Fällen ist die Rekursion eines Algorithmus abhängig von der Sprache und der Computerarchitektur schneller als die entsprechende iterative Lösung. In der Regel ist das Ausführen eines Funktionsaufrufs eine schnellere Operation auf Hardwareebene als die Operationen und der Speicherzugriff, die für eine iterative Schleife erforderlich sind.
  • Teilbarkeit - Viele rekursive Algorithmen sind von der Mentalität "Teilen und Erobern"; Das Ergebnis der Operation ist eine Funktion des Ergebnisses derselben Operation, die für jede der beiden Hälften der Eingabe ausgeführt wird. Auf diese Weise können Sie die Arbeit auf jeder Ebene in zwei Teile aufteilen und, falls verfügbar, die andere Hälfte einer anderen "Ausführungseinheit" zur Bearbeitung übergeben. Dies ist normalerweise schwieriger oder unmöglich mit einem iterativen Algorithmus.

Nachteile:

  • Benötigt Verständnis - Sie müssen einfach das Konzept der Rekursion "erfassen", um zu verstehen, was vor sich geht, und daher effektive rekursive Algorithmen schreiben und beibehalten. Ansonsten sieht es einfach nach schwarzer Magie aus.
  • Kontextabhängig - Ob eine Rekursion eine gute Idee ist oder nicht, hängt davon ab, wie elegant der Algorithmus in 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 Aufrufstapel - In der Regel sind Funktionsaufrufe billiger als der Cache-Zugriff, wodurch die Rekursion schneller als die Iteration erfolgen kann. Normalerweise ist die Tiefe des Aufrufstapels jedoch begrenzt, was zu einer fehlerhaften Rekursion führen kann, wenn ein iterativer Algorithmus funktioniert.
  • Unendliche Rekursion - Sie müssen wissen, wann Sie aufhören müssen. Es ist auch eine unendliche Iteration möglich, aber die beteiligten Schleifenkonstrukte sind normalerweise leichter zu verstehen und somit leichter zu debuggen.
KeithS
quelle
1

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 auf Reisen mitnehmen möchten) und möchten das Gesamtgewicht wissen. In dem Container befinden sich zwei oder drei lose Gegenstände und einige andere Container (z. B. Packsäcke). Das Gewicht des Gesamtcontainers ist offensichtlich das Gewicht des leeren Containers plus das Gewicht von allem, was sich darin befindet. 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 sagen: "Nun, das Gewicht jedes Packsacks ist das Gewicht des leeren Behälters plus das Gewicht von allem, was sich darin befindet." Und dann geht man weiter in Container in Container und so weiter, bis man zu einem Punkt kommt, an dem sich nur noch lose Gegenstände in einem Container befinden. Das ist Rekursion.

Sie denken vielleicht, dass dies im wirklichen Leben niemals passiert, aber stellen Sie sich vor, Sie versuchen, die Gehälter von Personen in einem bestimmten Unternehmen oder Geschäftsbereich zu zählen oder zu addieren Die Abteilungen dort sind Abteilungen und so weiter. Oder Verkäufe in einem Land mit Regionen, von denen einige Unterregionen usw. haben. Solche Probleme treten im Geschäftsleben immer wieder auf.

Kate Gregory
quelle
0

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 genau einmal die Hand jedes anderen. Wie viele Handshakes finden statt? Sie können wissen, 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 ist die Antwort (durch Inspektion) offensichtlich 1.

Angenommen, Sie haben drei Personen. Ermitteln Sie eine Person, 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 jetzt schon gemacht und es ist 1. Die Antwort lautet also 2 + 1 = 3.

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

Ausgedrückt als rekursive Funktion,

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

Mitch Schwartz
quelle
0

Im Leben kommt es (im Gegensatz zu einem Computerprogramm) selten zu einer Rekursion unter unserer direkten Kontrolle, da es verwirrend sein kann, dies zu erreichen. Bei der Wahrnehmung geht es in der Regel eher um die Nebenwirkungen als um die Funktionsreinheit. Wenn also eine Rekursion auftritt, bemerken Sie diese möglicherweise nicht.

Rekursion findet hier auf der Welt statt. Viel.

Ein gutes Beispiel ist (in vereinfachter Form) der Wasserkreislauf:

  • Die Sonne heizt den See
  • Das Wasser steigt in den Himmel und bildet Wolken
  • Die Wolken ziehen zu einem Berg hinüber
  • Am Berg wird die Luft zu kalt, um die Feuchtigkeit zurückzuhalten
  • Regen fällt
  • Ein Fluss bildet sich
  • Das Wasser im Fluss fließt in den See

Dies ist ein Zyklus, der dazu führt, dass sein Selbst wieder passiert. 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 zunächst nicht erkennen, aber die Art und Weise, wie wir einen Satz erzeugen, ist rekursiv, da wir nach den Regeln eine Instanz eines Symbols in eine andere Instanz desselben Symbols einbetten können.

Aus Steven Pinkers Sprachinstinkt:

Wenn 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

Der Vorgang des Verstehens des vollständigen Satzes beinhaltet das Verstehen kleinerer Sätze, bei denen die gleichen mentalen Tricks angewendet werden, um als vollständiger Satz verstanden zu werden.

Um die Rekursion aus programmtechnischer Sicht zu verstehen, ist es am einfachsten, sich ein Problem anzusehen, das mit der Rekursion gelöst werden kann, und zu verstehen, warum dies der Fall sein sollte und was dies bedeutet.

Für das Beispiel verwende ich die größte gemeinsame Divisor-Funktion, kurz gcd.

Du hast deine beiden Nummern aund b. Um ihre gcd zu finden (vorausgesetzt, keine von beiden ist 0), müssen Sie prüfen, ob sie agleichmäßig in geteilt werden können b. Wenn dies bder Fall ist, müssen Sie nach dem GCD bund dem Rest von suchen a/b.

Sie sollten bereits erkennen können, dass dies eine rekursive Funktion ist, da Sie die gcd-Funktion haben, die die gcd-Funktion 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, andernfalls wird Ihre Funktion für immer wiederkehren, was schließlich zu einem Stapelüberlauf führt!

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 getan wird und was als Nächstes passieren wird, sodass Sie leichter herausfinden können, ob der Code ordnungsgemäß funktioniert .

Matt Ellen
quelle
1
Ich fand das Beispiel des Wasserkreislaufs iterativ. Das zweite Sprachbeispiel scheint mehr Teilung und Eroberung als Rekursion zu sein.
Gulshan
@ Gulshan: Ich würde sagen, der Wasserkreislauf ist rekursiv, weil er sich selbst wie eine rekursive Funktion wiederholt. Es ist nicht so, als würde man einen Raum malen, in dem man die gleichen Schritte über mehrere Objekte (Wände, Decke usw.) ausführt, wie in einer for-Schleife. Das Sprachbeispiel verwendet das Teilen und Erobern, aber auch die "Funktion", die aufgerufen wird, um an den verschachtelten Sätzen zu arbeiten, ist auf diese Weise rekursiv.
Matt Ellen
Im Wasserkreislauf wird der Kreislauf von der Sonne gestartet, und kein anderes Element des Kreislaufs bewirkt, dass die Sonne ihn erneut startet. Also, wo ist der rekursive Aufruf?
Gulshan
Es gibt keinen rekursiven Aufruf! Ist keine Funktion. : D Es ist rekursiv, weil es dazu führt, dass sein Selbst wiederkehrt. Das Wasser aus dem See kommt zum See zurück und der Zyklus beginnt von neuem. Wenn ein anderes System Wasser in den See füllen würde, wäre es iterativ.
Matt Ellen
1
Der Wasserkreislauf ist eine while-Schleife. Sicher, eine while-Schleife kann durch Rekursion ausgedrückt werden, aber dadurch wird der Stapel gesprengt. Bitte nicht
Brian
0

Hier ist ein reales Beispiel für die Rekursion.

Stellen Sie sich vor, Sie haben eine Comic-Sammlung und Sie mischen alles zu einem großen Haufen. Achtung - wenn sie wirklich eine Sammlung haben, können sie Sie sofort töten, wenn Sie nur die Idee erwähnen, dies zu tun.

Lassen Sie sie nun diesen großen unsortierten Stapel Comics mit Hilfe 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 dabei ist: Wenn es nur um einzelne Ausgaben geht, haben sie den vollen "Stapelrahmen" mit den lokalen Pfählen, die vor ihnen auf dem Boden sichtbar sind. Geben Sie ihnen mehrere Ausdrucke des Handbuchs und legen Sie einen neben jede Stapelebene mit einer Markierung, auf der Sie sich gerade befinden (dh den Status der lokalen Variablen), damit Sie dort bei jedem Abschluss fortfahren können.

Das ist es, worum es bei der Rekursion im Grunde geht: Je mehr Sie sich damit befassen, desto detaillierter wird derselbe Prozess ausgeführt.

Sichern
quelle
-1
  • Beenden Sie, wenn die Ausgangsbedingung erreicht ist
  • etwas tun, um den Zustand der Dinge zu ändern
  • mache die Arbeit von Grund auf, beginnend mit dem gegenwärtigen Stand der Dinge

Rekursion ist eine sehr präzise Methode, um etwas auszudrücken, das wiederholt werden muss, bis etwas erreicht ist.

vpit3833
quelle
-1

Kein einfaches Englisch, keine Beispiele aus dem wirklichen Leben, sondern zwei Möglichkeiten, Rekursion durch Spielen zu lernen:

mouviciel
quelle
-2

Eine schöne Erklärung der Rekursion ist wörtlich "eine Aktion, die von selbst wieder auftritt".

Stellen Sie sich einen Maler vor, der eine Wand malt. Das ist rekursiv, weil die Aktion darin besteht, "einen Streifen von Decke zu Boden zu malen, als ein wenig nach rechts zu rutschen, und (einen Streifen von Decke zu Boden zu malen, als ein wenig nach rechts zu rutschen, und (a streifen Sie von der Decke zum Boden als scoot über ein wenig nach rechts und (etc))) ".

Seine paint () -Funktion ruft sich immer wieder auf, um seine größere paint_wall () -Funktion zu bilden.

Hoffentlich hat dieser arme Maler eine Art Abbruchbedingung :)

Dan1ell
quelle
6
Das Beispiel scheint mir eher eine iterative Prozedur zu sein, nicht eine rekursive.
Gulshan
@ Gulshan: Rekursion und Iteration machen ähnliche Dinge und oft funktionieren die Dinge auch mit beiden. Funktionale Sprachen verwenden in der Regel eine Rekursion anstelle einer Iteration. Es gibt bessere Beispiele für Rekursionen, bei denen es umständlich wäre, dasselbe iterativ zu schreiben.
David Thornley