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 разу 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 плюс Фібоначчі п мінус 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