>> ZAMYLA: Um zu verstehen, Rekursion, müssen Sie
zuerst verstehen, Rekursion.
Mit Rekursion bei der Programmgestaltung mittels dass Sie selbst bezogen haben
Definitionen.
Rekursive Datenstrukturen, zum Beispiel, sind Datenstrukturen,
schließen sich in deren Definitionen.
Aber heute werden wir konzentrieren auf rekursiven Funktionen.
>> Daran erinnern, dass Funktionen übernehmen Eingänge, Argumente, und einen Wert als
vertreten durch Ausgabe dieses Diagramm hier.
Wir werden von der Box, da der Körper denken die Funktion, die die Gruppe der
Anweisungen, die der Interpretation Eingangs-und ein Ausgangssignal.
Bei näherer Betrachtung innerhalb des Körpers die Funktion kann Anrufe zu offenbaren,
andere Funktionen.
Nutzen Sie diese einfache Funktion, foo, dass benötigt ein String als Eingabe und
Drucke wie viele Briefe dass String hat.
Die Funktion strlen, für String-Länge, genannt wird, dessen Ausgangssignal
für den Aufruf von printf erforderlich.
>> Nun, was macht eine rekursive Funktion besondere ist, dass es sich selbst nennt.
Wir können diese rekursive stellen rufen mit dieser orangefarbenen Pfeil
Schleife zurück zu sich.
Aber selbst wieder ausführen wird nur eine weitere rekursiven Aufruf und
eine und noch eine.
Aber rekursive Funktionen kann nicht unendlich sein.
Sie müssen irgendwie zu beenden, oder Ihr Programm wird ewig laufen.
>> Also müssen wir einen Weg finden, zu brechen aus den rekursiven Aufrufen.
Wir nennen dies die Basisfall.
Wenn die Basisfall-Bedingung erfüllt, die Funktion gibt, ohne dass
ein weiterer rekursiven Aufruf.
Nutzen Sie diese Funktion, hallo, eine Leere Funktion das dauert ein int n als Eingabe.
Der Basisfall kommt zuerst.
Wenn n kleiner als Null ist, und Druck bye zurück Für alle anderen Fälle, die
Funktion druckt hallo und führen der rekursive Aufruf.
Ein weiterer Aufruf der Funktion hallo mit ein Eingangswert verringert.
>> Nun, obwohl wir drucken hallo, das Funktion wird nicht beendet, bis wir
Rückkehr der Rückgabetyp, in diesem Fall nichtig.
Also für alle n anderen als der Basisfall diese Funktion wird wieder hallo hallo
n minus 1.
Da diese Funktion aber leer, wir wird nicht explizit Rückkehr geben hier.
Wir müssen nur die Funktion ausführen.
So ruft hallo (3) gedruckt und hallo hallo ausführen (2), hallo (1) führt ein
welche hallo ausführt (0), wobei die Base-Case-Bedingung erfüllt ist.
Also hallo (0) druckt Abschied und kehrt zurück.
>> OK.
So, jetzt haben wir die Grundlagen der rekursive Funktionen, die sie benötigen,
mindestens einen Basisfall sowie rekursiven Aufruf, machen wir weiter, um eine
sinn Beispiel.
Eines, das nicht nur zurückgibt nichtig, egal was.
>> Werfen wir einen Blick auf die faktorielle Betrieb am häufigsten verwendet
Wahrscheinlichkeitsberechnungen.
Die Fakultät von n ist das Produkt von jeder positive ganze Zahl kleiner als
und gleich n ist.
So Fakultät fünf ist 5 mal 4 mal 3 mal 2 mal 1 bis 120 zu geben.
Vier Fakultät ist 4 mal 3 mal 2 mal 1 bis 24 geben.
Und das gleiche gilt um jede positive ganze Zahl ist.
>> Also, wie könnten wir einen rekursiven Funktion, die die Fakultät berechnet
einer Anzahl?
Nun, wir müssen zu identifizieren sowohl die Basisfall und der rekursive Aufruf.
Der rekursive Aufruf wird die gleiche sein in allen Fällen mit Ausnahme der Basis
Fall, was bedeutet, dass wir uns zu haben, ein Muster zu finden, die uns unsere
gewünschte Ergebnis.
>> In diesem Beispiel sehen Sie, wie 5 faktorielle Multiplikation beinhaltet 4 zu 3 nach 2 von 1
Und noch am selben Multiplikation Hier befindet sich die
Definition von 4 Fakultät.
So sehen wir, dass 5 Fakultät ist nur 5 x 4 faktorielle.
Jetzt hat dieses Muster anwenden 4 factorial als auch?
Ja.
Wir sehen, dass 4 enthält die faktorielle Multiplikation 3 mal 2 mal 1, die
sehr gleiche Definition wie 3 Fakultät.
SO 4 faktoriellen gleich 4 mal 3 faktorielle, und so weiter und so fort unserer
Muster-Sticks bis zum 1. Fakultät, die per Definition gleich 1 ist.
>> Es gibt keine andere positive Zahlen verlassen.
So haben wir das Muster für unsere rekursiven Aufruf.
n Fakultät ist gleich dem n-fachen die Fakultät von n minus 1.
Und unsere Basisfall?
Das wird nur unsere Definition sein von 1 Fakultät.
>> So, jetzt können wir mit dem Schreiben zu bewegen auf Code für die Funktion.
Für den Basisfall, müssen wir die Zustand n = 1 entspricht, wo
wir 1 zurück.
Dann Bewegen auf dem rekursiven Aufruf, wir n-mal die Rückkehr
Fakultät von n minus 1.
>> Nun wollen wir testen, diese unsere.
Lassen Sie uns versuchen Fakultät 4.
Per unserer Funktion es ist gleich 4 mal faktorielle (3).
Fakultät (3) gleich ist 3 mal faktoriellen (2).
Faktoriellen (2) gleich 2-mal ist faktorielle (1), die 1 zurück.
Fakultät (2) gibt nun 2 mal 1, 2.
Fakultät (3) kann nun zurückkehren 3 mal 2, 6.
Und schließlich, faktorielle (4) gibt 4 mal 6, 24.
>> Wenn Sie stoßen Schwierigkeiten sind mit dem rekursiven Aufruf, so tun, als
arbeitet die Funktion bereits.
Was ich damit meine ist, dass Sie sollten Vertrauen Sie Ihrem rekursive Aufrufe zur Rückkehr
die richtigen Werte.
Zum Beispiel, wenn ich weiß, dass faktorielle (5) gleich 5 mal
faktorielle (4), werde ich darauf vertrauen, dass faktorielle (4) wird mir 24.
Betrachten Sie es als eine Variable, wenn Sie wird, wie wenn Sie bereits definiert
faktorielle (4).
So dass für jede faktorielle (n), ist es das Produkt von n und
die bisherige Fakultät.
Und das vorherige Fakultät wird durch den Aufruf erhalten
Fakultät von n minus 1.
>> Nun, sehen, wenn Sie implementieren können, ein rekursive Funktion sich.
Laden Sie Ihre Terminal oder run.cs50.net, und schreiben Sie eine Funktion Summe
das dauert eine ganze Zahl n und gibt die Summe aller aufeinander folgende positive
n ganze Zahlen von 1.
Ich habe aus der Summen von einigen geschrieben Werte, Ihnen zu helfen unsere.
Erstens, herauszufinden, die Base-Case-Zustand.
Dann schauen Summe (5).
Können Sie es in Bezug auf Ausdruck einer anderen Summe?
Nun, was Summe (4)?
Wie kann man ausdrücken Summe (4) in Bezug auf eine andere Summe?
>> Sobald Sie Summe haben (5) und Summe (4) in Bezug auf andere Summen ausgedrückt finden
Wenn Sie identifizieren können, ein Muster für die Summe (n).
Wenn nicht, versuchen ein paar andere Zahlen und drücken ihre Summen in
Bezug auf weitere Zahlen.
Durch die Identifizierung von Mustern für diskrete Zahlen, auf Ihrem Weg zu du bist gut
Identifizierung des Musters für jedes n.
>> Rekursion ist ein wirklich mächtiges Werkzeug, so natürlich ist es nicht darauf beschränkt
mathematische Funktionen.
Rekursion kann sehr effektiv eingesetzt werden beim Umgang mit Bäumen zum Beispiel.
Schauen Sie sich die kurz auf Bäume für ein gründlichere Überprüfung, aber für jetzt
Daran erinnern, dass binäre Suchbäume, in Insbesondere werden aus Knoten, die jeweils
mit einem Wert und zwei Knoten Zeiger.
Gewöhnlich wird dies durch die dargestellten Elternknoten mit einer Zeile Zeige
auf der linken Kindknoten und eines auf der rechten untergeordneten Knoten.
Der Aufbau eines binären Such Baum eignet sich gut
auf eine rekursive Suche.
Die rekursiven Aufruf entweder in den Pässen linken oder rechten Knoten, aber
der, dass in der Baum kurz.
>> Angenommen, Sie möchten eine Operation ausgeführt werden soll jeder einzelne Knoten in einem binären Baum.
Wie können Sie über das gehen?
Nun, Sie könnten eine rekursive schreiben Funktion, die den Vorgang ausführt
auf den übergeordneten Knoten und macht eine rekursive anrufen, um die gleiche Funktion,
vorbei in den linken und rechte Kind-Knoten.
Zum Beispiel wird diese Funktion foo, dass ändert den Wert eines bestimmten Knotens und
alle seine Kinder ein.
Der Basisfall von einem Null-Knoten Ursachen die Funktion, um zurückzukehren, was
dass es keine Knoten in diesem Unterbaum links.
>> Lassen Sie uns durch sie hindurchgehen.
Die erste Mutter 13 ist.
Wir ändern den Wert auf 1, und rufen Sie dann unsere Funktion auf der linken als auch
nach rechts.
Die Funktion, foo, ist auf der linken Seite namens Teilbaum ersten, so dass der linke Knoten
wird auf 1 und neu zugewiesen werden, wird foo auf die Kinder dieses Knotens aufgerufen werden,
zuerst die linke und dann die rechte, und so weiter und so fort.
Und ihnen sagen, dass die Zweige nicht haben mehr Kinder, damit der gleiche Prozess
wird für die richtigen Kinder weiterhin Knoten, bis der ganze Baum sind
1 zugewiesen.
>> Wie Sie sehen können, können Sie nicht beschränkt werden um nur ein rekursiven Aufruf.
Ebenso viele, wie die Arbeit zu erledigen.
Was, wenn Sie einen Baum hatte, wo jeder Knoten hatte drei Kinder,
Linke, mittlere und rechte?
Wie würden Sie foo bearbeiten?
Nun, einfach.
Fügen Sie einfach einen weiteren rekursiven Aufruf und Pass in die Mitte Knotenzeiger.
>> Rekursion ist sehr mächtig und nicht auf erwähnen, elegant, aber es kann eine werden
schwieriges Konzept auf den ersten, so sein Patient und nehmen Sie sich Zeit.
Beginnen Sie mit dem Basisfall.
Es ist in der Regel am einfachsten zu identifizieren, und dann können Sie arbeiten
von dort nach hinten.
Sie wissen, Sie zu erreichen, müssen Sie Ihre Basisfall, so dass Macht
Ihnen ein paar Hinweise.
Versuchen Sie, ein Sonderfall in Ausdruck hinsichtlich anderen Fällen oder in Teilmengen.
>> Vielen Dank für diesen kurzen beobachten.
Zumindest, jetzt können Sie Witze verstehen, wie diese.
Mein Name ist Zamyla, und dies ist CS50.
>> Nutzen Sie diese Funktion, hallo, ein Leere Funktion, nimmt
ein int, n, als Eingabe.
Der Basisfall kommt zuerst.
Wenn n kleiner als 0 ist, Druck "Auf Wiedersehen" und zurück.