1
00:00:00,000 --> 00:00:05,860
>> [Гуляе музыка]

2
00:00:05,860 --> 00:00:09,530
>> Даг Lloyd: Вы, напэўна, думаеце, што
Код выкарыстоўваецца толькі для выканання задачы.

3
00:00:09,530 --> 00:00:10,450
Вы пішаце гэта.

4
00:00:10,450 --> 00:00:11,664
Гэта нешта робіць.

5
00:00:11,664 --> 00:00:12,580
Гэта даволі шмат яго.

6
00:00:12,580 --> 00:00:13,160
>> Вы скампіляваць яго.

7
00:00:13,160 --> 00:00:13,993
Вы запускаеце праграму.

8
00:00:13,993 --> 00:00:15,370
Вы добра ісці.

9
00:00:15,370 --> 00:00:17,520
>> Але верыць гэтаму ці не, калі
вы код на працягу доўгага часу,

10
00:00:17,520 --> 00:00:20,550
вы на самой справе можа прыйсці, каб убачыць
Код, як нешта, што прыгожа.

11
00:00:20,550 --> 00:00:23,275
Гэта вырашае праблему ў
вельмі цікавы спосаб,

12
00:00:23,275 --> 00:00:26,510
ці ёсць нешта сапраўды
акуратны пра тое, як ён выглядае.

13
00:00:26,510 --> 00:00:28,750
Вы можаце смяяцца
на мяне, але гэта праўда.

14
00:00:28,750 --> 00:00:31,530
І Рэкурсія з'яўляецца адным са спосабаў
да выгляду гэтая ідэя

15
00:00:31,530 --> 00:00:34,090
прыгожая, элегантная, гледзячы код.

16
00:00:34,090 --> 00:00:37,740
Гэта вырашае праблемы такім чынам, што
цікавыя, лёгка візуалізаваць,

17
00:00:37,740 --> 00:00:39,810
і дзіўна кароткім.

18
00:00:39,810 --> 00:00:43,190
>> Шляху рэкурсіі працы
ёсць, рэкурсіўная функцыя

19
00:00:43,190 --> 00:00:49,291
вызначаецца як функцыя, якая выклікае
сябе як часткі яго выканання.

20
00:00:49,291 --> 00:00:51,790
Гэта можа здацца трохі дзіўным,
і мы ўбачым трохі

21
00:00:51,790 --> 00:00:53,750
пра тое, як гэта працуе ў цяперашні час.

22
00:00:53,750 --> 00:00:55,560
Але зноў жа, гэта
рэкурсіўныя працэдуры

23
00:00:55,560 --> 00:00:57,730
будзе так элегантны
таму што яны збіраюцца

24
00:00:57,730 --> 00:01:00,410
каб вырашыць гэтую праблему без
маючы ўсе гэтыя і іншыя функцыі

25
00:01:00,410 --> 00:01:02,710
або гэтыя доўгія завесы.

26
00:01:02,710 --> 00:01:06,310
Вы ўбачыце, што гэта рэкурсіўная
працэдуры будзе выглядаць такое кароткае.

27
00:01:06,310 --> 00:01:10,610
І яны сапраўды маюць намер зрабіць
код выглядаць нашмат прыгажэй.

28
00:01:10,610 --> 00:01:12,560
>> Я дам вам прыклад
гэта паглядзець, як

29
00:01:12,560 --> 00:01:14,880
рэкурсіўная працэдура можа быць вызначана.

30
00:01:14,880 --> 00:01:18,202
Так што, калі вы знаёмыя з гэтым
ад матэматычным класе шмат гадоў таму,

31
00:01:18,202 --> 00:01:20,910
там нешта называецца
Функцыя фактарыяла, якія, як правіла,

32
00:01:20,910 --> 00:01:25,340
пазначаецца як клічнікам, які
вызначана над ўсіх станоўчых цэлых лікаў.

33
00:01:25,340 --> 00:01:28,850
І тое, н
фактарыяла вылічаецца

34
00:01:28,850 --> 00:01:31,050
гэта вы памножыць ўсе
лік менш, чым

35
00:01:31,050 --> 00:01:33,750
або роўна п together--
усе цэлыя менш, чым

36
00:01:33,750 --> 00:01:34,880
або роўна п разам.

37
00:01:34,880 --> 00:01:39,850
>> Так 5 фактарыяла 5 разоў
4 разы 3 разы 2 разы 1.

38
00:01:39,850 --> 00:01:43,020
І 4 фактарыяла 4 разы
3 разы 2 разы 1 і гэтак далей.

39
00:01:43,020 --> 00:01:44,800
Вы атрымліваеце ідэю.

40
00:01:44,800 --> 00:01:47,060
>> Як праграмісты, мы не
выкарыстоўваць п, клічнік.

41
00:01:47,060 --> 00:01:51,840
Так мы вызначым фактарыяла
Функцыя як факт п.

42
00:01:51,840 --> 00:01:56,897
І мы будзем выкарыстоўваць для стварэння фактарыяла
рэкурсіўны рашэнне праблемы.

43
00:01:56,897 --> 00:01:59,230
І я думаю, вы маглі б знайсці
што гэта нашмат больш візуальна

44
00:01:59,230 --> 00:02:02,380
прывабным, чым итеративный
версія гэтага якім

45
00:02:02,380 --> 00:02:05,010
мы таксама зірнем на ў адзін момант.

46
00:02:05,010 --> 00:02:08,310
>> Дык вось пару
facts-- каламбур intended--

47
00:02:08,310 --> 00:02:10,169
аб factorial--
фактарыяла.

48
00:02:10,169 --> 00:02:13,090
Фактарыяла 1, як я сказаў, гэта 1.

49
00:02:13,090 --> 00:02:15,690
Фактарыяла 2 у 2 разы 1.

50
00:02:15,690 --> 00:02:18,470
Фактарыяла 3 сакавіка
разы 2 разы 1, і гэтак далей.

51
00:02:18,470 --> 00:02:20,810
Мы гаварылі пра 4 і 5 ўжо.

52
00:02:20,810 --> 00:02:23,940
>> Але, гледзячы на ​​гэта, ці не так гэта?

53
00:02:23,940 --> 00:02:28,220
Ня Фактарыял 2 разоў
2 разы Фактарыял 1?

54
00:02:28,220 --> 00:02:31,130
Я маю на ўвазе, фактарыяла 1 студзеня.

55
00:02:31,130 --> 00:02:34,940
Дык чаму мы не можам проста сказаць, што,
так Фактарыял 2 у 2 разы 1,

56
00:02:34,940 --> 00:02:38,520
гэта сапраўды ўсяго 2 разы
фактарыяла 1?

57
00:02:38,520 --> 00:02:40,900
>> А потым распаўсюдзіць гэтую ідэю,
ня Фактарыял 3

58
00:02:40,900 --> 00:02:44,080
усяго 3 разы Фактарыял 2?

59
00:02:44,080 --> 00:02:50,350
І Фактарыял 4 у 4 разы
фактарыяла 3, і гэтак далей?

60
00:02:50,350 --> 00:02:52,530
На самай справе, факторный
з любога ліку можна проста

61
00:02:52,530 --> 00:02:54,660
быць выказана, калі мы неяк
з выканаць гэта назаўжды.

62
00:02:54,660 --> 00:02:56,870
Мы можам абагульніць выгляд
факторный праблема

63
00:02:56,870 --> 00:02:59,910
як гэта п раз у
Фактарыяла N мінус 1.

64
00:02:59,910 --> 00:03:04,840
Гэта п раз прадукт
ўсе нумары менш, чым мне.

65
00:03:04,840 --> 00:03:08,890
>> Гэтая ідэя, гэта
Абагульненне задачы,

66
00:03:08,890 --> 00:03:13,410
дазваляе рэкурсіўна
вызначыць функцыю фактарыяла.

67
00:03:13,410 --> 00:03:15,440
Калі вы вызначаеце функцыю
рэкурсіўна, ёсць

68
00:03:15,440 --> 00:03:17,470
дзве рэчы, якія павінны быць часткай гэтага.

69
00:03:17,470 --> 00:03:20,990
Вы павінны мець нешта, званае
базавы выпадак, які, калі вы запускаеце яго,

70
00:03:20,990 --> 00:03:22,480
будзе спыніць працэс рэкурсіўнага.

71
00:03:22,480 --> 00:03:25,300
>> У адваротным выпадку, функцыя, якая выклікае
у тым: як вы маглі imagine--

72
00:03:25,300 --> 00:03:26,870
можа працягвацца вечна.

73
00:03:26,870 --> 00:03:29,047
Функцыя выклікае функцыю
называе выклікі функцый

74
00:03:29,047 --> 00:03:30,380
функцыя выклікае функцыю.

75
00:03:30,380 --> 00:03:32,380
Калі вы не ёсць спосаб
, Каб спыніць яго, вашу праграму

76
00:03:32,380 --> 00:03:34,760
будзе эфектыўна затрымаўся
ў бясконцым цыкле.

77
00:03:34,760 --> 00:03:37,176
Гэта прывядзе да краху ў рэшце рэшт,
таму што ён будзе працаваць з памяці.

78
00:03:37,176 --> 00:03:38,990
Але гэта да справы не адносіцца.

79
00:03:38,990 --> 00:03:42,210
>> Мы павінны мець іншы спосаб, каб спыніць
рэчы, акрамя нашай праграмы разбіваючы,

80
00:03:42,210 --> 00:03:46,010
таму што праграма, якая разбівае гэта
верагодна, не прыгожа або элегантна.

81
00:03:46,010 --> 00:03:47,690
І так мы называем гэта базавы варыянт.

82
00:03:47,690 --> 00:03:50,610
Гэта простае рашэнне
да праблемы, які спыняецца

83
00:03:50,610 --> 00:03:52,770
рэкурсіўны працэс узнікнення.

84
00:03:52,770 --> 00:03:55,220
Дык вось адна частка
рэкурсіўная функцыя.

85
00:03:55,220 --> 00:03:56,820
>> Другая частка рэкурсіўны выпадак.

86
00:03:56,820 --> 00:03:59,195
І гэта, дзе Рэкурсія
на самай справе адбываецца.

87
00:03:59,195 --> 00:04:02,200
Гэта тое, дзе
функцыя называць сябе.

88
00:04:02,200 --> 00:04:05,940
>> Гэта не будзе называць сябе сапраўды
гэтак жа, як яго называлі.

89
00:04:05,940 --> 00:04:08,880
Гэта будзе невялікая змена
што робіць праблему гэта

90
00:04:08,880 --> 00:04:11,497
спрабуе вырашыць маленькі трохі менш.

91
00:04:11,497 --> 00:04:14,330
Але гэта, як правіла праходзіць даляр
рашэння большую частку раствора

92
00:04:14,330 --> 00:04:17,450
на іншы выклік па лініі.

93
00:04:17,450 --> 00:04:20,290
>> Які з гэтых поглядаў
як базавай выпадку тут?

94
00:04:20,290 --> 00:04:25,384
Які з гэтых выглядае як
простае рашэнне праблемы?

95
00:04:25,384 --> 00:04:27,550
У нас ёсць куча факториалов,
і мы маглі б працягваць

96
00:04:27,550 --> 00:04:30,470
адбываецца on-- 6, 7, 8, 9, 10 і гэтак далей.

97
00:04:30,470 --> 00:04:34,130
>> Але адзін з гэтых выглядае як
добры выпадак, каб быць базавым сцэнаром.

98
00:04:34,130 --> 00:04:35,310
Гэта вельмі простае рашэнне.

99
00:04:35,310 --> 00:04:37,810
Мы не павінны рабіць нічога асаблівага.

100
00:04:37,810 --> 00:04:40,560
>> Фактарыяла 1 знаходзіцца ўсяго ў 1.

101
00:04:40,560 --> 00:04:42,790
Мы не павінны рабіць нічога
множанне на ўсіх.

102
00:04:42,790 --> 00:04:45,248
Падобна на тое, калі мы збіраемся
каб паспрабаваць вырашыць гэтую праблему,

103
00:04:45,248 --> 00:04:47,600
і мы павінны спыніць
Рэкурсія дзе-небудзь,

104
00:04:47,600 --> 00:04:50,610
мы, верагодна, хочаце, каб спыніць
гэта калі мы атрымліваем да 1.

105
00:04:50,610 --> 00:04:54,580
Мы не хочам, каб спыніць раней.

106
00:04:54,580 --> 00:04:56,660
>> Так што, калі мы вызначаем
наш фактарыяла,

107
00:04:56,660 --> 00:04:58,690
вось каркас для
як мы маглі б гэта зрабіць.

108
00:04:58,690 --> 00:05:03,110
Мы павінны падключыць ў гэтых двух things--
базавы варыянт і рэкурсіўны выпадак.

109
00:05:03,110 --> 00:05:04,990
Што базавы варыянт?

110
00:05:04,990 --> 00:05:10,150
Калі п роўна 1, вярнуцца 1-- гэта
сапраўды простая задача вырашыць.

111
00:05:10,150 --> 00:05:11,890
>> Фактарыяла 1 студзеня.

112
00:05:11,890 --> 00:05:13,860
Гэта не 1 раз нічога.

113
00:05:13,860 --> 00:05:15,020
Гэта проста 1.

114
00:05:15,020 --> 00:05:17,170
Гэта вельмі проста факт.

115
00:05:17,170 --> 00:05:19,620
І так, што можа быць нашым базавым сцэнаром.

116
00:05:19,620 --> 00:05:24,730
Калі нас прайшло 1 у гэтым
Функцыя, мы проста вяртае 1.

117
00:05:24,730 --> 00:05:27,320
>> Што рэкурсіўны
Справа, верагодна, выглядаць?

118
00:05:27,320 --> 00:05:32,445
Для кожнага іншы нумар
акрамя 1, што карціна?

119
00:05:32,445 --> 00:05:35,780
Ну, калі мы бярэм
фактарыяла N,

120
00:05:35,780 --> 00:05:38,160
Гэта п раз фактарыяла N мінус 1.

121
00:05:38,160 --> 00:05:42,130
>> Калі мы бярэм фактарыяла з 3,
гэта ў 3 разы Фактарыял 3 мінус 1,

122
00:05:42,130 --> 00:05:43,070
або 2.

123
00:05:43,070 --> 00:05:47,330
І таму, калі мы не
гледзячы на ​​1, інакш

124
00:05:47,330 --> 00:05:51,710
Вяртанне ў п раз
Фактарыяла N мінус 1.

125
00:05:51,710 --> 00:05:53,210
Гэта даволі проста.

126
00:05:53,210 --> 00:05:57,360
>> І дзеля наяўнасці трохі
чысцей і больш элегантны код,

127
00:05:57,360 --> 00:06:01,440
ведаю, што калі ў нас ёсць завесы аднарадковы
або аднарадковы ўмоўныя галіны,

128
00:06:01,440 --> 00:06:04,490
мы можам пазбавіцца ад усіх з
Фігурныя дужкі вакол іх.

129
00:06:04,490 --> 00:06:06,850
Такім чынам, мы можам аб'яднаць гэта з гэтым.

130
00:06:06,850 --> 00:06:09,640
Гэта сапраўды гэтак жа,
Функцыянальнасць, як гэты.

131
00:06:09,640 --> 00:06:13,850
>> Я проста забіраючы кучаравыя
дужкі, таму што ёсць толькі адна лінія

132
00:06:13,850 --> 00:06:18,500
ўнутры гэтых умоўных галін.

133
00:06:18,500 --> 00:06:21,160
Такім чынам, гэтыя паводзяць сябе аднолькава.

134
00:06:21,160 --> 00:06:23,800
Калі п роўна 1, вяртае 1.

135
00:06:23,800 --> 00:06:28,351
У адваротным выпадку вярнуць п раз
фактарыяла N мінус 1.

136
00:06:28,351 --> 00:06:29,850
Такім чынам, мы робім праблему менш.

137
00:06:29,850 --> 00:06:33,850
Калі п пачынаецца як 5, мы збіраемся
вярнуцца 5 разоў фактарыяла 4.

138
00:06:33,850 --> 00:06:37,100
І мы ўбачым у хвіліну, калі мы гаворым
аб stack-- выкліку ў іншым відэа

139
00:06:37,100 --> 00:06:39,390
дзе мы гаворым пра
патэлефанаваць stack-- мы даведаемся

140
00:06:39,390 --> 00:06:41,630
аб тым, чаму менавіта гэты працэс працуе.

141
00:06:41,630 --> 00:06:46,970
>> Але ў той час, Фактарыял 5 кажа
вярнуцца ў 5 разоў фактарыяла 4, і 4

142
00:06:46,970 --> 00:06:49,710
будзе казаць, добра, добра, вяртанне
4 разы Фактарыял 3.

143
00:06:49,710 --> 00:06:51,737
І, як вы бачыце, мы
роду набліжаецца да 1.

144
00:06:51,737 --> 00:06:53,820
Мы ўсё бліжэй і
бліжэй да гэтай базавай выпадку.

145
00:06:53,820 --> 00:06:58,180
>> І як толькі мы трапілі ў базавы варыянт,
ўсе папярэднія функцыі

146
00:06:58,180 --> 00:07:00,540
ёсць адказ, які яны шукалі.

147
00:07:00,540 --> 00:07:03,900
Фактарыяла 2 казаў вяртанне
2 разы Фактарыял 1.

148
00:07:03,900 --> 00:07:06,760
Ну, факторный 1 вяртаецца 1.

149
00:07:06,760 --> 00:07:10,090
Такім чынам, заклік да фактарыяла
2 можа вярнуцца ў 2 разы 1,

150
00:07:10,090 --> 00:07:13,980
і даць, што спіной да фактарыяла
3, які чакаў гэтага выніку.

151
00:07:13,980 --> 00:07:17,110
>> І тады ён можа разлічваць
яго вынік, 3 разы лютым 6,

152
00:07:17,110 --> 00:07:18,907
і аддаць яго фактарыяла 4.

153
00:07:18,907 --> 00:07:20,740
І зноў, у нас ёсць
відэа ў стэку выклікаў

154
00:07:20,740 --> 00:07:23,810
дзе гэта паказана трохі
больш, чым тое, што я кажу цяпер.

155
00:07:23,810 --> 00:07:25,300
Але гэта ён.

156
00:07:25,300 --> 00:07:29,300
Гэта само па сабе рашэнне
разліку фактарыяла колькасці.

157
00:07:29,300 --> 00:07:31,527
>> Гэта толькі чатыры радкі кода.

158
00:07:31,527 --> 00:07:32,610
Гэта вельмі выдатна, ці не так?

159
00:07:32,610 --> 00:07:35,480
Гэта свайго роду сэксуальны.

160
00:07:35,480 --> 00:07:38,580
>> Такім чынам, у агульным, але не
заўсёды, рэкурсіўная функцыя

161
00:07:38,580 --> 00:07:41,190
можа замяніць цыклу ў
нерекурсивный функцыя.

162
00:07:41,190 --> 00:07:46,100
Дык вось, побач, гэта ітэрацыйныя
версія функцыі фактарыяла.

163
00:07:46,100 --> 00:07:49,650
Абодва гэтыя Статыстыка
роўна тое ж самае.

164
00:07:49,650 --> 00:07:52,170
>> Яны абодва разліку фактарыяла п.

165
00:07:52,170 --> 00:07:54,990
Версія злева
выкарыстоўвае рэкурсіі, каб зрабіць гэта.

166
00:07:54,990 --> 00:07:58,320
Версія аб праве
выкарыстоўвае ітэрацыю, каб зрабіць гэта.

167
00:07:58,320 --> 00:08:02,050
>> І заўважце, мы павінны абвясьціць
пераменная цэлы твор.

168
00:08:02,050 --> 00:08:02,940
І тады мы пятля.

169
00:08:02,940 --> 00:08:06,790
Пакуль п больш, чым 0, то
размнажацца, што прадукт па п

170
00:08:06,790 --> 00:08:09,890
і не змяншаючы п да
мы вылічыць твор.

171
00:08:09,890 --> 00:08:14,600
Такім чынам, гэтыя дзве функцыі, зноў жа,
зрабіць тое ж самае.

172
00:08:14,600 --> 00:08:19,980
Але яны не робяць гэта ў
сапраўды такім жа чынам.

173
00:08:19,980 --> 00:08:22,430
>> Зараз можна
больш чым адну базу

174
00:08:22,430 --> 00:08:25,770
так, ці больш чым адзін
Рэкурсіўны выпадак, у залежнасці

175
00:08:25,770 --> 00:08:27,670
на што ваша функцыя спрабуе зрабіць.

176
00:08:27,670 --> 00:08:31,650
Вы не абавязкова абмяжоўваецца толькі
адзін базавы выпадак або адзін рэкурсіўны

177
00:08:31,650 --> 00:08:32,370
выпадак.

178
00:08:32,370 --> 00:08:35,320
Так што прыклад чагосьці
з мноствам базавых выпадках

179
00:08:35,320 --> 00:08:37,830
можа быць this--
Фібаначы парадкавы нумар.

180
00:08:37,830 --> 00:08:41,549
>> Вы можаце ўспомніць з
элементарныя школьныя дні

181
00:08:41,549 --> 00:08:45,740
што паслядоўнасць Фібаначы вызначаецца
як this-- першы элемент 0.

182
00:08:45,740 --> 00:08:46,890
Другім элементам з'яўляецца 1.

183
00:08:46,890 --> 00:08:49,230
Абодва з іх з'яўляюцца проста па азначэнні.

184
00:08:49,230 --> 00:08:55,920
>> Тады кожны элемент вызначаецца
у выглядзе сумы п мінус 1 і мінус 2 н.

185
00:08:55,920 --> 00:09:00,330
Так трэцяга элемента
будзе 0 + 1 = 1.

186
00:09:00,330 --> 00:09:03,280
А потым чацвёрты элемент
будзе другі элемент, 1,

187
00:09:03,280 --> 00:09:06,550
плюс трэці элемент, 1.

188
00:09:06,550 --> 00:09:08,507
І, што б 2.

189
00:09:08,507 --> 00:09:09,340
І гэтак далей, і гэтак далей.

190
00:09:09,340 --> 00:09:11,680
>> Такім чынам, у гэтым выпадку, у нас ёсць два базавых выпадкаў.

191
00:09:11,680 --> 00:09:14,850
Калі п роўна 1, вярнуць 0.

192
00:09:14,850 --> 00:09:18,560
Калі п роўна 2, вяртае 1.

193
00:09:18,560 --> 00:09:25,930
У адваротным выпадку, вяртанне Фібаначы п
мінус 1 плюс Фібаначы п мінус 2.

194
00:09:25,930 --> 00:09:27,180
>> Дык вось некалькі базавых выпадкаў.

195
00:09:27,180 --> 00:09:29,271
Што аб некалькіх выпадках рэкурсіўных?

196
00:09:29,271 --> 00:09:31,520
Ну, ёсць сёе-тое
называецца гіпотэза Коллатц.

197
00:09:31,520 --> 00:09:34,630
Я не збіраюся казаць,
Вы ведаеце, што гэта такое,

198
00:09:34,630 --> 00:09:38,170
таму што гэта на самай справе наш апошні
Праблема для дадзенага відэа.

199
00:09:38,170 --> 00:09:43,220
І гэта наша практыкаванні
працаваць разам.

200
00:09:43,220 --> 00:09:46,760
>> Дык вось тое, што
Коллатц гіпотэза is--

201
00:09:46,760 --> 00:09:48,820
гэта ставіцца да любога натуральнага.

202
00:09:48,820 --> 00:09:51,500
І гэта прадугледжвае, што гэта
заўсёды можна вярнуцца

203
00:09:51,500 --> 00:09:55,060
1, калі вы выканаеце наступныя дзеянні.

204
00:09:55,060 --> 00:09:57,560
Калі п = 1, спыніцца.

205
00:09:57,560 --> 00:10:00,070
Мы вярнуліся да 1, калі п = 1.

206
00:10:00,070 --> 00:10:05,670
>> У адваротным выпадку, прайсці праз гэта
Працэс зноў на п дзеліцца на 2.

207
00:10:05,670 --> 00:10:08,200
І паглядзець, калі вы можаце атрымаць назад да 1.

208
00:10:08,200 --> 00:10:13,260
У адваротным выпадку, калі п няцотна, прайсці
гэты працэс зноў на 3n плюс 1,

209
00:10:13,260 --> 00:10:15,552
ці 3 разы N плюс 1.

210
00:10:15,552 --> 00:10:17,010
Дык вось у нас ёсць адзін базавы варыянт.

211
00:10:17,010 --> 00:10:18,430
Калі п роўна 1, спыніцца.

212
00:10:18,430 --> 00:10:20,230
Мы не робім больш Рэкурсія.

213
00:10:20,230 --> 00:10:23,730
>> Але ў нас ёсць два рэкурсіўных спраў.

214
00:10:23,730 --> 00:10:28,750
Калі п цотна, мы робім адну рэкурсіўнай
Справа, называючы п дзеліцца на 2.

215
00:10:28,750 --> 00:10:33,950
Калі п няцотна, мы робім розныя
рэкурсіўная справа па 3 разы п плюс 1.

216
00:10:33,950 --> 00:10:39,120
>> І таму мэта гэтага відэа
прыняць секунды, паўза відэа,

217
00:10:39,120 --> 00:10:42,440
і паспрабаваць напісаць гэта
рэкурсіўная функцыя Коллатц

218
00:10:42,440 --> 00:10:47,640
дзе вы праходзіце ў значэнні п, і
ён разлічвае, колькі крокаў

219
00:10:47,640 --> 00:10:52,430
патрабуецца, каб атрымаць 1, калі вы пачынаеце з п
і вы будзеце прытрымлівацца гэтыя крокі наверсе.

220
00:10:52,430 --> 00:10:56,660
Калі п = 1, ён прымае меры 0.

221
00:10:56,660 --> 00:11:00,190
У адваротным выпадку, гэта будзе
адзін крок плюс аднак

222
00:11:00,190 --> 00:11:06,200
шмат крокаў ён бярэ на любым п
дзеліцца на 2, калі п цотна, або 3n + 1

223
00:11:06,200 --> 00:11:08,100
калі п няцотна.

224
00:11:08,100 --> 00:11:11,190
>> Зараз, я паклаў на экране тут
пару тэставых рэчаў для вас,

225
00:11:11,190 --> 00:11:15,690
пару тэставых варыянтаў для вас, каб убачыць
тое, што гэтыя розныя нумары Collatz з'яўляюцца,

226
00:11:15,690 --> 00:11:17,440
а таксама ілюстрацыя
пра крокі, якія

227
00:11:17,440 --> 00:11:20,390
трэба перажыць, каб вы маглі
накшталт разглядаюць гэты працэс у дзеянні.

228
00:11:20,390 --> 00:11:24,222
Такім чынам, калі п роўна
1, Коллатц п 0.

229
00:11:24,222 --> 00:11:26,180
Вы не павінны рабіць
нічога, каб вярнуцца да 1.

230
00:11:26,180 --> 00:11:27,600
Вы ўжо там.

231
00:11:27,600 --> 00:11:30,550
>> Калі п 2, ён займае
адзін крок, каб дабрацца да 1.

232
00:11:30,550 --> 00:11:31,810
Вы пачынаеце з 2.

233
00:11:31,810 --> 00:11:33,100
Добра, 2 не роўная 1.

234
00:11:33,100 --> 00:11:36,580
Такім чынам, гэта будзе адзін крок
плюс, аднак многія крокі, якія ён

235
00:11:36,580 --> 00:11:38,015
бярэ на п дзеліцца на 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 дзеліцца на 2 студзеня.

238
00:11:42,910 --> 00:11:47,200
Так ён прымае адзін крок плюс аднак
шмат крокаў патрабуецца для 1.

239
00:11:47,200 --> 00:11:49,720
1 займае нулявыя крокі.

240
00:11:49,720 --> 00:11:52,370
>> Для 3, як вы можаце бачыць, ёсць
ўдзел нямала крокаў.

241
00:11:52,370 --> 00:11:53,590
Вы ідзяце ад 3.

242
00:11:53,590 --> 00:11:56,710
І тады вы ідзяце ў
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Гэта зойме сем крокаў, каб вярнуцца да 1.

244
00:11:58,804 --> 00:12:01,220
І, як вы бачыце, ёсць
некалькі іншых выпадкаў тут выпрабаванняў

245
00:12:01,220 --> 00:12:02,470
каб праверыць вашу праграму.

246
00:12:02,470 --> 00:12:03,970
Такім чынам, яшчэ раз, паўза відэа.

247
00:12:03,970 --> 00:12:09,210
І я пайду скакаць назад цяпер
тое, што сам працэс тут,

248
00:12:09,210 --> 00:12:11,390
тое, што гэтая гіпотэза.

249
00:12:11,390 --> 00:12:14,140
>> Глядзіце, калі вы можаце высветліць,
як вызначыць Collatz п

250
00:12:14,140 --> 00:12:19,967
такім чынам, што ён падлічвае, колькі
крокі трэба, каб атрымаць 1.

251
00:12:19,967 --> 00:12:23,050
Так, мы спадзяемся, вы паўзу відэа
і вы не проста чакае мяне

252
00:12:23,050 --> 00:12:25,820
каб даць вам адказ тут.

253
00:12:25,820 --> 00:12:29,120
Але калі вы, ну,
вось адказ у любым выпадку.

254
00:12:29,120 --> 00:12:33,070
>> Дык вось магчымае вызначэнне
функцыі Collatz.

255
00:12:33,070 --> 00:12:35,610
Наша база case--, калі п
роўны 1, мы вяртаемся 0.

256
00:12:35,610 --> 00:12:38,250
Гэта не прымаць якія-небудзь
крокі, каб вярнуцца да 1.

257
00:12:38,250 --> 00:12:42,710
>> У адваротным выпадку, у нас ёсць два рэкурсіўны cases--
адным для цотных лікаў і адзін для няцотных.

258
00:12:42,710 --> 00:12:47,164
Як я праверыць цотных лікаў
каб праверыць, калі п па модулю 2 роўны 0.

259
00:12:47,164 --> 00:12:49,080
Гэта, у асноўным, зноў жа,
задаючы пытанне,

260
00:12:49,080 --> 00:12:54,050
калі ўспомніць, што мод is-- калі я
падзяляй п на 2 не існуе ніякага астатку?

261
00:12:54,050 --> 00:12:55,470
Гэта было б цотная колькасць.

262
00:12:55,470 --> 00:13:01,370
>> І так, калі п па модулю 2 роўны 0
Тэставанне гэта цотная колькасць.

263
00:13:01,370 --> 00:13:04,250
Калі гэта так, я хачу, каб вярнуць 1,
таму што гэта, безумоўна,

264
00:13:04,250 --> 00:13:09,270
адзін крок плюс Collatz з
усе лік палова мяне.

265
00:13:09,270 --> 00:13:13,910
У адваротным выпадку, я хачу, каб вярнуць 1
плюс Коллатц 3 разы N плюс 1.

266
00:13:13,910 --> 00:13:16,060
Гэта быў іншы
рэкурсіўны крок, які мы

267
00:13:16,060 --> 00:13:19,470
маглі б распачаць для разліку
Collatz-- колькасць крокаў

268
00:13:19,470 --> 00:13:22,610
ён прымае, каб вярнуцца
1 прысвоены нумар.

269
00:13:22,610 --> 00:13:24,610
Так, мы спадзяемся, гэты прыклад
даў вам крыху

270
00:13:24,610 --> 00:13:26,620
з густу рэкурсіўных працэдур.

271
00:13:26,620 --> 00:13:30,220
Спадзяюся, вы думаеце, код
трохі больш прыгожым, калі рэалізаваны

272
00:13:30,220 --> 00:13:32,760
у элегантным рэкурсіўнай чынам.

273
00:13:32,760 --> 00:13:35,955
Але нават калі няма, Рэкурсія з'яўляецца
сапраўды магутны інструмент, тым не менш.

274
00:13:35,955 --> 00:13:38,330
І так што гэта вызначана нешта
каб атрымаць сваю галаву вакол,

275
00:13:38,330 --> 00:13:41,360
таму што вы будзеце ў стане стварыць
Даволі халаднавата, якія выкарыстоўваюць Рэкурсія праграмы

276
00:13:41,360 --> 00:13:45,930
якія маглі б быць складаным, каб напісаць
калі вы выкарыстоўваеце завес і ітэрацыі.

277
00:13:45,930 --> 00:13:46,980
Я Дуг Лойд.

278
00:13:46,980 --> 00:13:48,780
Гэта CS50.

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