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
Вземете тази проста функция, Foo, че
приема единствен низ като вход и

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
необходима за поканата да ФОРМАТ.

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 н като вход.

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
>> OK.

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 пъти два пъти 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
The рекурсивно повикване няма да бъде същият
за всички случаи, с изключение на основата

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
Ние виждаме, че четири факториел съдържа
умножение 3 пъти 2 пъти 1, на

69
00:03:49,120 --> 00:03:51,590
същото определение като 3 факториел.

70
00:03:51,590 --> 00:03:56,950
Така 4 факторен е равно на четири пъти 3
факториел, и така нататък и така нататък ни

71
00:03:56,950 --> 00:04:02,170
модел се придържа до един факториел, което
по дефиниция е равно на 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
п факторен е равна на N пъти
факториела на п минус 1.

75
00:04:13,260 --> 00:04:14,370
И нашата база случай?

76
00:04:14,370 --> 00:04:17,370
Това просто ще бъде нашата дефиниция
на един факториел.

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
ние ще се върне един.

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
Per нашата функция е равен
4 пъти факторен (3).

85
00:04:39,420 --> 00:04:43,040
Повдигане (3) е равна на
3 пъти факторен (2).

86
00:04:43,040 --> 00:04:48,700
Повдигане (2) е равна на два пъти
факториел (1), която връща 1.

87
00:04:48,700 --> 00:04:52,490
Повдигане (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
числа от N до 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
The рекурсивно повикване или обходни пътища в
лявата или дясната възел, но по-

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
Например, тази функция, Фу, че
променя стойността на даден възел и

136
00:07:31,650 --> 00:07:33,830
всичко на децата си до едно.

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
Ние променете стойността на един, и след това се обадете
нашата функция в ляво, както и

142
00:07:47,930 --> 00:07:49,600
както отдясно.

143
00:07:49,600 --> 00:07:53,910
Функцията, Foo, се нарича в ляво
под-дърво, на първо място, така че лявата възел

144
00:07:53,910 --> 00:07:57,730
ще бъде преразпределено на една и 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