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