1
00:00:00,000 --> 00:00:07,800

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Для того, щоб зрозуміти,
рекурсія, ви повинні

3
00:00:10,190 --> 00:00:13,820
спочатку зрозуміти рекурсію.

4
00:00:13,820 --> 00:00:17,280
Маючи рекурсію в програмних дизайну коштів
що у вас є самосправочние

5
00:00:17,280 --> 00:00:18,570
визначення.

6
00:00:18,570 --> 00:00:21,520
Рекурсивні структури даних, наприклад,
це структури даних, які

7
00:00:21,520 --> 00:00:23,990
включають себе в
їх визначення.

8
00:00:23,990 --> 00:00:27,160
Але сьогодні ми збираємося зосередитися
на рекурсивних функцій.

9
00:00:27,160 --> 00:00:31,160
>> Нагадаємо, що функції приймають входи,
аргументи, і повертає значення, як і їх

10
00:00:31,160 --> 00:00:34,480
Вихід в особі
ця схема тут.

11
00:00:34,480 --> 00:00:38,060
Ми будемо думати про поле як тіло
функція, що містить набір

12
00:00:38,060 --> 00:00:42,340
інструкції, які інтерпретують
вхід і забезпечують вихід.

13
00:00:42,340 --> 00:00:45,660
При більш ретельному вивченні всередині тіла
функція може виявити виклики

14
00:00:45,660 --> 00:00:47,430
інші функції, а також.

15
00:00:47,430 --> 00:00:51,300
Візьміть цю просту функцію, Фу, що
займає один рядок в якості вхідних даних і

16
00:00:51,300 --> 00:00:54,630
друкує скільки листів
що рядок має.

17
00:00:54,630 --> 00:00:58,490
Функція STRLEN, для довжини рядка,
називається, вихід якого

18
00:00:58,490 --> 00:01:01,890
потрібно для виклику Printf.

19
00:01:01,890 --> 00:01:05,770
>> Тепер, те, що робить рекурсивную функцію
особливого в тому, що він називає себе.

20
00:01:05,770 --> 00:01:09,610
Ми можемо уявити цей рекурсивний
подзвонити з цим помаранчевої стрілкою

21
00:01:09,610 --> 00:01:11,360
цикл назад до себе.

22
00:01:11,360 --> 00:01:15,630
Але виконання себе знову буде тільки
зробити ще один рекурсивний виклик, і

23
00:01:15,630 --> 00:01:17,150
ще і ще.

24
00:01:17,150 --> 00:01:19,100
Але рекурсивні функції
не може бути нескінченним.

25
00:01:19,100 --> 00:01:23,490
Вони повинні покласти край так чи інакше, або ваш
Програма буде працювати вічно.

26
00:01:23,490 --> 00:01:27,680
>> Так що ми повинні знайти спосіб розірвати
з рекурсивних викликів.

27
00:01:27,680 --> 00:01:29,900
Базовий варіант Ми називаємо це.

28
00:01:29,900 --> 00:01:33,570
Коли базовий варіант умова виконується,
функція повертає без

29
00:01:33,570 --> 00:01:34,950
другий рекурсивний виклик.

30
00:01:34,950 --> 00:01:39,610
Візьміть цю функцію, привіт, порожній функції
, Яка приймає Int N в якості вхідних даних.

31
00:01:39,610 --> 00:01:41,260
Базовий варіант стоїть на першому місці.

32
00:01:41,260 --> 00:01:46,220
Якщо п менше нуля, друку побачення і
повернутися У всіх інших випадках,

33
00:01:46,220 --> 00:01:49,400
Функція буде друкувати привіт і виконати
рекурсивний виклик.

34
00:01:49,400 --> 00:01:53,600
Ще один дзвінок до функції привіт з
зменшується вхідне значення.

35
00:01:53,600 --> 00:01:56,790
>> Тепер, навіть при тому, що ми друкуємо привіт,
функція не припинити поки ми не

36
00:01:56,790 --> 00:02:00,370
повернути його повертається тип,
в цьому випадку порожнечі.

37
00:02:00,370 --> 00:02:04,830
Таким чином, для кожного п, крім базового варіанту,
ця функція привіт повернеться привіт

38
00:02:04,830 --> 00:02:06,890
н мінус 1.

39
00:02:06,890 --> 00:02:10,050
Так як ця функція є нікчемним, хоча, ми
НЕ буде явно тип повертається тут.

40
00:02:10,050 --> 00:02:12,000
Ми просто виконати функцію.

41
00:02:12,000 --> 00:02:16,960
Так називаючи привет (3) друкуватиме привіт і
виконати привет (2), який виконує привет (1) один

42
00:02:16,960 --> 00:02:20,560
який виконує Hi (0), де
базовий варіант умова.

43
00:02:20,560 --> 00:02:24,100
Так привет (0) друкує побачення і повертається.

44
00:02:24,100 --> 00:02:24,990
>> ОК.

45
00:02:24,990 --> 00:02:28,690
Так що тепер ми розуміємо основи
рекурсивні функції, які вони повинні

46
00:02:28,690 --> 00:02:32,730
щонайменше один базовий варіант, а також
рекурсивний виклик, давайте перейдемо до

47
00:02:32,730 --> 00:02:34,120
більш значущим прикладом.

48
00:02:34,120 --> 00:02:37,830
Той, який не просто повернути
НЕ анулює ні на що.

49
00:02:37,830 --> 00:02:41,340
>> Давайте поглянемо на факторіала
Операція використовується найчастіше в

50
00:02:41,340 --> 00:02:43,660
імовірнісні розрахунки.

51
00:02:43,660 --> 00:02:48,120
Факторіал п є твором кожен
позитивне ціле число менше

52
00:02:48,120 --> 00:02:49,400
і дорівнює п.

53
00:02:49,400 --> 00:02:56,731
Так факторний п'ять у 5 разів 4 раз
3 раз 2 раз 1, щоб дати 120.

54
00:02:56,731 --> 00:03:01,400
Чотири факторний в 4 рази 3 рази
2 раз 1 з отриманням 24.

55
00:03:01,400 --> 00:03:04,910
І те ж саме правило застосовується
будь-яке позитивне ціле.

56
00:03:04,910 --> 00:03:08,670
>> Отже, як ми могли б написати рекурсивний
функція, яка обчислює факторіал

57
00:03:08,670 --> 00:03:09,960
ряду?

58
00:03:09,960 --> 00:03:14,700
Ну, ми повинні визначити, як
базовий варіант і рекурсивний виклик.

59
00:03:14,700 --> 00:03:18,250
Рекурсивний виклик буде таким же,
для всіх випадків за основу, крім

60
00:03:18,250 --> 00:03:21,420
випадок, який означає, що ми повинні будемо
знайти модель, яка дасть нам нашу

61
00:03:21,420 --> 00:03:23,350
Бажаний результат.

62
00:03:23,350 --> 00:03:30,270
>> Для цього прикладу, подивимося, як 5 факторіала
включає множення 4 по 3 на 2 на 1

63
00:03:30,270 --> 00:03:33,010
І в той же множення
знаходиться тут,

64
00:03:33,010 --> 00:03:35,430
Визначення 4 факторіала.

65
00:03:35,430 --> 00:03:39,810
Отже, ми бачимо, що 5 факторіал
всього 5 разів 4 факторний.

66
00:03:39,810 --> 00:03:43,360
Тепер же ця модель застосовується
до 4 факторіал, а?

67
00:03:43,360 --> 00:03:44,280
Так.

68
00:03:44,280 --> 00:03:49,120
Ми бачимо, що 4 факторний містить
множення 3 рази 2 раз 1,

69
00:03:49,120 --> 00:03:51,590
Сам ж визначення, як 3 факторіала.

70
00:03:51,590 --> 00:03:56,950
Так 4 факторний дорівнює 4 рази 3
факторний, і так далі і тому подібне нашої

71
00:03:56,950 --> 00:04:02,170
шаблон не прилипає до 1 факторіала, яка
за визначенням дорівнює 1.

72
00:04:02,170 --> 00:04:04,950
>> Там немає іншої позитивний
цілі залишили.

73
00:04:04,950 --> 00:04:07,870
Тому у нас є зразок для
наш рекурсивний виклик.

74
00:04:07,870 --> 00:04:13,260
н факторний дорівнює п раз
факторіал п мінус 1.

75
00:04:13,260 --> 00:04:14,370
І наш базовий сценарій?

76
00:04:14,370 --> 00:04:17,370
Це буде просто наше визначення
1 факторіала.

77
00:04:17,370 --> 00:04:19,995
>> Так що тепер ми можемо перейти до написання
код функції.

78
00:04:19,995 --> 00:04:24,110
Для базового варіанту, ми будемо мати
стан п дорівнює дорівнює 1, де

79
00:04:24,110 --> 00:04:25,780
ми повернемося 1.

80
00:04:25,780 --> 00:04:29,280
Тоді перейти на рекурсивного виклику,
ми повернемося п раз

81
00:04:29,280 --> 00:04:32,180
Факторіал п мінус 1.

82
00:04:32,180 --> 00:04:33,590
>> Тепер давайте перевіримо це наше.

83
00:04:33,590 --> 00:04:35,900
Давайте спробуємо факторіала 4.

84
00:04:35,900 --> 00:04:39,420
За нашої функції він дорівнює
в 4 рази факторіал (3).

85
00:04:39,420 --> 00:04:43,040
Факторіал (3) дорівнює
3 рази факторних (2).

86
00:04:43,040 --> 00:04:48,700
Факторіал (2) дорівнює 2 рази
факторний (1), яка повертає 1.

87
00:04:48,700 --> 00:04:52,490
Факторіал (2) тепер повертає 2 рази 1, 2.

88
00:04:52,490 --> 00:04:55,960
Факторіал (3) тепер можна повернутися
3 рази 2, 6.

89
00:04:55,960 --> 00:05:02,490
І, нарешті, факторний (4)
повертає 4 рази 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Якщо виникають будь-які труднощі
з рекурсивного виклику, робити вигляд, що

91
00:05:06,780 --> 00:05:09,660
функція працює вже.

92
00:05:09,660 --> 00:05:13,450
Те, що я маю на увазі, що ви повинні
довіряти своїм рекурсивні виклики, щоб повернутися

93
00:05:13,450 --> 00:05:15,100
правильні значення.

94
00:05:15,100 --> 00:05:18,960
Наприклад, якщо я знаю, що
факторний (5) дорівнює 5 раз

95
00:05:18,960 --> 00:05:24,870
факторний (4), я збираюся вірити, що
факторний (4) дасть мені 24.

96
00:05:24,870 --> 00:05:28,510
Думайте про це як змінної, якщо ви
буде, як якщо б ви вже визначені

97
00:05:28,510 --> 00:05:30,070
факторіал (4).

98
00:05:30,070 --> 00:05:33,850
Таким чином, для будь-якого факторіала (п), це
твір п і

99
00:05:33,850 --> 00:05:35,360
попередній факторний.

100
00:05:35,360 --> 00:05:38,130
І це попередня факторний
виходить шляхом виклику

101
00:05:38,130 --> 00:05:41,330
Факторіал п мінус 1.

102
00:05:41,330 --> 00:05:45,130
>> Так от, бачите, якщо ви можете реалізувати
рекурсивна функція себе.

103
00:05:45,130 --> 00:05:50,490
Завантажте ваш термінал, або run.cs50.net,
і написати функцію суму

104
00:05:50,490 --> 00:05:54,770
, Яка приймає число п і повертає
Сума всіх підряд позитивний

105
00:05:54,770 --> 00:05:57,490
цілі числа від п до 1.

106
00:05:57,490 --> 00:06:01,000
Я виписав суми деяких
значення, які допоможуть вам наш.

107
00:06:01,000 --> 00:06:04,030
По-перше, з'ясувати,
базовий варіант стан.

108
00:06:04,030 --> 00:06:06,170
Потім подивіться на суми (5).

109
00:06:06,170 --> 00:06:09,270
Чи можете ви висловити її через
іншої суми?

110
00:06:09,270 --> 00:06:11,290
Тепер, що стосується суми (4)?

111
00:06:11,290 --> 00:06:15,630
Як ви можете висловити суму (4)
з точки зору іншої суми?

112
00:06:15,630 --> 00:06:19,655
>> Якщо у вас є сума (5) і сума (4)
виражається через інших сум, см.

113
00:06:19,655 --> 00:06:22,970
якщо ви можете визначити
шаблон для суми (п).

114
00:06:22,970 --> 00:06:26,190
Якщо ні, спробуйте кілька інших номерів
і виражати свої суми в

115
00:06:26,190 --> 00:06:28,410
умови ще номера.

116
00:06:28,410 --> 00:06:31,930
Виявляючи закономірності для дискретних
номера, ви добре на вашому шляху до

117
00:06:31,930 --> 00:06:34,320
виявлення зразок для будь-якого п.

118
00:06:34,320 --> 00:06:38,040
>> Рекурсія це дійсно потужний інструмент,
тому, звичайно, це не обмежується

119
00:06:38,040 --> 00:06:39,820
математичні функції.

120
00:06:39,820 --> 00:06:44,040
Рекурсія може бути використаний вельми ефективно
при роботі з деревами, наприклад.

121
00:06:44,040 --> 00:06:47,210
Перевірте вистачає дерев для
більш ретельний аналіз, але зараз

122
00:06:47,210 --> 00:06:51,140
нагадати, що бінарні дерева пошуку, в
Зокрема, складаються з вузлів, кожен

123
00:06:51,140 --> 00:06:53,820
зі значенням і двох покажчиків вузлів.

124
00:06:53,820 --> 00:06:57,270
Як правило, вона представлена
батьківський вузол, що має один рядок, що вказує

125
00:06:57,270 --> 00:07:01,870
на лівий вузол дітьми та один
в потрібне дочірнього вузла.

126
00:07:01,870 --> 00:07:04,510
Структура бінарного пошуку
дерево добре піддається

127
00:07:04,510 --> 00:07:05,940
до рекурсивного пошуку.

128
00:07:05,940 --> 00:07:09,730
Рекурсивний виклик або переходить в
вліво або право вузол, але більш

129
00:07:09,730 --> 00:07:10,950
того, що в дереві короткого замикання.

130
00:07:10,950 --> 00:07:15,690
>> Припустимо, ви хочете виконати операцію
кожен вузол в двійковому дереві.

131
00:07:15,690 --> 00:07:17,410
Як ви могли б піти з цього приводу?

132
00:07:17,410 --> 00:07:20,600
Ну, ви могли б написати рекурсивную
функція, яка виконує операцію

133
00:07:20,600 --> 00:07:24,450
на батьківському сайті і робить рекурсивний
подзвонити в тій же функції,

134
00:07:24,450 --> 00:07:27,630
проходячи в лівій і
правий дочірні вузли.

135
00:07:27,630 --> 00:07:31,650
Наприклад, це функція, Foo, що
змінює значення даного вузла і

136
00:07:31,650 --> 00:07:33,830
всі його дітей до 1.

137
00:07:33,830 --> 00:07:37,400
База випадку нульового причин вузлів
функція для повернення, вказуючи

138
00:07:37,400 --> 00:07:41,290
що немає ніяких вузлів
залишили в цьому поддереве.

139
00:07:41,290 --> 00:07:42,620
>> Давайте йти через нього.

140
00:07:42,620 --> 00:07:44,340
Перший батько 13.

141
00:07:44,340 --> 00:07:47,930
Ми міняємо його значення на 1, а потім викликати
наша функція зліва, а

142
00:07:47,930 --> 00:07:49,600
як право.

143
00:07:49,600 --> 00:07:53,910
Функція, Фу, називається зліва
суб-дерево спочатку, так що ліва вузол

144
00:07:53,910 --> 00:07:57,730
буде переведений на 1 і Foo буде
назвати на дітей цього вузла,

145
00:07:57,730 --> 00:08:01,900
Перший лівий, а потім правий,
і так далі і тому подібне.

146
00:08:01,900 --> 00:08:05,630
І сказати їм, що філії не мають
більше дітей, так само процес

147
00:08:05,630 --> 00:08:09,700
буде тривати протягом правильних дітей
до вузли все дерево в НЕ

148
00:08:09,700 --> 00:08:11,430
переведений в 1.

149
00:08:11,430 --> 00:08:15,390
>> Як ви можете бачити, ви не обмежені
просто один рекурсивний виклик.

150
00:08:15,390 --> 00:08:17,930
Так само, як багато хто, як буде отримати роботу.

151
00:08:17,930 --> 00:08:21,200
Що якщо у вас на дерево, де кожен
вузол було троє дітей,

152
00:08:21,200 --> 00:08:23,100
Зліва, середній, і правильно?

153
00:08:23,100 --> 00:08:24,886
Як би ви змінити Foo?

154
00:08:24,886 --> 00:08:25,860
Ну, просто.

155
00:08:25,860 --> 00:08:30,250
Просто додати ще один рекурсивний виклик і
пройти в покажчику середнього вузла.

156
00:08:30,250 --> 00:08:34,549
>> Рекурсія є дуже потужним і не
кажучи елегантно, але це може бути

157
00:08:34,549 --> 00:08:38,010
складна концепція на перший, так тому і бути
пацієнтові і не поспішайте.

158
00:08:38,010 --> 00:08:39,370
Почніть з базового варіанту.

159
00:08:39,370 --> 00:08:42,650
Це, як правило, найпростіший для виявлення,
а потім ви можете працювати

160
00:08:42,650 --> 00:08:43,830
назад звідти.

161
00:08:43,830 --> 00:08:46,190
Ви знаєте, що вам потрібно для досягнення ваших
базовий варіант, так що може

162
00:08:46,190 --> 00:08:47,760
дати вам кілька порад.

163
00:08:47,760 --> 00:08:53,120
Спробуйте висловити один конкретний випадок в
умови інших випадках, або в підмножин.

164
00:08:53,120 --> 00:08:54,700
>> Дякуємо за перегляд цієї короткої.

165
00:08:54,700 --> 00:08:58,920
Принаймні, тепер ви можете
зрозуміти жарти, як це.

166
00:08:58,920 --> 00:09:01,250
Мене звуть Zamyla, і це CS50.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Візьміть цю функцію, привіт,
недійсними функція, яка приймає

169
00:09:07,170 --> 00:09:09,212
внутр, п, в якості вхідних даних.

170
00:09:09,212 --> 00:09:11,020
Базовий варіант стоїть на першому місці.

171
00:09:11,020 --> 00:09:14,240
Якщо п менше 0, друку
"До побачення" і повернення.

172
00:09:14,240 --> 00:09:15,490