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

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Pewnie myślisz, że
Kod jest tylko używane do wykonania zadania.

3
00:00:09,530 --> 00:00:10,450
Możesz napisać go.

4
00:00:10,450 --> 00:00:11,664
To coś robi.

5
00:00:11,664 --> 00:00:12,580
To dość dużo.

6
00:00:12,580 --> 00:00:13,160
>> Go skompilować.

7
00:00:13,160 --> 00:00:13,993
Uruchomieniu programu.

8
00:00:13,993 --> 00:00:15,370
Jesteś dobry, aby przejść.

9
00:00:15,370 --> 00:00:17,520
>> Ale wierzcie lub nie, jeśli
kodować przez dłuższy czas,

10
00:00:17,520 --> 00:00:20,550
rzeczywiście może przyjść, aby zobaczyć
Kod jako coś, co jest piękne.

11
00:00:20,550 --> 00:00:23,275
Rozwiązuje problem
bardzo ciekawy sposób,

12
00:00:23,275 --> 00:00:26,510
czy jest coś naprawdę
schludny temat jej wyglądu.

13
00:00:26,510 --> 00:00:28,750
Można się śmiać
na mnie, ale to prawda.

14
00:00:28,750 --> 00:00:31,530
I rekurencja jest jeden sposób,
do sortowania się ten pomysł

15
00:00:31,530 --> 00:00:34,090
z pięknym, eleganckim wyglądzie kod.

16
00:00:34,090 --> 00:00:37,740
Rozwiązuje to problem w taki sposób, aby
są ciekawe, łatwe do wizualizacji,

17
00:00:37,740 --> 00:00:39,810
i zaskakująco krótka.

18
00:00:39,810 --> 00:00:43,190
>> Prace sposób rekurencja
jest rekurencyjna funkcja

19
00:00:43,190 --> 00:00:49,291
jest określona jako funkcja, która wywołuje
Sam w ramach jego realizacji.

20
00:00:49,291 --> 00:00:51,790
To może wydawać się trochę dziwne,
i zobaczymy trochę

21
00:00:51,790 --> 00:00:53,750
o tym, jak to działa w jednej chwili.

22
00:00:53,750 --> 00:00:55,560
Ale znowu, te
procedury rekurencyjne są

23
00:00:55,560 --> 00:00:57,730
będzie tak eleganckie
bo będą

24
00:00:57,730 --> 00:01:00,410
rozwiązać ten problem bez
mając te wszystkie inne funkcje

25
00:01:00,410 --> 00:01:02,710
lub te długie pętle.

26
00:01:02,710 --> 00:01:06,310
Zobaczysz, że to rekurencyjny
Procedury będą wyglądać tak krótko.

27
00:01:06,310 --> 00:01:10,610
A tak naprawdę idą do
Twój kod wyglądać o wiele piękniej.

28
00:01:10,610 --> 00:01:12,560
>> Dam ci przykład
tego, w jaki sposób

29
00:01:12,560 --> 00:01:14,880
procedura rekurencyjna może być zdefiniowana.

30
00:01:14,880 --> 00:01:18,202
Więc jeśli jesteś obeznany z tym
z lekcji matematyki wiele lat temu,

31
00:01:18,202 --> 00:01:20,910
Jest coś, co nazywa się
Funkcja silni, która jest zwykle

32
00:01:20,910 --> 00:01:25,340
oznaczany jako wykrzyknikiem, który
jest określona w stosunku do wszystkich dodatnich liczb całkowitych.

33
00:01:25,340 --> 00:01:28,850
A sposób, że n
silnia jest obliczana

34
00:01:28,850 --> 00:01:31,050
jest pomnożyć wszystkie
liczby poniżej

35
00:01:31,050 --> 00:01:33,750
lub równą n together--
wszystkie liczby całkowite mniej niż

36
00:01:33,750 --> 00:01:34,880
lub równą n razem.

37
00:01:34,880 --> 00:01:39,850
>> Więc 5 silnia jest 5 razy
4 razy 3 razy 2 razy 1.

38
00:01:39,850 --> 00:01:43,020
I 4 silnia jest 4 razy
3, 2 razy po 1 i tak dalej.

39
00:01:43,020 --> 00:01:44,800
Masz pomysł.

40
00:01:44,800 --> 00:01:47,060
>> Jako programiści, my nie
używać n, wykrzyknik.

41
00:01:47,060 --> 00:01:51,840
Będziemy więc zdefiniować silnia
Funkcja jako fakt n.

42
00:01:51,840 --> 00:01:56,897
I użyjemy silni, aby utworzyć
rekurencyjny rozwiązanie problemu.

43
00:01:56,897 --> 00:01:59,230
I myślę, że może się okazać,
że jest to dużo bardziej wizualnie

44
00:01:59,230 --> 00:02:02,380
atrakcyjne niż iteracyjny
Wersja ta,

45
00:02:02,380 --> 00:02:05,010
Będziemy również przyjrzeć się w jednej chwili.

46
00:02:05,010 --> 00:02:08,310
>> Więc oto kilka
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
o factorial--
silnia funkcji.

48
00:02:10,169 --> 00:02:13,090
Silnia 1, jak powiedziałem, to 1.

49
00:02:13,090 --> 00:02:15,690
Silnia 2 jest 2 razy 1.

50
00:02:15,690 --> 00:02:18,470
Silnia 3 wynosi 3
razy 2 razy po 1 i tak dalej.

51
00:02:18,470 --> 00:02:20,810
Rozmawialiśmy o 4 i 5 już.

52
00:02:20,810 --> 00:02:23,940
>> Ale patrząc na to, nie jest to prawda?

53
00:02:23,940 --> 00:02:28,220
Nie jest silnia 2 tylko
2 razy silnia 1?

54
00:02:28,220 --> 00:02:31,130
To znaczy, silnia 1 to 1.

55
00:02:31,130 --> 00:02:34,940
Więc dlaczego nie możemy po prostu powiedzieć, że,
od silnia 2 jest 2 razy 1,

56
00:02:34,940 --> 00:02:38,520
to naprawdę tylko 2 razy
silnia 1?

57
00:02:38,520 --> 00:02:40,900
>> A następnie rozszerzenie tego pojęcia,
nie jest silnia 3

58
00:02:40,900 --> 00:02:44,080
tylko 3 razy silnia 2?

59
00:02:44,080 --> 00:02:50,350
I silnia 4 jest 4 razy
silnia 3, i tak dalej?

60
00:02:50,350 --> 00:02:52,530
W rzeczywistości, silnia
z dowolnej liczby można po prostu

61
00:02:52,530 --> 00:02:54,660
być wyrażona, jeśli my niby
od przeprowadzenia tego na zawsze.

62
00:02:54,660 --> 00:02:56,870
Możemy rodzaj uogólnienia
silnia problemem

63
00:02:56,870 --> 00:02:59,910
jak to n razy
silnia n minus 1.

64
00:02:59,910 --> 00:03:04,840
To N razy produktem
wszystkie numery mniej niż mnie.

65
00:03:04,840 --> 00:03:08,890
>> Ten pomysł, to
uogólnienie problemu,

66
00:03:08,890 --> 00:03:13,410
Pozwala nam to rekurencyjnie
zdefiniować funkcję silni.

67
00:03:13,410 --> 00:03:15,440
Podczas definiowania funkcji
rekurencyjnie, nie

68
00:03:15,440 --> 00:03:17,470
Dwie rzeczy, które muszą być jego częścią.

69
00:03:17,470 --> 00:03:20,990
Trzeba mieć coś nazywa się
wariant podstawowy, który, kiedy wyzwolić go,

70
00:03:20,990 --> 00:03:22,480
zatrzyma proces rekurencyjny.

71
00:03:22,480 --> 00:03:25,300
>> W przeciwnym razie funkcja, która zwraca
itself-- jak można imagine--

72
00:03:25,300 --> 00:03:26,870
może trwać wiecznie.

73
00:03:26,870 --> 00:03:29,047
Funkcja wywołuje funkcję
wzywa do wywołania funkcji

74
00:03:29,047 --> 00:03:30,380
funkcja wywołuje funkcję.

75
00:03:30,380 --> 00:03:32,380
Jeśli nie ma sposobu
go zatrzymać, program

76
00:03:32,380 --> 00:03:34,760
będzie skutecznie zatrzymany
w nieskończonej pętli.

77
00:03:34,760 --> 00:03:37,176
Zawiesisz w końcu,
ponieważ będzie to zabraknie pamięci.

78
00:03:37,176 --> 00:03:38,990
Ale, że o to chodzi.

79
00:03:38,990 --> 00:03:42,210
>> Musimy mieć jakiś inny sposób, aby zatrzymać
rzeczy oprócz naszego programu upaść,

80
00:03:42,210 --> 00:03:46,010
ponieważ program, który zawiesza się
Prawdopodobnie nie piękne i eleganckie.

81
00:03:46,010 --> 00:03:47,690
I tak nazywamy to wariant podstawowy.

82
00:03:47,690 --> 00:03:50,610
Jest to proste rozwiązanie
do problemu, który zatrzymuje

83
00:03:50,610 --> 00:03:52,770
Proces rekurencyjne występowaniu.

84
00:03:52,770 --> 00:03:55,220
Więc to jest jedna część
Funkcja rekurencyjna.

85
00:03:55,220 --> 00:03:56,820
>> Druga część jest rekurencyjna przypadek.

86
00:03:56,820 --> 00:03:59,195
I to jest, gdzie rekurencji
ten rzeczywiście nastąpi.

87
00:03:59,195 --> 00:04:02,200
To jest, gdy
Funkcja będzie nazywać się.

88
00:04:02,200 --> 00:04:05,940
>> To nie będzie nazywać się w dokładnie
taki sam sposób, w jaki został powołany.

89
00:04:05,940 --> 00:04:08,880
To będzie niewielkie zmiany
sprawia, że ​​problem jest to

90
00:04:08,880 --> 00:04:11,497
próbuje rozwiązać malusieńki nieco mniejsze.

91
00:04:11,497 --> 00:04:14,330
Ale na ogół przechodzi złotówki
rozwiązując masę roztworu

92
00:04:14,330 --> 00:04:17,450
do innego połączenia w dół.

93
00:04:17,450 --> 00:04:20,290
>> Który z tych strojów
jak przypadku bazowego tutaj?

94
00:04:20,290 --> 00:04:25,384
Który z nich wygląda jak
Najprostsze rozwiązanie problemu?

95
00:04:25,384 --> 00:04:27,550
Mamy kilka silni,
i mogliśmy kontynuować

96
00:04:27,550 --> 00:04:30,470
dzieje on-- 6, 7, 8, 9, 10, i tak dalej.

97
00:04:30,470 --> 00:04:34,130
>> Ale jeden z nich wygląda jak
Dobrym przykładem będzie wariant podstawowy.

98
00:04:34,130 --> 00:04:35,310
To bardzo proste rozwiązanie.

99
00:04:35,310 --> 00:04:37,810
Nie musimy robić nic szczególnego.

100
00:04:37,810 --> 00:04:40,560
>> Silnia 1 jest tylko jeden.

101
00:04:40,560 --> 00:04:42,790
Nie mamy zrobić dowolny
Mnożenie w ogóle.

102
00:04:42,790 --> 00:04:45,248
Wydaje się, że jeśli mamy
aby spróbować rozwiązać ten problem,

103
00:04:45,248 --> 00:04:47,600
i musimy się zatrzymać
Rekurencja gdzieś,

104
00:04:47,600 --> 00:04:50,610
prawdopodobnie chce się zatrzymać
że gdy mamy do 1.

105
00:04:50,610 --> 00:04:54,580
Nie chcemy, aby zatrzymać przed tym.

106
00:04:54,580 --> 00:04:56,660
>> Więc jeśli mamy definiowania
nasza funkcja silnia,

107
00:04:56,660 --> 00:04:58,690
oto szkielet dla
w jaki sposób możemy to zrobić.

108
00:04:58,690 --> 00:05:03,110
Musimy podłączyć tych dwóch things--
wariant podstawowy, a rekurencyjne przypadek.

109
00:05:03,110 --> 00:05:04,990
Co znajduje się wariant podstawowy?

110
00:05:04,990 --> 00:05:10,150
Jeśli n jest równe 1, to powrót 1--
bardzo prosty do rozwiązania problemem.

111
00:05:10,150 --> 00:05:11,890
>> Silnia 1 to 1.

112
00:05:11,890 --> 00:05:13,860
To nie 1 razy cokolwiek.

113
00:05:13,860 --> 00:05:15,020
To tylko jeden.

114
00:05:15,020 --> 00:05:17,170
To bardzo łatwe fakt.

115
00:05:17,170 --> 00:05:19,620
I tak, że może być naszym wariant podstawowy.

116
00:05:19,620 --> 00:05:24,730
Jeśli przejdzie 1 do tego
Funkcja, po prostu zwraca 1.

117
00:05:24,730 --> 00:05:27,320
>> Jaka jest rekurencyjna
Sprawa prawdopodobnie wyglądać?

118
00:05:27,320 --> 00:05:32,445
Dla każdego innego numeru
oprócz 1, co jest wzór?

119
00:05:32,445 --> 00:05:35,780
Cóż, jeśli bierzemy
silnia n,

120
00:05:35,780 --> 00:05:38,160
To n razy silnia n minus 1.

121
00:05:38,160 --> 00:05:42,130
>> Jeśli bierzemy silni 3,
to 3 razy silnia 3 minus 1,

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

123
00:05:43,070 --> 00:05:47,330
I tak, jeśli nie jesteśmy
patrząc na 1, w przeciwnym wypadku

124
00:05:47,330 --> 00:05:51,710
powrót n razy
silnia n minus 1.

125
00:05:51,710 --> 00:05:53,210
To całkiem proste.

126
00:05:53,210 --> 00:05:57,360
>> I w imię konieczności nieznacznie
czystsze i bardziej Kod elegancki,

127
00:05:57,360 --> 00:06:01,440
wiedzą, że jeśli mamy pętle jednoliniowy
lub jednoliniowy skoków warunkowych,

128
00:06:01,440 --> 00:06:04,490
możemy pozbyć wszystkie z
nawiasy klamrowe wokół nich.

129
00:06:04,490 --> 00:06:06,850
Więc możemy skonsolidować to do tego.

130
00:06:06,850 --> 00:06:09,640
To jest dokładnie to samo
funkcjonalność jak ten.

131
00:06:09,640 --> 00:06:13,850
>> Ja tylko odbierając kręcone
szelki, bo jest tylko jedna linia

132
00:06:13,850 --> 00:06:18,500
wewnątrz tych oddziałów warunkowych.

133
00:06:18,500 --> 00:06:21,160
Więc te zachowują się identycznie.

134
00:06:21,160 --> 00:06:23,800
Jeśli n jest równe 1, powrót 1.

135
00:06:23,800 --> 00:06:28,351
W przeciwnym razie zwraca n razy
silnia n minus 1.

136
00:06:28,351 --> 00:06:29,850
Więc robimy problem mniejszy.

137
00:06:29,850 --> 00:06:33,850
Jeśli n zaczyna się jak 5, będziemy
powrót 5 razy silni 4.

138
00:06:33,850 --> 00:06:37,100
I zobaczymy, w chwili, gdy mówimy
o stack-- połączeń w innym wideo

139
00:06:37,100 --> 00:06:39,390
gdzie mówimy o
zadzwoń stack-- dowiemy się

140
00:06:39,390 --> 00:06:41,630
o tym, dlaczego działa dokładnie ten proces.

141
00:06:41,630 --> 00:06:46,970
>> Ale podczas silnia 5 mówi
powrót 5 razy silnia 4 i 4

142
00:06:46,970 --> 00:06:49,710
powie, dobrze, dobrze, powrót
4 razy silnia 3.

143
00:06:49,710 --> 00:06:51,737
I jak widać, jesteśmy
rodzaj zbliża 1.

144
00:06:51,737 --> 00:06:53,820
Jesteśmy coraz bliżej i
bliżej tym przypadku bazowego.

145
00:06:53,820 --> 00:06:58,180
>> I raz trafiliśmy w sprawę podstawową,
wszystkich poprzednich funkcji

146
00:06:58,180 --> 00:07:00,540
ma odpowiedzi szukali.

147
00:07:00,540 --> 00:07:03,900
Silnia 2 mówił powrót
2 razy silnia 1.

148
00:07:03,900 --> 00:07:06,760
Cóż, silnia 1 Zwraca 1.

149
00:07:06,760 --> 00:07:10,090
Tak więc wezwanie do silnia
z 2 może powrócić 2 razy 1,

150
00:07:10,090 --> 00:07:13,980
i daj to z powrotem do silni
3, który czeka na tego wyniku.

151
00:07:13,980 --> 00:07:17,110
>> I wtedy można obliczyć
jego wynik, 3 razy 2 jest 6,

152
00:07:17,110 --> 00:07:18,907
i oddać silni 4.

153
00:07:18,907 --> 00:07:20,740
I znowu mamy
wideo na stosie wywołań

154
00:07:20,740 --> 00:07:23,810
gdzie jest to przedstawione trochę
więcej niż to, co mówię teraz.

155
00:07:23,810 --> 00:07:25,300
Ale to jest to.

156
00:07:25,300 --> 00:07:29,300
Samo to jest rozwiązanie
obliczania silni liczby.

157
00:07:29,300 --> 00:07:31,527
>> To tylko cztery linie kodu.

158
00:07:31,527 --> 00:07:32,610
To bardzo fajne, prawda?

159
00:07:32,610 --> 00:07:35,480
To trochę sexy.

160
00:07:35,480 --> 00:07:38,580
>> Tak więc w ogólności, lecz nie
Zawsze, rekurencyjna funkcja

161
00:07:38,580 --> 00:07:41,190
może zastąpić pętli w
nierekursywnych funkcji.

162
00:07:41,190 --> 00:07:46,100
Więc, obok siebie, jest iteracyjna
wersja funkcji silni.

163
00:07:46,100 --> 00:07:49,650
Obie te oblicz
dokładnie to samo.

164
00:07:49,650 --> 00:07:52,170
>> Oboje obliczyć silnię n.

165
00:07:52,170 --> 00:07:54,990
Wersja na lewo
używa rekursji, aby to zrobić.

166
00:07:54,990 --> 00:07:58,320
Wersja na prawo
wykorzystuje iteracji, aby to zrobić.

167
00:07:58,320 --> 00:08:02,050
>> Oraz informacja, musimy zadeklarować
zmienna produktem całkowitą.

168
00:08:02,050 --> 00:08:02,940
A potem w pętli.

169
00:08:02,940 --> 00:08:06,790
Pod warunkiem, n jest większe niż 0, mamy
utrzymać mnożąc ten produkt przez n

170
00:08:06,790 --> 00:08:09,890
i zmniejszanie n, aż
obliczamy produkt.

171
00:08:09,890 --> 00:08:14,600
Tak więc te dwie funkcje, znowu,
zrobić dokładnie to samo.

172
00:08:14,600 --> 00:08:19,980
Ale nie rób tego w
dokładnie tak samo.

173
00:08:19,980 --> 00:08:22,430
>> Teraz możliwe jest
więcej niż jedną bazę

174
00:08:22,430 --> 00:08:25,770
przypadek lub więcej niż jeden
rekurencyjne przypadku, w zależności

175
00:08:25,770 --> 00:08:27,670
na co twoja funkcja stara się zrobić.

176
00:08:27,670 --> 00:08:31,650
Nie zawsze są ograniczone tylko do
jeden wariant podstawowy lub pojedynczy rekurencyjne

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

178
00:08:32,370 --> 00:08:35,320
Więc to przykład czegoś,
z wielu przypadków bazowych

179
00:08:35,320 --> 00:08:37,830
może być this--
Ciąg liczb Fibonacciego.

180
00:08:37,830 --> 00:08:41,549
>> Można przypomnieć od
elementarne dni szkolne

181
00:08:41,549 --> 00:08:45,740
że sekwencja Fibonacci definiuje
jak this-- pierwszy element jest 0.

182
00:08:45,740 --> 00:08:46,890
Drugi element 1.

183
00:08:46,890 --> 00:08:49,230
Obie z nich są po prostu z definicji.

184
00:08:49,230 --> 00:08:55,920
>> Następnie każdy inny element jest zdefiniowany
a suma n plus 1, a n minus 2.

185
00:08:55,920 --> 00:09:00,330
Więc trzeciego elementu
byłoby 0 plus 1 to 1.

186
00:09:00,330 --> 00:09:03,280
A potem czwarty element
jest drugim elementem, 1,

187
00:09:03,280 --> 00:09:06,550
oraz trzeci element 1.

188
00:09:06,550 --> 00:09:08,507
A to byłoby 2.

189
00:09:08,507 --> 00:09:09,340
I tak dalej, i tak dalej.

190
00:09:09,340 --> 00:09:11,680
>> Więc w tym przypadku, mamy dwa przypadki bazowe.

191
00:09:11,680 --> 00:09:14,850
Jeśli n jest równe 1, powrót 0.

192
00:09:14,850 --> 00:09:18,560
Jeśli n wynosi 2, powrót 1.

193
00:09:18,560 --> 00:09:25,930
W przeciwnym razie, powrót Fibonacciego n
minus 1 plus Fibonacciego n minus 2.

194
00:09:25,930 --> 00:09:27,180
>> Więc to jest kilka przypadków bazowych.

195
00:09:27,180 --> 00:09:29,271
Co z wielu cyklicznych przypadkach?

196
00:09:29,271 --> 00:09:31,520
Cóż, coś
zwana hipoteza Collatz.

197
00:09:31,520 --> 00:09:34,630
Nie powiem,
Wiesz, co to jest,

198
00:09:34,630 --> 00:09:38,170
bo to rzeczywiście nasza ostateczna
Problemem dla tego filmu wideo.

199
00:09:38,170 --> 00:09:43,220
I to jest nasza ćwiczenia
działać wspólnie.

200
00:09:43,220 --> 00:09:46,760
>> Więc oto co
Collatz domysły jest--

201
00:09:46,760 --> 00:09:48,820
ma zastosowanie do każdej liczby całkowitej dodatniej.

202
00:09:48,820 --> 00:09:51,500
I spekuluje, że jest to
Zawsze można wrócić

203
00:09:51,500 --> 00:09:55,060
do 1, jeśli wykonaj następujące kroki.

204
00:09:55,060 --> 00:09:57,560
Jeśli n jest 1, stop.

205
00:09:57,560 --> 00:10:00,070
Mamy z powrotem na 1, jeśli n oznacza 1.

206
00:10:00,070 --> 00:10:05,670
>> W przeciwnym razie, przejść przez to
Proces ponownie n dzieli się przez 2.

207
00:10:05,670 --> 00:10:08,200
I sprawdzić, czy można wrócić do 1.

208
00:10:08,200 --> 00:10:13,260
W przeciwnym razie, jeśli n jest nieparzyste, przejść
proces ten ponownie 3n plus 1,

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

210
00:10:15,552 --> 00:10:17,010
Więc tutaj mamy jeden przypadek bazowy.

211
00:10:17,010 --> 00:10:18,430
Jeśli n jest równe 1, stop.

212
00:10:18,430 --> 00:10:20,230
Nie robimy żadnych więcej rekursji.

213
00:10:20,230 --> 00:10:23,730
>> Ale mamy dwa rekurencyjne przypadki.

214
00:10:23,730 --> 00:10:28,750
Jeśli n jest parzyste, robimy jeden rekurencyjnych
Sprawa, nazywając n dzieli się przez 2.

215
00:10:28,750 --> 00:10:33,950
Jeśli n jest nieparzyste, robimy różne
Przypadek 3 rekurencyjne n razy plus 1.

216
00:10:33,950 --> 00:10:39,120
>> A więc celem tego filmu jest
wziąć drugi, wstrzymać odtwarzanie pliku wideo,

217
00:10:39,120 --> 00:10:42,440
i spróbować napisać to
Funkcja rekurencyjna Collatz

218
00:10:42,440 --> 00:10:47,640
gdzie przechodzą w wartości n, a
oblicza, ile kroków,

219
00:10:47,640 --> 00:10:52,430
potrzeba, aby do 1, jeśli zaczniesz od n
i wykonaj te kroki się powyżej.

220
00:10:52,430 --> 00:10:56,660
Jeśli n oznacza 1, to trwa 0 czynności.

221
00:10:56,660 --> 00:11:00,190
W przeciwnym razie, to będzie
jeden krok plusa jednak

222
00:11:00,190 --> 00:11:06,200
wiele czynności wykonywanych na każdej n
podzielony przez 2, gdy n jest równe, albo 3 n plus 1

223
00:11:06,200 --> 00:11:08,100
jeśli n jest nieparzyste.

224
00:11:08,100 --> 00:11:11,190
>> Teraz, mam umieścić na ekranie tutaj
kilka rzeczy badań dla Ciebie,

225
00:11:11,190 --> 00:11:15,690
kilka testów przypadkach dla Ciebie, aby zobaczyć
co te są różne numery Collatz,

226
00:11:15,690 --> 00:11:17,440
a także ilustracją
z kroków, które

227
00:11:17,440 --> 00:11:20,390
trzeba przeszedł więc można
rodzaj zobaczyć ten proces w akcji.

228
00:11:20,390 --> 00:11:24,222
Tak więc, gdy n jest równe
1, Collatz n wynosi 0.

229
00:11:24,222 --> 00:11:26,180
Nie musisz robić
wszystko, aby wrócić do 1.

230
00:11:26,180 --> 00:11:27,600
Jesteś już tam jest.

231
00:11:27,600 --> 00:11:30,550
>> Jeśli n oznacza 2, to ma
jeden krok, aby dostać się do 1.

232
00:11:30,550 --> 00:11:31,810
Zaczynasz z 2.

233
00:11:31,810 --> 00:11:33,100
Więc, 2 nie jest równa 1.

234
00:11:33,100 --> 00:11:36,580
Więc to będzie jeden krok
plus jednak wiele kroków,

235
00:11:36,580 --> 00:11:38,015
przybiera n dzieli się przez 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 podzielone przez 2 to 1.

238
00:11:42,910 --> 00:11:47,200
Tak to trwa jeden krok plusa jednak
wiele kroków trwa do 1.

239
00:11:47,200 --> 00:11:49,720
1 ma zerowe kroki.

240
00:11:49,720 --> 00:11:52,370
>> Na 3, jak widać, nie ma
sporo etapów.

241
00:11:52,370 --> 00:11:53,590
Idziesz od 3.

242
00:11:53,590 --> 00:11:56,710
A następnie udać się do
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
To trwa siedem kroków, aby wrócić do 1.

244
00:11:58,804 --> 00:12:01,220
I jak widać, istnieje
kilka innych przypadków testowych tutaj

245
00:12:01,220 --> 00:12:02,470
przetestować swój program.

246
00:12:02,470 --> 00:12:03,970
Więc jeszcze raz, zatrzymać wideo.

247
00:12:03,970 --> 00:12:09,210
I pójdę wrócić teraz
co sam proces jest tutaj,

248
00:12:09,210 --> 00:12:11,390
co to przypuszczenie.

249
00:12:11,390 --> 00:12:14,140
>> Sprawdź, czy możesz dowiedzieć się,
jak zdefiniować Collatz n

250
00:12:14,140 --> 00:12:19,967
tak, że oblicza, ile
kroki trzeba, aby dostać się do 1.

251
00:12:19,967 --> 00:12:23,050
Więc mam nadzieję, wstrzymaniu wideo
i nie czekają na mnie

252
00:12:23,050 --> 00:12:25,820
dać odpowiedź tutaj.

253
00:12:25,820 --> 00:12:29,120
Ale jeśli jesteś, dobrze,
oto odpowiedź tak.

254
00:12:29,120 --> 00:12:33,070
>> Więc tutaj jest możliwe określenie
funkcji Collatz.

255
00:12:33,070 --> 00:12:35,610
Nasza baza case-- jeśli n jest
równa 1, to zwraca 0.

256
00:12:35,610 --> 00:12:38,250
Nie bierze żadnej
kroki, aby wrócić do 1.

257
00:12:38,250 --> 00:12:42,710
>> W przeciwnym razie mamy dwa rekurencyjne cases--
jeden dla liczb parzystych i jeden dla dziwne.

258
00:12:42,710 --> 00:12:47,164
Sposób, w jaki przetestować liczb parzystych
jest sprawdzenie, czy n mod 2 jest równa 0.

259
00:12:47,164 --> 00:12:49,080
Jest to w zasadzie, ponownie
zadać pytanie,

260
00:12:49,080 --> 00:12:54,050
jeśli przypomnieć, co mod jest-- jeśli
podział n przez 2 ma tam pozostała?

261
00:12:54,050 --> 00:12:55,470
To byłoby liczbą parzystą.

262
00:12:55,470 --> 00:13:01,370
>> I tak, jeśli n mod 2 jest równa 0 to
Badanie to jest liczbą parzystą.

263
00:13:01,370 --> 00:13:04,250
Jeśli tak, chcę wrócić 1,
bo to jest na pewno

264
00:13:04,250 --> 00:13:09,270
przyjmuje jeden krok do plusa Collatz z
co liczba jest połowa mnie.

265
00:13:09,270 --> 00:13:13,910
W przeciwnym razie, chcę wrócić 1
plus Collatz z 3 razy n plus 1.

266
00:13:13,910 --> 00:13:16,060
To był drugi
rekurencyjne krokiem, że

267
00:13:16,060 --> 00:13:19,470
może trwać do obliczenia
Collatz-- liczbę kroków

268
00:13:19,470 --> 00:13:22,610
trzeba, by wrócić
do 1 podano numer.

269
00:13:22,610 --> 00:13:24,610
Więc mam nadzieję, że ten przykład
dał ci trochę

270
00:13:24,610 --> 00:13:26,620
o smaku procedur rekurencyjnych.

271
00:13:26,620 --> 00:13:30,220
Mamy nadzieję, że myślisz, że kod jest
trochę więcej piękna, jeśli realizowane

272
00:13:30,220 --> 00:13:32,760
w eleganckim, rekurencyjnego sposób.

273
00:13:32,760 --> 00:13:35,955
Ale nawet jeśli nie, rekurencja jest
naprawdę potężnym narzędziem, jednak.

274
00:13:35,955 --> 00:13:38,330
A więc jest to zdecydowanie coś
aby uzyskać głowę,

275
00:13:38,330 --> 00:13:41,360
ponieważ będziesz w stanie stworzyć
całkiem fajne programy za pomocą rekurencji

276
00:13:41,360 --> 00:13:45,930
które mogłyby być złożone do pisania
jeśli korzystasz z pętli i iteracji.

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

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

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