1
00:00:00,000 --> 00:00:05,860
>> [Musikwiedergabe]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Sie denken wahrscheinlich, dass
Code wird nur verwendet, um eine Aufgabe zu erfüllen.

3
00:00:09,530 --> 00:00:10,450
Sie schreiben es heraus.

4
00:00:10,450 --> 00:00:11,664
Es tut etwas.

5
00:00:11,664 --> 00:00:12,580
Das ist ziemlich viel es.

6
00:00:12,580 --> 00:00:13,160
>> Sie kompilieren.

7
00:00:13,160 --> 00:00:13,993
Sie führen Sie das Programm.

8
00:00:13,993 --> 00:00:15,370
Sie sind gut zu gehen.

9
00:00:15,370 --> 00:00:17,520
>> Aber es glauben oder nicht, wenn
Sie für eine lange Zeit zu codieren,

10
00:00:17,520 --> 00:00:20,550
Sie könnte in der Tat gekommen, um zu sehen
Code als etwas, das schön ist.

11
00:00:20,550 --> 00:00:23,275
Es löst ein Problem in
eine sehr interessante Art und Weise,

12
00:00:23,275 --> 00:00:26,510
oder es gibt einfach etwas wirklich
ordentlich über die Art, wie es aussieht.

13
00:00:26,510 --> 00:00:28,750
Sie werden sich vielleicht lachen
mich an, aber es ist wahr.

14
00:00:28,750 --> 00:00:31,530
Und Rekursion ist ein Weg,
diese Idee Art erhalten

15
00:00:31,530 --> 00:00:34,090
schöne, elegant aussehende Code.

16
00:00:34,090 --> 00:00:37,740
Es löst Probleme in einer Weise,
sind interessant, einfach zu visualisieren,

17
00:00:37,740 --> 00:00:39,810
und überraschend kurz.

18
00:00:39,810 --> 00:00:43,190
>> Die Art, wie Rekursion Werke
ist, eine rekursive Funktion

19
00:00:43,190 --> 00:00:49,291
wird als eine Funktion, die Anrufe definiert
sich als Teil der Ausführung.

20
00:00:49,291 --> 00:00:51,790
Das mag ein wenig seltsam,
und wir werden ein bisschen zu sehen

21
00:00:51,790 --> 00:00:53,750
etwa, wie das funktioniert in einem Augenblick.

22
00:00:53,750 --> 00:00:55,560
Aber noch einmal, diese
rekursive Prozeduren sind

23
00:00:55,560 --> 00:00:57,730
geht so elegant zu sein
denn sie gehen,

24
00:00:57,730 --> 00:01:00,410
um dieses Problem zu lösen, ohne
mit all diesen anderen Funktionen

25
00:01:00,410 --> 00:01:02,710
oder diese langen Schleifen.

26
00:01:02,710 --> 00:01:06,310
Sie finden, dass diese rekursive sehen
Verfahren gehen, um so kurz zu suchen.

27
00:01:06,310 --> 00:01:10,610
Und sie wirklich gehen, um
Ihr Code sehen viel schöner.

28
00:01:10,610 --> 00:01:12,560
>> Ich gebe Ihnen ein Beispiel geben
davon zu sehen, wie

29
00:01:12,560 --> 00:01:14,880
eine rekursive Prozedur könnte festgelegt werden.

30
00:01:14,880 --> 00:01:18,202
Also, wenn Sie mit diesen vertraut sind
von Math-Klasse vor vielen Jahren,

31
00:01:18,202 --> 00:01:20,910
Es gibt etwas, genannt
faktorielle Funktion, die normalerweise

32
00:01:20,910 --> 00:01:25,340
wie ein Ausrufezeichen, bezeichnet die
wird über alle positiven ganzen Zahlen definiert.

33
00:01:25,340 --> 00:01:28,850
Und die Art und Weise, dass n
Fakultät berechnet

34
00:01:28,850 --> 00:01:31,050
wird sie alle zu multiplizieren
die Zahlen weniger als

35
00:01:31,050 --> 00:01:33,750
oder gleich n together--
alle ganzen Zahlen weniger als

36
00:01:33,750 --> 00:01:34,880
oder gleich n zusammen.

37
00:01:34,880 --> 00:01:39,850
>> So 5 Fakultät ist 5-mal
4 mal 3 mal 2 mal 1.

38
00:01:39,850 --> 00:01:43,020
Und 4 Fakultät ist 4 mal
3 mal 2 mal 1 und so weiter.

39
00:01:43,020 --> 00:01:44,800
Sie erhalten die Idee.

40
00:01:44,800 --> 00:01:47,060
>> Als Programmierer, wissen wir nicht
n verwenden, Ausrufezeichen.

41
00:01:47,060 --> 00:01:51,840
Also werden wir die Fakultät zu definieren
Funktion als Tatsache des n.

42
00:01:51,840 --> 00:01:56,897
Und wir factorial verwenden, um zu erstellen
eine rekursive Lösung für ein Problem.

43
00:01:56,897 --> 00:01:59,230
Und ich denke, finden Sie vielleicht,
dass es viel mehr visuell

44
00:01:59,230 --> 00:02:02,380
attraktiv als die iterative
Version davon, die

45
00:02:02,380 --> 00:02:05,010
wir werden auch einen Blick auf in einem Augenblick.

46
00:02:05,010 --> 00:02:08,310
>> So, hier sind ein paar
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
über die factorial--
Fakultätsfunktion.

48
00:02:10,169 --> 00:02:13,090
Die Fakultät von 1, wie gesagt, ist 1.

49
00:02:13,090 --> 00:02:15,690
Die Fakultät von 2 2 mal 1.

50
00:02:15,690 --> 00:02:18,470
Die Fakultät von 3 3
mal 2 mal 1, und so weiter.

51
00:02:18,470 --> 00:02:20,810
Wir sprachen über 4 und 5 bereits.

52
00:02:20,810 --> 00:02:23,940
>> Aber ein Blick auf diese, ist nicht das wahr?

53
00:02:23,940 --> 00:02:28,220
Wird nicht von 2 factorial nur
2-fache der Fakultät von 1?

54
00:02:28,220 --> 00:02:31,130
Ich meine, die Fakultät 1 1 ist.

55
00:02:31,130 --> 00:02:34,940
Also warum können wir nicht einfach sagen, dass,
seit Fakultät von 2 2 mal 1,

56
00:02:34,940 --> 00:02:38,520
es ist wirklich nur 2 mal
die Fakultät von 1?

57
00:02:38,520 --> 00:02:40,900
>> Und dann die sich diese Idee,
ist nicht der Fakultät von 3

58
00:02:40,900 --> 00:02:44,080
nur 3-fache der Fakultät von 2?

59
00:02:44,080 --> 00:02:50,350
Und die Fakultät von 4 ist 4-mal
die Fakultät von 3, und so weiter?

60
00:02:50,350 --> 00:02:52,530
In der Tat die faktorielle
aus einer beliebigen Anzahl kann einfach

61
00:02:52,530 --> 00:02:54,660
wenn wir Art ausgedrückt werden
der Durchführung dieses heraus für immer.

62
00:02:54,660 --> 00:02:56,870
Wir können Art von verallgemeinern
die Fakultät Problem

63
00:02:56,870 --> 00:02:59,910
da es n-mal die
Fakultät von n minus 1.

64
00:02:59,910 --> 00:03:04,840
Es ist n-mal das Produkt
alle Zahlen kleiner als ich.

65
00:03:04,840 --> 00:03:08,890
>> Diese Idee, dies
Verallgemeinerung des Problems

66
00:03:08,890 --> 00:03:13,410
ermöglicht es uns, rekursiv
definieren die Fakultätsfunktion.

67
00:03:13,410 --> 00:03:15,440
Wenn Sie eine Funktion definieren
rekursiv, es gibt

68
00:03:15,440 --> 00:03:17,470
zwei Dinge, um ein Teil davon zu sein braucht.

69
00:03:17,470 --> 00:03:20,990
Sie müssen einen so genannten
Basisfall, der, wenn Sie es auslösen,

70
00:03:20,990 --> 00:03:22,480
wird die rekursive Prozess zu stoppen.

71
00:03:22,480 --> 00:03:25,300
>> Ansonsten eine Funktion, ruft
itself-- wie Sie vielleicht imagine--

72
00:03:25,300 --> 00:03:26,870
könnte ewig so weitergehen.

73
00:03:26,870 --> 00:03:29,047
Function die Funktion aufruft
ruft die Funktionsaufrufe

74
00:03:29,047 --> 00:03:30,380
Die Funktion ruft die Funktion.

75
00:03:30,380 --> 00:03:32,380
Wenn Sie nicht über einen Weg
um es zu stoppen, Ihr Programm

76
00:03:32,380 --> 00:03:34,760
effektiv geklebt werden
bei einer Endlosschleife.

77
00:03:34,760 --> 00:03:37,176
Es wird schließlich abstürzen,
denn es wird ein Speicherproblem.

78
00:03:37,176 --> 00:03:38,990
Aber das ist nicht der Punkt.

79
00:03:38,990 --> 00:03:42,210
>> Wir müssen einen anderen Weg, um zu stoppen
Dinge neben unserem Programm abstürzt,

80
00:03:42,210 --> 00:03:46,010
denn ein Programm, das abstürzt ist
wahrscheinlich nicht schön oder elegant.

81
00:03:46,010 --> 00:03:47,690
Und so haben wir nennen dies die Basisfall.

82
00:03:47,690 --> 00:03:50,610
Dies ist eine einfache Lösung,
für ein Problem, stoppt

83
00:03:50,610 --> 00:03:52,770
die rekursive Prozess auftritt.

84
00:03:52,770 --> 00:03:55,220
Also das ist ein Teil der
eine rekursive Funktion.

85
00:03:55,220 --> 00:03:56,820
>> Der zweite Teil ist die rekursive Fall.

86
00:03:56,820 --> 00:03:59,195
Und das ist, wo die Rekursion
tatsächlich stattfinden wird.

87
00:03:59,195 --> 00:04:02,200
Hier setzt die
Funktion selbst aufrufen.

88
00:04:02,200 --> 00:04:05,940
>> Es wird sich in genau das nicht nennen
die gleiche Art, wie es hieß.

89
00:04:05,940 --> 00:04:08,880
Es wird eine leichte Variation sein
das macht das Problem, es ist

90
00:04:08,880 --> 00:04:11,497
versuchen zu lösen, ein klein wenig kleiner.

91
00:04:11,497 --> 00:04:14,330
Aber es geht in der Regel den Schwarzen Peter
des Lösens der Masse der Lösung

92
00:04:14,330 --> 00:04:17,450
an einen anderen Anruf auf der ganzen Linie.

93
00:04:17,450 --> 00:04:20,290
>> Welche dieser Blicke
wie die Basisfall hier?

94
00:04:20,290 --> 00:04:25,384
Welcher dieser sieht aus wie die
einfachste Lösung für ein Problem?

95
00:04:25,384 --> 00:04:27,550
Wir haben eine Reihe von Fakultäten,
und wir werden weiterhin könnten

96
00:04:27,550 --> 00:04:30,470
gehen an-- 6, 7, 8, 9, 10, und so weiter.

97
00:04:30,470 --> 00:04:34,130
>> Aber eine dieser sieht aus wie eine
gutes Beispiel, um die Basis Fall sein.

98
00:04:34,130 --> 00:04:35,310
Es ist eine sehr einfache Lösung.

99
00:04:35,310 --> 00:04:37,810
Wir haben nicht um etwas Besonderes zu tun.

100
00:04:37,810 --> 00:04:40,560
>> Die Fakultät von 1 ist nur 1.

101
00:04:40,560 --> 00:04:42,790
Wir haben nicht zu einem zu tun
Multiplikation überhaupt.

102
00:04:42,790 --> 00:04:45,248
Es scheint, als ob wir
um zu versuchen, dieses Problem zu lösen,

103
00:04:45,248 --> 00:04:47,600
und wir müssen das stoppen
Rekursion irgendwo,

104
00:04:47,600 --> 00:04:50,610
wir wollen wahrscheinlich zu stoppen
es, wenn wir bekommen, um 1.

105
00:04:50,610 --> 00:04:54,580
Wir wollen nicht, dass, bevor stoppen.

106
00:04:54,580 --> 00:04:56,660
>> Also, wenn wir definieren
unsere Fakultätsfunktion,

107
00:04:56,660 --> 00:04:58,690
hier ist ein Gerüst für
wie wir das tun.

108
00:04:58,690 --> 00:05:03,110
Wir müssen in diesen beiden things-- Stecker
das Basismodell und der rekursiven Fall.

109
00:05:03,110 --> 00:05:04,990
Was ist in der Basisfall?

110
00:05:04,990 --> 00:05:10,150
Wenn n gleich 1 ist, zurückzukehren 1-- das ist,
ein wirklich einfaches Problem zu lösen.

111
00:05:10,150 --> 00:05:11,890
>> Die Fakultät von 1 1.

112
00:05:11,890 --> 00:05:13,860
Es ist nicht 1 mal nichts.

113
00:05:13,860 --> 00:05:15,020
Es ist nur 1.

114
00:05:15,020 --> 00:05:17,170
Es ist eine sehr einfache Tatsache.

115
00:05:17,170 --> 00:05:19,620
Und damit unsere Basis Fall sein.

116
00:05:19,620 --> 00:05:24,730
Wenn wir uns übergeben 1 in diesem
Funktion, werden wir nur 1 zurückzukehren.

117
00:05:24,730 --> 00:05:27,320
>> Was ist die rekursive
Fall wohl aussehen?

118
00:05:27,320 --> 00:05:32,445
Für jede andere Zahl
außer 1, was ist das Muster?

119
00:05:32,445 --> 00:05:35,780
Nun, wenn wir nehmen
die Fakultät von n,

120
00:05:35,780 --> 00:05:38,160
es ist n mal die Fakultät von n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Wenn wir nehmen die Fakultät 3,
es ist 3-fache der Fakultät 3 minus 1,

122
00:05:42,130 --> 00:05:43,070
oder 2.

123
00:05:43,070 --> 00:05:47,330
Und so, wenn wir nicht
Blick auf 1, sonst

124
00:05:47,330 --> 00:05:51,710
Rück n mal die
Fakultät von n minus 1.

125
00:05:51,710 --> 00:05:53,210
Es ist ziemlich einfach.

126
00:05:53,210 --> 00:05:57,360
>> Und aus Gründen der mit geringfügig
sauberer und elegant-Code,

127
00:05:57,360 --> 00:06:01,440
wissen, dass, wenn wir Einzelleitungsschleifen
oder Single-Line-bedingte Verzweigungen,

128
00:06:01,440 --> 00:06:04,490
können wir all das loswerden
geschweiften Klammern um sie herum.

129
00:06:04,490 --> 00:06:06,850
So können wir dies, dies zu konsolidieren.

130
00:06:06,850 --> 00:06:09,640
Dies hat genau die gleiche
Funktionen wie diese.

131
00:06:09,640 --> 00:06:13,850
>> Ich bin einfach nur Wegnehmen der geschweiften
Hosenträger, denn es gibt nur eine Zeile

132
00:06:13,850 --> 00:06:18,500
innerhalb dieser bedingte Verzweigungen.

133
00:06:18,500 --> 00:06:21,160
Das sind also identisch verhalten.

134
00:06:21,160 --> 00:06:23,800
Wenn n gleich 1 ist, gib 1.

135
00:06:23,800 --> 00:06:28,351
N mal Ansonsten zurückkehren
die Fakultät von n minus 1.

136
00:06:28,351 --> 00:06:29,850
So machen wir das Problem kleiner.

137
00:06:29,850 --> 00:06:33,850
Wenn n beginnt als 5, sind wir zu gehen
Rück 5 mal die Fakultät 4.

138
00:06:33,850 --> 00:06:37,100
Und wir werden gleich sehen, wenn wir sprechen
über den Anruf stack-- in einem anderen Video

139
00:06:37,100 --> 00:06:39,390
wo wir über das reden
rufen stack-- wir lernen,

140
00:06:39,390 --> 00:06:41,630
warum genau dieser Prozess funktioniert.

141
00:06:41,630 --> 00:06:46,970
>> Aber während Fakultät von 5 sagt,
Rück 5 mal Fakultät von 4, und 4

142
00:06:46,970 --> 00:06:49,710
wird sagen, OK, gut, Rück
4 mal die Fakultät von 3.

143
00:06:49,710 --> 00:06:51,737
Und wie Sie sehen können, sind wir
Art der Annäherung an 1.

144
00:06:51,737 --> 00:06:53,820
Wir nähern und
näher an das Basisszenario.

145
00:06:53,820 --> 00:06:58,180
>> Und wenn wir uns auf den Basisfall,
alle vorherigen Funktionen

146
00:06:58,180 --> 00:07:00,540
haben die Antwort sie suchten.

147
00:07:00,540 --> 00:07:03,900
Fakultät 2 sagte Rückkehr
2-fache der Fakultät von 1.

148
00:07:03,900 --> 00:07:06,760
Nun, Fakultät von 1 ergibt 1.

149
00:07:06,760 --> 00:07:10,090
So die Forderung nach factorial
von 2 kann 2 mal 1 zurückzukehren,

150
00:07:10,090 --> 00:07:13,980
und geben Sie das zurück zu Fakultät
3, die darauf wartet, zu diesem Ergebnis.

151
00:07:13,980 --> 00:07:17,110
>> Und dann ist es berechnen
das Ergebnis, 3-mal 2 6,

152
00:07:17,110 --> 00:07:18,907
und geben Sie es zurück zu Fakultät von 4.

153
00:07:18,907 --> 00:07:20,740
Und wieder haben wir ein
Video auf der Call-Stack

154
00:07:20,740 --> 00:07:23,810
wenn dies ein wenig dargestellt
mehr als das, was ich jetzt sage.

155
00:07:23,810 --> 00:07:25,300
Aber das ist es.

156
00:07:25,300 --> 00:07:29,300
Dies allein ist die Lösung
Berechnung der Fakultät einer Zahl.

157
00:07:29,300 --> 00:07:31,527
>> Es ist nur vier Zeilen Code.

158
00:07:31,527 --> 00:07:32,610
Das ist ziemlich cool, oder?

159
00:07:32,610 --> 00:07:35,480
Es ist irgendwie sexy.

160
00:07:35,480 --> 00:07:38,580
>> So im Allgemeinen, aber nicht
immer, eine rekursive Funktion

161
00:07:38,580 --> 00:07:41,190
kann eine Schleife in einer zu ersetzen
Nicht-rekursive Funktion.

162
00:07:41,190 --> 00:07:46,100
Also hier, nebeneinander, ist die iterative
Version der Fakultätsfunktion.

163
00:07:46,100 --> 00:07:49,650
Beide dieser calculate
genau die gleiche Sache.

164
00:07:49,650 --> 00:07:52,170
>> Beide berechnen die Fakultät von n.

165
00:07:52,170 --> 00:07:54,990
Die Version auf der linken
Rekursion verwendet, es zu tun.

166
00:07:54,990 --> 00:07:58,320
Die Version auf der rechten
Iteration verwendet, es zu tun.

167
00:07:58,320 --> 00:08:02,050
>> Und beachtet, müssen wir erklären,
eine Variable eine ganze Zahl Produkt.

168
00:08:02,050 --> 00:08:02,940
Und dann haben wir Schleife.

169
00:08:02,940 --> 00:08:06,790
Sofern n größer als 0 ist, haben wir
halten Multiplikation dieses Produkts durch n

170
00:08:06,790 --> 00:08:09,890
und Dekrementieren n bis
berechnen wir das Produkt.

171
00:08:09,890 --> 00:08:14,600
Also diese beiden Funktionen wieder,
tun genau das Gleiche.

172
00:08:14,600 --> 00:08:19,980
Aber sie tun es nicht in
genau die gleiche Weise.

173
00:08:19,980 --> 00:08:22,430
>> Nun ist es möglich,
haben mehr als eine Basis

174
00:08:22,430 --> 00:08:25,770
Gehäuse oder mehreren
rekursiven Fall kann in Abhängigkeit

175
00:08:25,770 --> 00:08:27,670
ab, was Ihre Funktion wird versuchen, zu tun.

176
00:08:27,670 --> 00:08:31,650
Sie sind nicht unbedingt nur beschränkt
eine einzige Basisfall oder eine einzelne rekursive

177
00:08:31,650 --> 00:08:32,370
Fall.

178
00:08:32,370 --> 00:08:35,320
So ein Beispiel für etwas,
mit mehreren Basis Fällen

179
00:08:35,320 --> 00:08:37,830
könnte die this--
Fibonacci-Zahlenfolge.

180
00:08:37,830 --> 00:08:41,549
>> Sie können aus erinnern
Grundschule Tage

181
00:08:41,549 --> 00:08:45,740
dass die Fibonacci-Folge definiert
wie this-- das erste Element 0.

182
00:08:45,740 --> 00:08:46,890
Das zweite Element 1.

183
00:08:46,890 --> 00:08:49,230
Beide von denen sind nur per Definition.

184
00:08:49,230 --> 00:08:55,920
>> Dann jeden zweiten Element definiert ist
als Summe von n minus 1 und n minus 2.

185
00:08:55,920 --> 00:09:00,330
Also das dritte Element
wäre 0 plus 1 ist 1.

186
00:09:00,330 --> 00:09:03,280
Und dann wird das vierte Element
würde das zweite Element 1 sein kann,

187
00:09:03,280 --> 00:09:06,550
plus dem dritten Element 1.

188
00:09:06,550 --> 00:09:08,507
Und das wäre 2 sein.

189
00:09:08,507 --> 00:09:09,340
Und so weiter und so fort.

190
00:09:09,340 --> 00:09:11,680
>> Also in diesem Fall, wir haben zwei Basis Fällen.

191
00:09:11,680 --> 00:09:14,850
Wenn n gleich 1, 0 zurück.

192
00:09:14,850 --> 00:09:18,560
Wenn n gleich 2 ist, gib 1.

193
00:09:18,560 --> 00:09:25,930
Andernfalls zurückkehren Fibonacci von n
minus 1 plus Fibonacci n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Also das ist, mehrere Basis Fällen.

195
00:09:27,180 --> 00:09:29,271
Wie sieht es mehrere rekursive Fällen?

196
00:09:29,271 --> 00:09:31,520
Nun, es ist etwas,
genannt Collatz-Vermutung.

197
00:09:31,520 --> 00:09:34,630
Ich werde mich nicht zu sagen,
Sie wissen, was das ist,

198
00:09:34,630 --> 00:09:38,170
denn es ist wirklich unsere letzte
Problem für diese bestimmte Video.

199
00:09:38,170 --> 00:09:43,220
Und es ist unsere Übung
zusammen zu arbeiten auf.

200
00:09:43,220 --> 00:09:46,760
>> Also hier ist was die
Collatz Conjecture ist--

201
00:09:46,760 --> 00:09:48,820
Es gilt für jede positive ganze Zahl ist.

202
00:09:48,820 --> 00:09:51,500
Und spekuliert, dass es
immer möglich, um wieder

203
00:09:51,500 --> 00:09:55,060
1, wenn Sie die folgenden Schritte aus.

204
00:09:55,060 --> 00:09:57,560
Wenn n 1 ist, zu stoppen.

205
00:09:57,560 --> 00:10:00,070
Wir haben wieder auf 1 hat, wenn n 1 ist.

206
00:10:00,070 --> 00:10:05,670
>> Andernfalls durch diese gehen
Prozess erneut von n durch 2 geteilt.

207
00:10:05,670 --> 00:10:08,200
Und sehen, wenn Sie zurück zu 1 bekommen können.

208
00:10:08,200 --> 00:10:13,260
Andernfalls, wenn n ungerade ist, durchlaufen
dieser Prozess wieder auf 3 n + 1,

209
00:10:13,260 --> 00:10:15,552
oder 3 mal n plus 1.

210
00:10:15,552 --> 00:10:17,010
Hier haben wir also eine einzige Basisfall.

211
00:10:17,010 --> 00:10:18,430
Wenn n gleich 1 ist, zu stoppen.

212
00:10:18,430 --> 00:10:20,230
Wir sind nicht dabei jede weitere Rekursion.

213
00:10:20,230 --> 00:10:23,730
>> Aber wir haben zwei rekursive Fällen.

214
00:10:23,730 --> 00:10:28,750
Wenn n gerade ist, machen wir einen rekursiven
Fall calling n durch 2 geteilt.

215
00:10:28,750 --> 00:10:33,950
Wenn n ungerade ist, wir tun, eine andere
rekursiven Fall auf 3 mal n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Und so ist das Ziel für dieses Video
um eine zweite zu nehmen, unterbrechen Sie das Video,

217
00:10:39,120 --> 00:10:42,440
und versuchen, dies schreibe
rekursive Funktion Collatz

218
00:10:42,440 --> 00:10:47,640
wo Sie übergeben einen Wert n und
berechnet er, wie viele Schritte es

219
00:10:47,640 --> 00:10:52,430
dauert, bis 1, wenn man vom n starten
und folgen Sie diese Schritte oben.

220
00:10:52,430 --> 00:10:56,660
Wenn n 1 ist, dauert es 0 Schritten.

221
00:10:56,660 --> 00:11:00,190
Ansonsten ist es zu gehen
einen Schritt zzgl jedoch

222
00:11:00,190 --> 00:11:06,200
viele Schritte nimmt es entweder N
geteilt durch 2, wenn n gerade ist, oder 3 n plus 1

223
00:11:06,200 --> 00:11:08,100
wenn n ungerade ist.

224
00:11:08,100 --> 00:11:11,190
>> Nun, ich habe auf dem Bildschirm ablegen
ein paar Test Dinge für Sie,

225
00:11:11,190 --> 00:11:15,690
ein paar Tests Fällen für Sie, um zu sehen,
was diese verschiedenen Collatz Zahlen sind,

226
00:11:15,690 --> 00:11:17,440
und auch eine Darstellung
der Schritte,

227
00:11:17,440 --> 00:11:20,390
brauchen, um durch, so dass Sie weg sein
Art sehen, diesen Prozess in Aktion.

228
00:11:20,390 --> 00:11:24,222
Also, wenn n gleich
1, Collatz von n 0.

229
00:11:24,222 --> 00:11:26,180
Sie müssen nicht zu tun,
alles tun, um wieder auf 1 zu bekommen.

230
00:11:26,180 --> 00:11:27,600
Bist du schon da.

231
00:11:27,600 --> 00:11:30,550
>> Wenn n 2 ist, dauert es
einen Schritt, um bis 1 zu bekommen.

232
00:11:30,550 --> 00:11:31,810
Sie beginnen mit 2.

233
00:11:31,810 --> 00:11:33,100
Nun, 2 nicht gleich 1.

234
00:11:33,100 --> 00:11:36,580
Also, es wird ein Schritt sein,
zzgl jedoch viele Schritte es

235
00:11:36,580 --> 00:11:38,015
nimmt n durch 2 geteilt.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 geteilt durch 2 1 ist.

238
00:11:42,910 --> 00:11:47,200
So einen Schritt zzgl jedoch dauert es
viele Schritte, die für 1.

239
00:11:47,200 --> 00:11:49,720
1 nimmt Null Schritte.

240
00:11:49,720 --> 00:11:52,370
>> 3, wie Sie sehen können, gibt es
durchaus ein paar Schritte.

241
00:11:52,370 --> 00:11:53,590
Sie gehen vom 3.

242
00:11:53,590 --> 00:11:56,710
Und dann haben Sie zu gehen
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Es dauert sieben Schritte, um wieder auf 1 zu bekommen.

244
00:11:58,804 --> 00:12:01,220
Und wie Sie sehen können, gibt es eine
paar andere Testfälle hier

245
00:12:01,220 --> 00:12:02,470
zu testen Sie Ihr Programm.

246
00:12:02,470 --> 00:12:03,970
Also noch einmal, unterbrechen Sie das Video.

247
00:12:03,970 --> 00:12:09,210
Und ich werde gehen nun zurück zu springen
was die eigentliche Prozess ist hier,

248
00:12:09,210 --> 00:12:11,390
was diese Vermutung.

249
00:12:11,390 --> 00:12:14,140
>> Sehen Sie, wenn Sie herausfinden können
wie Collatz von n zu definieren

250
00:12:14,140 --> 00:12:19,967
so daß es berechnet, wie viele
Schritte es braucht, um auf 1 zu bekommen.

251
00:12:19,967 --> 00:12:23,050
Hoffentlich können Sie das Video angehalten haben
und Sie sind nicht nur darauf warten, für mich

252
00:12:23,050 --> 00:12:25,820
dass Sie hier die Antwort geben.

253
00:12:25,820 --> 00:12:29,120
Aber wenn Sie sind, nun ja,
hier ist die Antwort sowieso.

254
00:12:29,120 --> 00:12:33,070
>> Also hier ist eine mögliche Definition
der Collatz-Funktion.

255
00:12:33,070 --> 00:12:35,610
Unsere Basis Fall-- wenn n
gleich 1 ist, kehren wir 0.

256
00:12:35,610 --> 00:12:38,250
Es braucht nicht jeder
Schritte, um wieder auf 1 zu bekommen.

257
00:12:38,250 --> 00:12:42,710
>> Ansonsten haben wir zwei rekursive cases--
eine für ungerade Zahlen und eine für ungerade.

258
00:12:42,710 --> 00:12:47,164
So wie ich das testen gerade Zahlen
ist zu prüfen, ob n mod 2 gleich 0 ist.

259
00:12:47,164 --> 00:12:49,080
Dies ist im Grunde wieder
die Frage zu stellen,

260
00:12:49,080 --> 00:12:54,050
wenn Sie, was mod ist-- erinnern, wenn ich
divide n von 2 gibt es keinen Rest?

261
00:12:54,050 --> 00:12:55,470
Das wäre eine gerade Zahl sein.

262
00:12:55,470 --> 00:13:01,370
>> Und so, wenn n mod 2 gleich 0 ist
Tests ist dies eine gerade Zahl ist.

263
00:13:01,370 --> 00:13:04,250
Wenn dem so ist, möchte ich zurück 1,
denn dies ist definitiv

264
00:13:04,250 --> 00:13:09,270
nehmen einen Schritt zzgl Collatz von
was auch immer Nummer ist die Hälfte von mir.

265
00:13:09,270 --> 00:13:13,910
Ansonsten möchte ich zurück 1
zzgl Collatz von 3 mal n plus 1.

266
00:13:13,910 --> 00:13:16,060
Das war die andere
rekursive Schritt, den wir

267
00:13:16,060 --> 00:13:19,470
könnte zu ergreifen, um die Berechnung
Collatz-- die Anzahl der Schritte

268
00:13:19,470 --> 00:13:22,610
es braucht, um wieder
1 einer Nummer versehen.

269
00:13:22,610 --> 00:13:24,610
Also hoffentlich dieses Beispiel
hat dir ein wenig

270
00:13:24,610 --> 00:13:26,620
ein Geschmack von rekursive Prozeduren.

271
00:13:26,620 --> 00:13:30,220
Ich hoffe, dass du Code ein
wenig schöner, wenn implementiert

272
00:13:30,220 --> 00:13:32,760
in einem eleganten, rekursive Art und Weise.

273
00:13:32,760 --> 00:13:35,955
Aber selbst wenn nicht, ist eine Rekursion
wirklich leistungsfähiges Werkzeug, dennoch.

274
00:13:35,955 --> 00:13:38,330
Und so ist es auf jeden Fall etwas
um den Kopf herum zu erhalten,

275
00:13:38,330 --> 00:13:41,360
weil Sie in der Lage zu schaffen
ziemlich cool Programme mit Rekursion

276
00:13:41,360 --> 00:13:45,930
die ansonsten komplexe zu schreiben sein könnte
wenn Sie mit Loops und Iteration sind.

277
00:13:45,930 --> 00:13:46,980
Ich bin Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Dies ist CS50.

279
00:13:48,780 --> 00:13:50,228