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
И начинът, N
факторен се изчислява

34
00:01:28,850 --> 00:01:31,050
се умножите всички
цифрите по-малко от

35
00:01:31,050 --> 00:01:33,750
или равна на N 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
The факториела 1, както казах, е един.

49
00:02:13,090 --> 00:02:15,690
The факториела 2 е 2 пъти по 1.

50
00:02:15,690 --> 00:02:18,470
The факториела 3 е 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 е 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
Това е N пъти продукта от
всички числа по-малки от мен.

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
>> В противен случай, функция, която призовава
itself-- както може би 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
Имаме един куп factorials,
и можем да продължим

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
>> The факториела 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
ние вероятно искате да спрете
то когато стигнем до един.

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
>> The факториела 1 е 1.

112
00:05:11,890 --> 00:05:13,860
Това не е нещо, 1 пъти.

113
00:05:13,860 --> 00:05:15,020
Това е просто един.

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
За всеки друг номер
освен една, каква е схемата?

119
00:05:32,445 --> 00:05:35,780
Е, ако си говорим
факториела на п,

120
00:05:35,780 --> 00:05:38,160
това е п пъти факториела на п минус 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
В противен случай се върне н пъти
факториела на п минус 1.

136
00:06:28,351 --> 00:06:29,850
Така че ние правим проблема по-малък.

137
00:06:29,850 --> 00:06:33,850
Ако п започва като 5, ние ще
върнете 5 пъти факториела на четири.

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
ще кажа, OK, добре, възвръщаемост
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 пъти 2 е 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 плюс Фибоначи на N минус 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
Е, има нещо
наречено хипотезата Collatz.

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
>> Така че тук е това, което
Collatz предположение 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
>> В противен случай, проверете това
процес отново на п разделена на две.

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
Ако п е дори това, ние правим една рекурсивни
случай, наричайки п разделена на две.

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
и да се опитаме и да напиша тази
рекурсивни функции Collatz

218
00:10:42,440 --> 00:10:47,640
където можете да премине в стойност п и
той изчислява колко го стъпки

219
00:10:47,640 --> 00:10:52,430
необходимо, за да стигнем до един, ако започнете от п
и да следвате тези стъпки до горе.

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
много стъпки, които предприема от двете п
разделена на две, ако п е дори, или 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, Collatz на п е 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, е необходимо
една стъпка за да стигнем до един.

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 е разделена на две 1.

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
така, че да изчислява колко
стъпки е необходимо да стигнем до един.

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-- ако I
разделение п от 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
плюс Collatz 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