1
00:00:00,000 --> 00:00:05,860
>> [Mūzikas atskaņošanai]

2
00:00:05,860 --> 00:00:09,530
>> Doug LLOYD: Jūs droši vien domājat, ka
kods tiek izmantots tikai, lai izpildītu uzdevumu.

3
00:00:09,530 --> 00:00:10,450
Jūs rakstīt to ārā.

4
00:00:10,450 --> 00:00:11,664
Tas nav kaut kas.

5
00:00:11,664 --> 00:00:12,580
Tas ir diezgan daudz to.

6
00:00:12,580 --> 00:00:13,160
>> Jūs sastādīt to.

7
00:00:13,160 --> 00:00:13,993
Jūs palaist programmu.

8
00:00:13,993 --> 00:00:15,370
Jūs esat labi iet.

9
00:00:15,370 --> 00:00:17,520
>> Bet ticiet vai nē, ja
jūs kods uz ilgu laiku,

10
00:00:17,520 --> 00:00:20,550
jūs tiešām varētu nākt, lai redzētu
kodu, kā kaut ko, kas ir skaists.

11
00:00:20,550 --> 00:00:23,275
Tas atrisina problēmu
ļoti interesants veids,

12
00:00:23,275 --> 00:00:26,510
vai tur ir tikai kaut kas patiešām
veikls par to, kā tas izskatās.

13
00:00:26,510 --> 00:00:28,750
Jūs varētu smieties
uz mani, bet tā ir taisnība.

14
00:00:28,750 --> 00:00:31,530
Un rekursijas ir viens no veidiem
lai veida iegūt šo ideju

15
00:00:31,530 --> 00:00:34,090
no skaista, eleganta izskata kods.

16
00:00:34,090 --> 00:00:37,740
Tas atrisina problēmas, tādā veidā, ka
ir interesanti, viegli iztēloties,

17
00:00:37,740 --> 00:00:39,810
un pārsteidzoši īss.

18
00:00:39,810 --> 00:00:43,190
>> The Way rekursijas darbi
ir, rekursīvs funkcijas

19
00:00:43,190 --> 00:00:49,291
tiek definēta kā funkciju, kas aicina
pati kā daļu no tās izpildes.

20
00:00:49,291 --> 00:00:51,790
Tas varētu likties mazliet dīvaini,
un mēs redzēsim mazliet

21
00:00:51,790 --> 00:00:53,750
par to, kā tas darbojas brīdi.

22
00:00:53,750 --> 00:00:55,560
Bet atkal, tie
rekursīvas procedūras

23
00:00:55,560 --> 00:00:57,730
būs tik elegants
jo viņi dodas

24
00:00:57,730 --> 00:01:00,410
lai atrisinātu šo problēmu bez
kam ir visas šīs citas funkcijas

25
00:01:00,410 --> 00:01:02,710
vai šie ilgi cilpas.

26
00:01:02,710 --> 00:01:06,310
Jūs redzēsiet, ka šie rekursīvas
procedūras ir gatavojas izskatās tik īss.

27
00:01:06,310 --> 00:01:10,610
Un viņi tiešām gatavojas darīt
Jūsu kods izskatīsies daudz skaistāku.

28
00:01:10,610 --> 00:01:12,560
>> Es došu jums piemēru
Tas lai redzētu, kā

29
00:01:12,560 --> 00:01:14,880
rekursīvs procedūra var definēt.

30
00:01:14,880 --> 00:01:18,202
Tātad, ja jūs esat iepazinušies ar šo
no matemātikas klasē pirms daudziem gadiem,

31
00:01:18,202 --> 00:01:20,910
tur ir kaut kas sauc
factorial funkcija, kas parasti ir

32
00:01:20,910 --> 00:01:25,340
apzīmēts kā izsaukuma zīmi, kas
definē pār visiem pozitīviem veseliem skaitļiem.

33
00:01:25,340 --> 00:01:28,850
Un tā, ka n
factorial aprēķina

34
00:01:28,850 --> 00:01:31,050
tiek jūs reizināt visu
skaitļi mazāk nekā

35
00:01:31,050 --> 00:01:33,750
vai vienāds ar n together--
visi veseli skaitļi mazāk nekā

36
00:01:33,750 --> 00:01:34,880
vai vienāds ar n kopā.

37
00:01:34,880 --> 00:01:39,850
>> Tātad 5 factorial ir 5 reizes
4 reizes 3 reizes 2 reizes 1.

38
00:01:39,850 --> 00:01:43,020
Un 4 factorial ir 4 reizes
3 reizes 2 reizes 1 un tā tālāk.

39
00:01:43,020 --> 00:01:44,800
Jūs saņemsiet ideja.

40
00:01:44,800 --> 00:01:47,060
>> Kā programmētāji, mums nav
izmantot N, izsaukuma zīmi.

41
00:01:47,060 --> 00:01:51,840
Tātad mēs definēt faktoriālu
funkcija kā faktu n.

42
00:01:51,840 --> 00:01:56,897
Un mēs izmantosim faktoriālu, lai izveidotu
rekursīvs risinājums problēmai.

43
00:01:56,897 --> 00:01:59,230
Un es domāju, ka jūs varētu atrast
ka tas ir daudz vairāk vizuāli

44
00:01:59,230 --> 00:02:02,380
pievilcīgs nekā iteratīvs
versija par šo, kas

45
00:02:02,380 --> 00:02:05,010
mēs arī to apskatīt brīdi.

46
00:02:05,010 --> 00:02:08,310
>> Tātad, šeit ir pāris
facts-- pun intended--

47
00:02:08,310 --> 00:02:10,169
par factorial--
faktoriāls funkcija.

48
00:02:10,169 --> 00:02:13,090
No 1. factorial, kā jau teicu, ir 1.

49
00:02:13,090 --> 00:02:15,690
No 2. factorial ir 2 reizes 1.

50
00:02:15,690 --> 00:02:18,470
No 3. factorial ir 3
reizes 2 reizes 1, un tā tālāk.

51
00:02:18,470 --> 00:02:20,810
Mēs runājām par 4. un 5. jau.

52
00:02:20,810 --> 00:02:23,940
>> Bet skatoties uz to, nav taisnība?

53
00:02:23,940 --> 00:02:28,220
Vai nav faktoriālu 2 vienkārši
2 reizes faktoriālu 1?

54
00:02:28,220 --> 00:02:31,130
Es domāju, faktoriālu 1 ir 1.

55
00:02:31,130 --> 00:02:34,940
Tātad, kāpēc mēs nevaram vienkārši teikt, ka,
kopš faktoriālu no 2 ir 2 reizes 1,

56
00:02:34,940 --> 00:02:38,520
tas patiešām ir tikai 2 reizes
faktoriālu 1?

57
00:02:38,520 --> 00:02:40,900
>> Un tad paplašinot šo ideju,
nav faktoriālu 3

58
00:02:40,900 --> 00:02:44,080
tikai 3 reizes faktoriālu 2?

59
00:02:44,080 --> 00:02:50,350
Un faktoriālu 4 ir 4 reizes
faktoriālu 3, un tā tālāk?

60
00:02:50,350 --> 00:02:52,530
Faktiski, faktoriālu
Jebkuras skaits var vienkārši

61
00:02:52,530 --> 00:02:54,660
izsaka ja mēs laipns
no veikt šo out uz visiem laikiem.

62
00:02:54,660 --> 00:02:56,870
Mēs varam veida vispārināt
faktoriālu problēma

63
00:02:56,870 --> 00:02:59,910
kā tas ir n reizes
factorial n mīnus 1.

64
00:02:59,910 --> 00:03:04,840
Tas ir n reizes produkts
visi skaitļi mazāk nekā man.

65
00:03:04,840 --> 00:03:08,890
>> Šī ideja, šis
vispārināšana problēmas,

66
00:03:08,890 --> 00:03:13,410
ļauj rekursīvi
definēt Faktoru funkciju.

67
00:03:13,410 --> 00:03:15,440
Kad jūs definētu funkciju
rekursīvi, tur ir

68
00:03:15,440 --> 00:03:17,470
divas lietas, kas ir nepieciešams, lai būtu daļa no tā.

69
00:03:17,470 --> 00:03:20,990
Jums ir nepieciešams, lai būtu kaut ko sauc
bāze gadījums, kas, kad jūs izraisīt to,

70
00:03:20,990 --> 00:03:22,480
pārtrauks rekursīvas procesu.

71
00:03:22,480 --> 00:03:25,300
>> Pretējā gadījumā funkcija, kas prasa
itself-- kā jūs varētu imagine--

72
00:03:25,300 --> 00:03:26,870
varētu iet uz visiem laikiem.

73
00:03:26,870 --> 00:03:29,047
Funkcija izsauc funkciju
aicina Funkcija zvanus

74
00:03:29,047 --> 00:03:30,380
funkcija izsauc funkciju.

75
00:03:30,380 --> 00:03:32,380
Ja jums nav veids
lai to apturētu, savu programmu

76
00:03:32,380 --> 00:03:34,760
faktiski būs iestrēdzis
pie bezgalīgu cilpu.

77
00:03:34,760 --> 00:03:37,176
Tas būs crash galā,
jo tas būs beigušies atmiņas.

78
00:03:37,176 --> 00:03:38,990
Bet tas ir blakus punktu.

79
00:03:38,990 --> 00:03:42,210
>> Mums ir nepieciešams, lai ir kāda cita veids, kā apturēt
lietas, turklāt mūsu programmas crashing,

80
00:03:42,210 --> 00:03:46,010
jo programma, kas avārijām ir
iespējams, nav skaisti vai elegants.

81
00:03:46,010 --> 00:03:47,690
Un tā mēs dēvējam bāzes gadījums.

82
00:03:47,690 --> 00:03:50,610
Tas ir vienkāršs risinājums
uz problēmu, kas aptur

83
00:03:50,610 --> 00:03:52,770
rekursīvas process rašanos.

84
00:03:52,770 --> 00:03:55,220
Tā ka ir viena daļa no
rekursīvs funkciju.

85
00:03:55,220 --> 00:03:56,820
>> Otrā daļa ir rekursīvs gadījums.

86
00:03:56,820 --> 00:03:59,195
Un tas ir, ja rekursijas
tiešām notiks.

87
00:03:59,195 --> 00:04:02,200
Tas ir, ja
funkcija aicinās sevi.

88
00:04:02,200 --> 00:04:05,940
>> Tas nebūs zvanīt sevi tieši
tāpat to sauca.

89
00:04:05,940 --> 00:04:08,880
Tas būs neliela variācija
kas padara šo problēmu tas ir

90
00:04:08,880 --> 00:04:11,497
mēģinot atrisināt maziņš mazliet mazāka.

91
00:04:11,497 --> 00:04:14,330
Bet tas parasti iet buks
atrisināt lielāko daļu no risinājuma

92
00:04:14,330 --> 00:04:17,450
uz citu zvanu nosaka līniju.

93
00:04:17,450 --> 00:04:20,290
>> Kurš no šiem izskatās
tāpat bāzes gadījums?

94
00:04:20,290 --> 00:04:25,384
Kura no šīm izskatās
Vienkāršākais risinājums problēmai?

95
00:04:25,384 --> 00:04:27,550
Mums ir ķekars faktoriālu,
un mēs varētu turpināt

96
00:04:27,550 --> 00:04:30,470
iet on-- 6, 7, 8, 9, 10, un tā tālāk.

97
00:04:30,470 --> 00:04:34,130
>> Bet viens no šiem izskatās
laba lieta būt bāzes gadījums.

98
00:04:34,130 --> 00:04:35,310
Tas ir ļoti vienkāršs risinājums.

99
00:04:35,310 --> 00:04:37,810
Mums nav kaut kas īpašs jādara.

100
00:04:37,810 --> 00:04:40,560
>> No 1 factorial ir tikai 1.

101
00:04:40,560 --> 00:04:42,790
Mums nav jādara kādu
pavairošana vispār.

102
00:04:42,790 --> 00:04:45,248
Šķiet, tāpat kā tad, ja mēs ejam
lai mēģinātu atrisināt šo problēmu,

103
00:04:45,248 --> 00:04:47,600
un mums ir nepieciešams, lai apturētu
rekursijas kaut kur,

104
00:04:47,600 --> 00:04:50,610
mēs, iespējams, vēlas, lai apturētu
tā, kad mēs nokļūt līdz 1.

105
00:04:50,610 --> 00:04:54,580
Mēs nevēlamies apstāties pirms tam.

106
00:04:54,580 --> 00:04:56,660
>> Tātad, ja mēs esam definējot
Mūsu factorial funkcija,

107
00:04:56,660 --> 00:04:58,690
šeit ir karkass
kā mēs varētu darīt.

108
00:04:58,690 --> 00:05:03,110
Mums ir nepieciešams, lai kontaktdakšu šiem diviem things--
bāzes modeli, un rekursīvas lieta.

109
00:05:03,110 --> 00:05:04,990
Kas ir bāzes lieta?

110
00:05:04,990 --> 00:05:10,150
Ja n ir vienāds ar 1, atgriezties 1-- tas ir
ļoti vienkāršs problēmu atrisināt.

111
00:05:10,150 --> 00:05:11,890
>> No 1 faktoriāls ir 1.

112
00:05:11,890 --> 00:05:13,860
Tas nav 1 reizes neko.

113
00:05:13,860 --> 00:05:15,020
Tas ir tikai 1.

114
00:05:15,020 --> 00:05:17,170
Tas ir ļoti vienkārši fakts.

115
00:05:17,170 --> 00:05:19,620
Un tā, kas var būt mūsu bāze gadījums.

116
00:05:19,620 --> 00:05:24,730
Ja mēs pagājis 1 par šo
funkcija, mēs vienkārši atgriezties 1.

117
00:05:24,730 --> 00:05:27,320
>> Kas ir rekursīvas
gadījums, iespējams, izskatās?

118
00:05:27,320 --> 00:05:32,445
Par katru citu numuru
Bez tam 1., kāda ir modelis?

119
00:05:32,445 --> 00:05:35,780
Nu, ja mēs esam ņemot
faktoriālu n,

120
00:05:35,780 --> 00:05:38,160
ir pienācis n reizes faktoriālu n mīnus 1.

121
00:05:38,160 --> 00:05:42,130
>> Ja mēs esam ņemot faktoriālu 3,
tas ir 3 reizes faktoriālu 3 mīnus 1,

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

123
00:05:43,070 --> 00:05:47,330
Un tāpēc, ja mēs neesam
apskatot 1, pretējā gadījumā

124
00:05:47,330 --> 00:05:51,710
atgriešanās n reizes
factorial n mīnus 1.

125
00:05:51,710 --> 00:05:53,210
Tas ir diezgan vienkārši.

126
00:05:53,210 --> 00:05:57,360
>> Un labad kam nedaudz
tīrāku un vairāk elegants kods,

127
00:05:57,360 --> 00:06:01,440
zina, ka, ja mums ir viena līnija cilpas
vai single-line nosacītie filiāles,

128
00:06:01,440 --> 00:06:04,490
mēs varam atbrīvoties no visa
cirtaini bikšturi ap tiem.

129
00:06:04,490 --> 00:06:06,850
Tātad, mēs varam nostiprināt šo to.

130
00:06:06,850 --> 00:06:09,640
Tas ir tieši tāds pats
funkcionalitāti, kā šis.

131
00:06:09,640 --> 00:06:13,850
>> Es esmu tikai atņemot cirtaini
breketes, jo tur ir tikai viena līnija

132
00:06:13,850 --> 00:06:18,500
iekšpusē šiem nosacītas filiālēm.

133
00:06:18,500 --> 00:06:21,160
Tātad šie izturēties vienādi.

134
00:06:21,160 --> 00:06:23,800
Ja n ir vienāds ar 1, atgriezties 1.

135
00:06:23,800 --> 00:06:28,351
Pretējā atgriezties n reizes
faktoriālu n mīnus 1.

136
00:06:28,351 --> 00:06:29,850
Tātad mēs nesam mazāku problēmu.

137
00:06:29,850 --> 00:06:33,850
Ja n uzsāk veikt kā 5, mēs ejam, lai
atgriezt 5 reizes faktoriālu 4.

138
00:06:33,850 --> 00:06:37,100
Un mēs redzēsim pēc brīža, kad mēs runājam
par zvanu stack-- citā video

139
00:06:37,100 --> 00:06:39,390
ja mēs runājam par
zvaniet stack-- mēs mācīties

140
00:06:39,390 --> 00:06:41,630
par to, kāpēc tieši šis process darbojas.

141
00:06:41,630 --> 00:06:46,970
>> Bet, kamēr factorial 5 saka
atgriezties 5 reizes factorial no 4, un 4

142
00:06:46,970 --> 00:06:49,710
gatavojas teikt, OK, labi, atgriešanās
4 reizes faktoriālu 3.

143
00:06:49,710 --> 00:06:51,737
Un, kā jūs varat redzēt, mēs esam
kārtot tuvojas 1.

144
00:06:51,737 --> 00:06:53,820
Mēs esam nonākuši tuvāk un
tuvāk šo gadījumu.

145
00:06:53,820 --> 00:06:58,180
>> Un, kad mēs hit bāzes lietu,
visu iepriekšējo funkciju

146
00:06:58,180 --> 00:07:00,540
ir atbilde viņi meklē.

147
00:07:00,540 --> 00:07:03,900
Faktoriāls 2. teica atgriešanos
2 reizes faktoriālu 1.

148
00:07:03,900 --> 00:07:06,760
Nu, faktoriālu no 1 atdevi 1.

149
00:07:06,760 --> 00:07:10,090
Tātad aicinājums faktoriālo
2. var atgriezt 2 reizes 1,

150
00:07:10,090 --> 00:07:13,980
un dod, ka atpakaļ uz faktoriālu
3, kas gaida šo rezultātu.

151
00:07:13,980 --> 00:07:17,110
>> Un tad to var aprēķināt
tās rezultāts, 3 reizes 2 ir 6,

152
00:07:17,110 --> 00:07:18,907
un dot to atpakaļ uz faktoriālu 4.

153
00:07:18,907 --> 00:07:20,740
Un atkal, mums ir
video par zvanu kaudze

154
00:07:20,740 --> 00:07:23,810
ja tas ir ilustrēts nedaudz
vairāk nekā tas, ko es saku tagad.

155
00:07:23,810 --> 00:07:25,300
Bet tas ir tā.

156
00:07:25,300 --> 00:07:29,300
Tas vien ir risinājums
Aprēķinot skaitļa faktoriālu.

157
00:07:29,300 --> 00:07:31,527
>> Tas ir tikai četras rindiņas kodu.

158
00:07:31,527 --> 00:07:32,610
Tas ir diezgan cool, vai ne?

159
00:07:32,610 --> 00:07:35,480
Tas ir sava veida sexy.

160
00:07:35,480 --> 00:07:38,580
>> Tā vispār, bet ne
vienmēr, rekursīvs funkcijas

161
00:07:38,580 --> 00:07:41,190
var aizstāt cilpu kādā
non-rekursīvas funkcijas.

162
00:07:41,190 --> 00:07:46,100
Tātad šeit, blakus, ir iteratīvs
versija faktoriālo funkciju.

163
00:07:46,100 --> 00:07:49,650
Abas šīs Aprēķināt
tieši tas pats.

164
00:07:49,650 --> 00:07:52,170
>> Viņi abi aprēķināt faktoriālu n.

165
00:07:52,170 --> 00:07:54,990
Version pa kreisi
izmanto Rekursija, lai to izdarītu.

166
00:07:54,990 --> 00:07:58,320
Version labajā pusē
izmanto atkārtojuma, lai to izdarītu.

167
00:07:58,320 --> 00:08:02,050
>> Un paziņojums, mums ir jādeklarē
mainīgs vesels skaitlis produkts.

168
00:08:02,050 --> 00:08:02,940
Un tad mēs cilpa.

169
00:08:02,940 --> 00:08:06,790
Tik ilgi, kamēr n ir lielāks par 0, mēs
glabāt reizinot šo produktu ar n

170
00:08:06,790 --> 00:08:09,890
un decrementing N līdz
mēs aprēķināt produktu.

171
00:08:09,890 --> 00:08:14,600
Tātad šīs divas funkcijas, atkal,
darīt tieši to pašu.

172
00:08:14,600 --> 00:08:19,980
Bet tie nav darīt to
tieši tāpat.

173
00:08:19,980 --> 00:08:22,430
>> Tagad, tas ir iespējams, lai
ir vairāk nekā vienas bāzes

174
00:08:22,430 --> 00:08:25,770
gadījums vai vairāk nekā viens
rekursīvs gadījumā, atkarībā

175
00:08:25,770 --> 00:08:27,670
par ko jūsu funkcija mēģina darīt.

176
00:08:27,670 --> 00:08:31,650
Jūs ne vienmēr ir tikai tikai uz
vienu gadījumu, vai viena rekursīva

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

178
00:08:32,370 --> 00:08:35,320
Tātad piemērs kaut
ar vairākām bāzes gadījumos

179
00:08:35,320 --> 00:08:37,830
varētu būt this--
Fibonači skaitļi secība.

180
00:08:37,830 --> 00:08:41,549
>> Jūs varbūt atceraties no
pamatskolas dienas

181
00:08:41,549 --> 00:08:45,740
ka Fibonači secība ir definēts
tāpat this-- pirmais elements ir 0.

182
00:08:45,740 --> 00:08:46,890
Otrais elements ir 1.

183
00:08:46,890 --> 00:08:49,230
Abi no tiem ir vienkārši pēc definīcijas.

184
00:08:49,230 --> 00:08:55,920
>> Tad katru otro elements ir definēts
kā n mīnus 1 un n mīnus 2 summu.

185
00:08:55,920 --> 00:09:00,330
Tātad trešā elementa
Būtu 0 plus 1 ir 1.

186
00:09:00,330 --> 00:09:03,280
Un tad ceturtais elements
būtu otrais elements, 1,

187
00:09:03,280 --> 00:09:06,550
plus trešais elements, 1.

188
00:09:06,550 --> 00:09:08,507
Un tas būtu 2.

189
00:09:08,507 --> 00:09:09,340
Un tā tālāk, un tā tālāk.

190
00:09:09,340 --> 00:09:11,680
>> Tātad šajā gadījumā, mums ir divas bāzes lietas.

191
00:09:11,680 --> 00:09:14,850
Ja n ir vienāds ar 1, atgriezties 0.

192
00:09:14,850 --> 00:09:18,560
Ja n ir vienāds ar 2, atgriezties 1.

193
00:09:18,560 --> 00:09:25,930
Pretējā gadījumā atgriešanās Fibonacci n
mīnus 1 plus Fibonači n mīnus 2.

194
00:09:25,930 --> 00:09:27,180
>> Tā ka ir vairākas bāzes gadījumus.

195
00:09:27,180 --> 00:09:29,271
Kas par vairākiem rekursīvs gadījumos?

196
00:09:29,271 --> 00:09:31,520
Nu, tur ir kaut kas
sauc Collatz minējums.

197
00:09:31,520 --> 00:09:34,630
Es neesmu gatavojas teikt,
jūs zināt, kas tas ir,

198
00:09:34,630 --> 00:09:38,170
jo tas ir tiešām mūsu gala
problēma šo konkrēto video.

199
00:09:38,170 --> 00:09:43,220
Un tas ir mūsu uzdevums
strādāt kopā.

200
00:09:43,220 --> 00:09:46,760
>> Tātad, šeit ir tas, ko
Collatz minējums is--

201
00:09:46,760 --> 00:09:48,820
tas attiecas uz katram pozitīvam skaitlim.

202
00:09:48,820 --> 00:09:51,500
Un tā lēš, ka tas ir
vienmēr ir iespējams saņemt atpakaļ

203
00:09:51,500 --> 00:09:55,060
ar 1, ja jūs izpildiet šīs darbības.

204
00:09:55,060 --> 00:09:57,560
Ja n ir 1, apturēt.

205
00:09:57,560 --> 00:10:00,070
Mēs esam ieguvuši atpakaļ uz 1, ja n ir 1.

206
00:10:00,070 --> 00:10:05,670
>> Pretējā gadījumā, iet caur šo
process atkal n dalot ar 2.

207
00:10:05,670 --> 00:10:08,200
Un redzēt, ja jūs varat saņemt atpakaļ 1.

208
00:10:08,200 --> 00:10:13,260
Pretējā gadījumā, ja n ir nepāra, iet cauri
šis process atkal 3N plus 1,

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

210
00:10:15,552 --> 00:10:17,010
Tātad šeit mums ir vienota bāze lietu.

211
00:10:17,010 --> 00:10:18,430
Ja n ir vienāds ar 1, apturēt.

212
00:10:18,430 --> 00:10:20,230
Mēs nedarām nevienu vairāk Rekursija.

213
00:10:20,230 --> 00:10:23,730
>> Bet mums ir divas rekursīvs gadījumi.

214
00:10:23,730 --> 00:10:28,750
Ja n ir pat, mēs darīt vienu rekursīvas
gadījumā, aicinot n dalot ar 2.

215
00:10:28,750 --> 00:10:33,950
Ja n ir nepāra, mēs cits
rekursīvo gadījums 3 reizes n plus 1.

216
00:10:33,950 --> 00:10:39,120
>> Un tā mērķis šai video ir
ņemt otro, apturētu video,

217
00:10:39,120 --> 00:10:42,440
un mēģināt rakstīt šo
rekursīvas funkcijas Collatz

218
00:10:42,440 --> 00:10:47,640
kur jums iet ar vērtību n, un
tā aprēķina, cik daudz pasākumiem, ko tā

219
00:10:47,640 --> 00:10:52,430
nepieciešams, lai nokļūtu līdz 1, ja jūs sākat no n
un jūs izpildiet šos soļus augšas.

220
00:10:52,430 --> 00:10:56,660
Ja n ir 1, tas aizņem 0 soļus.

221
00:10:56,660 --> 00:11:00,190
Pretējā gadījumā, tas notiek, lai
veikt vienu soli plus tomēr

222
00:11:00,190 --> 00:11:06,200
daudzi soļi tā veic vai nu n
dalīts ar 2, ja n ir pat, vai 3n plus 1

223
00:11:06,200 --> 00:11:08,100
ja n ir nepāra.

224
00:11:08,100 --> 00:11:11,190
>> Tagad, es esmu likts uz ekrāna šeit
pāris testa lietas jums,

225
00:11:11,190 --> 00:11:15,690
pāris testos gadījumu jums, lai redzētu
ko šie dažādie Collatz skaitļi ir,

226
00:11:15,690 --> 00:11:17,440
un arī ilustrācija
par pasākumiem, kas

227
00:11:17,440 --> 00:11:20,390
nepieciešams gājusi cauri, lai jūs varētu
kārtot redzēt šo procesu darbībā.

228
00:11:20,390 --> 00:11:24,222
Tātad, ja n ir vienāds ar
1, Collatz no n ir 0.

229
00:11:24,222 --> 00:11:26,180
Jums nav jādara
kaut kas, lai saņemtu atpakaļ uz 1.

230
00:11:26,180 --> 00:11:27,600
Tu esi jau tur.

231
00:11:27,600 --> 00:11:30,550
>> Ja n ir 2, tas aizņem
viens solis, lai nokļūtu līdz 1.

232
00:11:30,550 --> 00:11:31,810
Tu sāc ar 2.

233
00:11:31,810 --> 00:11:33,100
Nu, 2 nav vienāds ar 1.

234
00:11:33,100 --> 00:11:36,580
Tātad tas būs viens solis
plus tomēr daudzi pasākumiem, ko tā

235
00:11:36,580 --> 00:11:38,015
uzņemas n dalot ar 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 dalīts ar 2 ir 1.

238
00:11:42,910 --> 00:11:47,200
Tātad tas aizņem vienu soli plus tomēr
daudzi soļi, kas nepieciešams, lai 1.

239
00:11:47,200 --> 00:11:49,720
1. ņem nulle soļus.

240
00:11:49,720 --> 00:11:52,370
>> 3, kā jūs varat redzēt, tur ir
iesaistīts diezgan dažus soļus.

241
00:11:52,370 --> 00:11:53,590
Jums iet no 3.

242
00:11:53,590 --> 00:11:56,710
Un tad doties uz
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Tas aizņem septiņus soļus, lai saņemtu atpakaļ uz 1.

244
00:11:58,804 --> 00:12:01,220
Un, kā jūs varat redzēt, tur ir
pāris citas pārbaudes gadījumos šeit

245
00:12:01,220 --> 00:12:02,470
izmēģināt savu programmu.

246
00:12:02,470 --> 00:12:03,970
Tātad vēlreiz, apturētu video.

247
00:12:03,970 --> 00:12:09,210
Un es iešu lēkt atpakaļ tagad
ko faktiskais process ir šeit,

248
00:12:09,210 --> 00:12:11,390
ko šis minējums ir.

249
00:12:11,390 --> 00:12:14,140
>> Skat, ja jūs varat izdomāt
Kā noteikt Collatz n

250
00:12:14,140 --> 00:12:19,967
lai tā aprēķina, cik daudz
soļi, kas nepieciešams, lai nokļūtu līdz 1.

251
00:12:19,967 --> 00:12:23,050
Tik cerams, jums ir apturēta video
un jums ir ne tikai gaida mani

252
00:12:23,050 --> 00:12:25,820
sniegt jums atbildi šeit.

253
00:12:25,820 --> 00:12:29,120
Bet, ja jums ir, labi,
Lūk atbilde vienalga.

254
00:12:29,120 --> 00:12:33,070
>> Tātad, šeit ir iespējams definīcija
no Collatz funkciju.

255
00:12:33,070 --> 00:12:35,610
Mūsu bāze case-- ja n ir
vienāds ar 1, mēs atgrieztos 0.

256
00:12:35,610 --> 00:12:38,250
Tas neņem jebkurš
soļi, lai saņemtu atpakaļ uz 1.

257
00:12:38,250 --> 00:12:42,710
>> Pretējā gadījumā mums ir divas rekursīvas cases--
viena pāra numuri un viens nepāra.

258
00:12:42,710 --> 00:12:47,164
Kā es tests pāra numuru
ir pārbaudīt, vai n mod 2 ir vienāds ar 0.

259
00:12:47,164 --> 00:12:49,080
Tas ir galvenokārt, atkal,
uzdodot jautājumu,

260
00:12:49,080 --> 00:12:54,050
Ja jūs atceraties, ko mod is-- ja es
dalīt n ar 2 tur nav atlikums?

261
00:12:54,050 --> 00:12:55,470
Tas būtu pāra skaitlis.

262
00:12:55,470 --> 00:13:01,370
>> Un tāpēc, ja n mod 2 ir vienāds ar 0 ir
testēšana ir šī pāra skaits.

263
00:13:01,370 --> 00:13:04,250
Ja tā, es vēlos atgriezties 1,
jo tas noteikti

264
00:13:04,250 --> 00:13:09,270
ņemot vienu soli plus Collatz par
kāds numurs ir puse no manis.

265
00:13:09,270 --> 00:13:13,910
Citādi, es vēlos atgriezties 1
plus Collatz par 3 reizes n plus 1.

266
00:13:13,910 --> 00:13:16,060
Ka bija otra
rekursīvo solis, ka mēs

267
00:13:16,060 --> 00:13:19,470
varētu veikt, lai aprēķinātu
Collatz-- vairākus pasākumus

268
00:13:19,470 --> 00:13:22,610
tas nepieciešams, lai saņemtu atpakaļ
1 piešķir numuru.

269
00:13:22,610 --> 00:13:24,610
Tātad, cerams, šis piemērs
tev mazliet

270
00:13:24,610 --> 00:13:26,620
par garšu rekursīvs procedūru.

271
00:13:26,620 --> 00:13:30,220
Cerams, ka jūs domājat, ka kods ir
nedaudz vairāk skaisti, ja īstenos

272
00:13:30,220 --> 00:13:32,760
elegantā, rekursīvas veidā.

273
00:13:32,760 --> 00:13:35,955
Bet pat tad, ja tā nav, rekursijas ir
tiešām spēcīgs instruments tomēr.

274
00:13:35,955 --> 00:13:38,330
Un tā tas noteikti ir kaut
lai saņemtu savu galvu apkārt,

275
00:13:38,330 --> 00:13:41,360
jo jūs varēsiet radīt
pretty cool programmas, izmantojot Rekursija

276
00:13:41,360 --> 00:13:45,930
kas citādi varētu būt sarežģīti uzrakstīt
ja jūs izmantojat cilpas un atkārtojuma.

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

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

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