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.