[Musikwiedergabe] 

DOUG LLOYD: Sie denken wahrscheinlich, dass Code wird nur verwendet, um eine Aufgabe zu erfüllen. Sie schreiben es heraus. Es tut etwas. Das ist ziemlich viel es. 

Sie kompilieren. Sie führen Sie das Programm. Sie sind gut zu gehen. 

Aber es glauben oder nicht, wenn Sie für eine lange Zeit zu codieren, Sie könnte in der Tat gekommen, um zu sehen Code als etwas, das schön ist. Es löst ein Problem in eine sehr interessante Art und Weise, oder es gibt einfach etwas wirklich ordentlich über die Art, wie es aussieht. Sie werden sich vielleicht lachen mich an, aber es ist wahr. Und Rekursion ist ein Weg, diese Idee Art erhalten schöne, elegant aussehende Code. Es löst Probleme in einer Weise, sind interessant, einfach zu visualisieren, und überraschend kurz. 

Die Art, wie Rekursion Werke ist, eine rekursive Funktion wird als eine Funktion, die Anrufe definiert sich als Teil der Ausführung. Das mag ein wenig seltsam, und wir werden ein bisschen zu sehen etwa, wie das funktioniert in einem Augenblick. Aber noch einmal, diese rekursive Prozeduren sind geht so elegant zu sein denn sie gehen, um dieses Problem zu lösen, ohne mit all diesen anderen Funktionen oder diese langen Schleifen. Sie finden, dass diese rekursive sehen Verfahren gehen, um so kurz zu suchen. Und sie wirklich gehen, um Ihr Code sehen viel schöner. 

Ich gebe Ihnen ein Beispiel geben davon zu sehen, wie eine rekursive Prozedur könnte festgelegt werden. Also, wenn Sie mit diesen vertraut sind von Math-Klasse vor vielen Jahren, Es gibt etwas, genannt faktorielle Funktion, die normalerweise wie ein Ausrufezeichen, bezeichnet die wird über alle positiven ganzen Zahlen definiert. Und die Art und Weise, dass n Fakultät berechnet wird sie alle zu multiplizieren die Zahlen weniger als oder gleich n together-- alle ganzen Zahlen weniger als oder gleich n zusammen. 

So 5 Fakultät ist 5-mal 4 mal 3 mal 2 mal 1. Und 4 Fakultät ist 4 mal 3 mal 2 mal 1 und so weiter. Sie erhalten die Idee. 

Als Programmierer, wissen wir nicht n verwenden, Ausrufezeichen. Also werden wir die Fakultät zu definieren Funktion als Tatsache des n. Und wir factorial verwenden, um zu erstellen eine rekursive Lösung für ein Problem. Und ich denke, finden Sie vielleicht, dass es viel mehr visuell attraktiv als die iterative Version davon, die wir werden auch einen Blick auf in einem Augenblick. 

So, hier sind ein paar facts-- pun intended-- über die factorial-- Fakultätsfunktion. Die Fakultät von 1, wie gesagt, ist 1. Die Fakultät von 2 2 mal 1. Die Fakultät von 3 3 mal 2 mal 1, und so weiter. Wir sprachen über 4 und 5 bereits. 

Aber ein Blick auf diese, ist nicht das wahr? Wird nicht von 2 factorial nur 2-fache der Fakultät von 1? Ich meine, die Fakultät 1 1 ist. Also warum können wir nicht einfach sagen, dass, seit Fakultät von 2 2 mal 1, es ist wirklich nur 2 mal die Fakultät von 1? 

Und dann die sich diese Idee, ist nicht der Fakultät von 3 nur 3-fache der Fakultät von 2? Und die Fakultät von 4 ist 4-mal die Fakultät von 3, und so weiter? In der Tat die faktorielle aus einer beliebigen Anzahl kann einfach wenn wir Art ausgedrückt werden der Durchführung dieses heraus für immer. Wir können Art von verallgemeinern die Fakultät Problem da es n-mal die Fakultät von n minus 1. Es ist n-mal das Produkt alle Zahlen kleiner als ich. 

Diese Idee, dies Verallgemeinerung des Problems ermöglicht es uns, rekursiv definieren die Fakultätsfunktion. Wenn Sie eine Funktion definieren rekursiv, es gibt zwei Dinge, um ein Teil davon zu sein braucht. Sie müssen einen so genannten Basisfall, der, wenn Sie es auslösen, wird die rekursive Prozess zu stoppen. 

Ansonsten eine Funktion, ruft itself-- wie Sie vielleicht imagine-- könnte ewig so weitergehen. Function die Funktion aufruft ruft die Funktionsaufrufe Die Funktion ruft die Funktion. Wenn Sie nicht über einen Weg um es zu stoppen, Ihr Programm effektiv geklebt werden bei einer Endlosschleife. Es wird schließlich abstürzen, denn es wird ein Speicherproblem. Aber das ist nicht der Punkt. 

Wir müssen einen anderen Weg, um zu stoppen Dinge neben unserem Programm abstürzt, denn ein Programm, das abstürzt ist wahrscheinlich nicht schön oder elegant. Und so haben wir nennen dies die Basisfall. Dies ist eine einfache Lösung, für ein Problem, stoppt die rekursive Prozess auftritt. Also das ist ein Teil der eine rekursive Funktion. 

Der zweite Teil ist die rekursive Fall. Und das ist, wo die Rekursion tatsächlich stattfinden wird. Hier setzt die Funktion selbst aufrufen. 

Es wird sich in genau das nicht nennen die gleiche Art, wie es hieß. Es wird eine leichte Variation sein das macht das Problem, es ist versuchen zu lösen, ein klein wenig kleiner. Aber es geht in der Regel den Schwarzen Peter des Lösens der Masse der Lösung an einen anderen Anruf auf der ganzen Linie. 

Welche dieser Blicke wie die Basisfall hier? Welcher dieser sieht aus wie die einfachste Lösung für ein Problem? Wir haben eine Reihe von Fakultäten, und wir werden weiterhin könnten gehen an-- 6, 7, 8, 9, 10, und so weiter. 

Aber eine dieser sieht aus wie eine gutes Beispiel, um die Basis Fall sein. Es ist eine sehr einfache Lösung. Wir haben nicht um etwas Besonderes zu tun. 

Die Fakultät von 1 ist nur 1. Wir haben nicht zu einem zu tun Multiplikation überhaupt. Es scheint, als ob wir um zu versuchen, dieses Problem zu lösen, und wir müssen das stoppen Rekursion irgendwo, wir wollen wahrscheinlich zu stoppen es, wenn wir bekommen, um 1. Wir wollen nicht, dass, bevor stoppen. 

Also, wenn wir definieren unsere Fakultätsfunktion, hier ist ein Gerüst für wie wir das tun. Wir müssen in diesen beiden things-- Stecker das Basismodell und der rekursiven Fall. Was ist in der Basisfall? Wenn n gleich 1 ist, zurückzukehren 1-- das ist, ein wirklich einfaches Problem zu lösen. 

Die Fakultät von 1 1. Es ist nicht 1 mal nichts. Es ist nur 1. Es ist eine sehr einfache Tatsache. Und damit unsere Basis Fall sein. Wenn wir uns übergeben 1 in diesem Funktion, werden wir nur 1 zurückzukehren. 

Was ist die rekursive Fall wohl aussehen? Für jede andere Zahl außer 1, was ist das Muster? Nun, wenn wir nehmen die Fakultät von n, es ist n mal die Fakultät von n minus 1. 

Wenn wir nehmen die Fakultät 3, es ist 3-fache der Fakultät 3 minus 1, oder 2. Und so, wenn wir nicht Blick auf 1, sonst Rück n mal die Fakultät von n minus 1. Es ist ziemlich einfach. 

Und aus Gründen der mit geringfügig sauberer und elegant-Code, wissen, dass, wenn wir Einzelleitungsschleifen oder Single-Line-bedingte Verzweigungen, können wir all das loswerden geschweiften Klammern um sie herum. So können wir dies, dies zu konsolidieren. Dies hat genau die gleiche Funktionen wie diese. 

Ich bin einfach nur Wegnehmen der geschweiften Hosenträger, denn es gibt nur eine Zeile innerhalb dieser bedingte Verzweigungen. Das sind also identisch verhalten. Wenn n gleich 1 ist, gib 1. N mal Ansonsten zurückkehren die Fakultät von n minus 1. So machen wir das Problem kleiner. Wenn n beginnt als 5, sind wir zu gehen Rück 5 mal die Fakultät 4. Und wir werden gleich sehen, wenn wir sprechen über den Anruf stack-- in einem anderen Video wo wir über das reden rufen stack-- wir lernen, warum genau dieser Prozess funktioniert. 

Aber während Fakultät von 5 sagt, Rück 5 mal Fakultät von 4, und 4 wird sagen, OK, gut, Rück 4 mal die Fakultät von 3. Und wie Sie sehen können, sind wir Art der Annäherung an 1. Wir nähern und näher an das Basisszenario. 

Und wenn wir uns auf den Basisfall, alle vorherigen Funktionen haben die Antwort sie suchten. Fakultät 2 sagte Rückkehr 2-fache der Fakultät von 1. Nun, Fakultät von 1 ergibt 1. So die Forderung nach factorial von 2 kann 2 mal 1 zurückzukehren, und geben Sie das zurück zu Fakultät 3, die darauf wartet, zu diesem Ergebnis. 

Und dann ist es berechnen das Ergebnis, 3-mal 2 6, und geben Sie es zurück zu Fakultät von 4. Und wieder haben wir ein Video auf der Call-Stack wenn dies ein wenig dargestellt mehr als das, was ich jetzt sage. Aber das ist es. Dies allein ist die Lösung Berechnung der Fakultät einer Zahl. 

Es ist nur vier Zeilen Code. Das ist ziemlich cool, oder? Es ist irgendwie sexy. 

So im Allgemeinen, aber nicht immer, eine rekursive Funktion kann eine Schleife in einer zu ersetzen Nicht-rekursive Funktion. Also hier, nebeneinander, ist die iterative Version der Fakultätsfunktion. Beide dieser calculate genau die gleiche Sache. 

Beide berechnen die Fakultät von n. Die Version auf der linken Rekursion verwendet, es zu tun. Die Version auf der rechten Iteration verwendet, es zu tun. 

Und beachtet, müssen wir erklären, eine Variable eine ganze Zahl Produkt. Und dann haben wir Schleife. Sofern n größer als 0 ist, haben wir halten Multiplikation dieses Produkts durch n und Dekrementieren n bis berechnen wir das Produkt. Also diese beiden Funktionen wieder, tun genau das Gleiche. Aber sie tun es nicht in genau die gleiche Weise. 

Nun ist es möglich, haben mehr als eine Basis Gehäuse oder mehreren rekursiven Fall kann in Abhängigkeit ab, was Ihre Funktion wird versuchen, zu tun. Sie sind nicht unbedingt nur beschränkt eine einzige Basisfall oder eine einzelne rekursive Fall. So ein Beispiel für etwas, mit mehreren Basis Fällen könnte die this-- Fibonacci-Zahlenfolge. 

Sie können aus erinnern Grundschule Tage dass die Fibonacci-Folge definiert wie this-- das erste Element 0. Das zweite Element 1. Beide von denen sind nur per Definition. 

Dann jeden zweiten Element definiert ist als Summe von n minus 1 und n minus 2. Also das dritte Element wäre 0 plus 1 ist 1. Und dann wird das vierte Element würde das zweite Element 1 sein kann, plus dem dritten Element 1. Und das wäre 2 sein. Und so weiter und so fort. 

Also in diesem Fall, wir haben zwei Basis Fällen. Wenn n gleich 1, 0 zurück. Wenn n gleich 2 ist, gib 1. Andernfalls zurückkehren Fibonacci von n minus 1 plus Fibonacci n minus 2. 

Also das ist, mehrere Basis Fällen. Wie sieht es mehrere rekursive Fällen? Nun, es ist etwas, genannt Collatz-Vermutung. Ich werde mich nicht zu sagen, Sie wissen, was das ist, denn es ist wirklich unsere letzte Problem für diese bestimmte Video. Und es ist unsere Übung zusammen zu arbeiten auf. 

Also hier ist was die Collatz Conjecture ist-- Es gilt für jede positive ganze Zahl ist. Und spekuliert, dass es immer möglich, um wieder 1, wenn Sie die folgenden Schritte aus. Wenn n 1 ist, zu stoppen. Wir haben wieder auf 1 hat, wenn n 1 ist. 

Andernfalls durch diese gehen Prozess erneut von n durch 2 geteilt. Und sehen, wenn Sie zurück zu 1 bekommen können. Andernfalls, wenn n ungerade ist, durchlaufen dieser Prozess wieder auf 3 n + 1, oder 3 mal n plus 1. Hier haben wir also eine einzige Basisfall. Wenn n gleich 1 ist, zu stoppen. Wir sind nicht dabei jede weitere Rekursion. 

Aber wir haben zwei rekursive Fällen. Wenn n gerade ist, machen wir einen rekursiven Fall calling n durch 2 geteilt. Wenn n ungerade ist, wir tun, eine andere rekursiven Fall auf 3 mal n plus 1. 

Und so ist das Ziel für dieses Video um eine zweite zu nehmen, unterbrechen Sie das Video, und versuchen, dies schreibe rekursive Funktion Collatz wo Sie übergeben einen Wert n und berechnet er, wie viele Schritte es dauert, bis 1, wenn man vom n starten und folgen Sie diese Schritte oben. Wenn n 1 ist, dauert es 0 Schritten. Ansonsten ist es zu gehen einen Schritt zzgl jedoch viele Schritte nimmt es entweder N geteilt durch 2, wenn n gerade ist, oder 3 n plus 1 wenn n ungerade ist. 

Nun, ich habe auf dem Bildschirm ablegen ein paar Test Dinge für Sie, ein paar Tests Fällen für Sie, um zu sehen, was diese verschiedenen Collatz Zahlen sind, und auch eine Darstellung der Schritte, brauchen, um durch, so dass Sie weg sein Art sehen, diesen Prozess in Aktion. Also, wenn n gleich 1, Collatz von n 0. Sie müssen nicht zu tun, alles tun, um wieder auf 1 zu bekommen. Bist du schon da. 

Wenn n 2 ist, dauert es einen Schritt, um bis 1 zu bekommen. Sie beginnen mit 2. Nun, 2 nicht gleich 1. Also, es wird ein Schritt sein, zzgl jedoch viele Schritte es nimmt n durch 2 geteilt. 

2 geteilt durch 2 1 ist. So einen Schritt zzgl jedoch dauert es viele Schritte, die für 1. 1 nimmt Null Schritte. 

3, wie Sie sehen können, gibt es durchaus ein paar Schritte. Sie gehen vom 3. Und dann haben Sie zu gehen 10, 5, 16, 8, 4, 2, 1. Es dauert sieben Schritte, um wieder auf 1 zu bekommen. Und wie Sie sehen können, gibt es eine paar andere Testfälle hier zu testen Sie Ihr Programm. Also noch einmal, unterbrechen Sie das Video. Und ich werde gehen nun zurück zu springen was die eigentliche Prozess ist hier, was diese Vermutung. 

Sehen Sie, wenn Sie herausfinden können wie Collatz von n zu definieren so daß es berechnet, wie viele Schritte es braucht, um auf 1 zu bekommen. Hoffentlich können Sie das Video angehalten haben und Sie sind nicht nur darauf warten, für mich dass Sie hier die Antwort geben. Aber wenn Sie sind, nun ja, hier ist die Antwort sowieso. 

Also hier ist eine mögliche Definition der Collatz-Funktion. Unsere Basis Fall-- wenn n gleich 1 ist, kehren wir 0. Es braucht nicht jeder Schritte, um wieder auf 1 zu bekommen. 

Ansonsten haben wir zwei rekursive cases-- eine für ungerade Zahlen und eine für ungerade. So wie ich das testen gerade Zahlen ist zu prüfen, ob n mod 2 gleich 0 ist. Dies ist im Grunde wieder die Frage zu stellen, wenn Sie, was mod ist-- erinnern, wenn ich divide n von 2 gibt es keinen Rest? Das wäre eine gerade Zahl sein. 

Und so, wenn n mod 2 gleich 0 ist Tests ist dies eine gerade Zahl ist. Wenn dem so ist, möchte ich zurück 1, denn dies ist definitiv nehmen einen Schritt zzgl Collatz von was auch immer Nummer ist die Hälfte von mir. Ansonsten möchte ich zurück 1 zzgl Collatz von 3 mal n plus 1. Das war die andere rekursive Schritt, den wir könnte zu ergreifen, um die Berechnung Collatz-- die Anzahl der Schritte es braucht, um wieder 1 einer Nummer versehen. Also hoffentlich dieses Beispiel hat dir ein wenig ein Geschmack von rekursive Prozeduren. Ich hoffe, dass du Code ein wenig schöner, wenn implementiert in einem eleganten, rekursive Art und Weise. Aber selbst wenn nicht, ist eine Rekursion wirklich leistungsfähiges Werkzeug, dennoch. Und so ist es auf jeden Fall etwas um den Kopf herum zu erhalten, weil Sie in der Lage zu schaffen ziemlich cool Programme mit Rekursion die ansonsten komplexe zu schreiben sein könnte wenn Sie mit Loops und Iteration sind. Ich bin Doug Lloyd. Dies ist CS50.