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
потребни за повик за 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
looping назад кон себе.

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

33
00:01:46,220 --> 00:01:49,400
функција ќе печати Здраво и изврши
рекурзивен повик.

34
00:01:49,400 --> 00:01:53,600
Уште еден повик до функцијата hi со
на decremented влезна вредност.

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
Значи за секој n освен база случај,
оваа функција hi ќе се врати hi-

38
00:02:04,830 --> 00:02:06,890
на n минус 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
Па повикувајќи hi (3) ќе се печати Здраво и
изврши hi (2), кој извршува hi (1) еден

42
00:02:16,960 --> 00:02:20,560
, кој извршува hi (0), каде што
база случај услов е исполнет.

43
00:02:20,560 --> 00:02:24,100
Па hi (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
Фактор од n е производ на сите
позитивен цел број помалку од

52
00:02:48,120 --> 00:02:49,400
и еднаков на n.

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
n факторен е еднаква на n пати
факториел од n минус 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
За база случај, ќе имаме
состојба n еднаква еднакво на 1, каде што

79
00:04:24,110 --> 00:04:25,780
ние ќе се врати 1.

80
00:04:25,780 --> 00:04:29,280
Потоа се движи кон рекурзивен повик,
ние ќе се вратат n пати

81
00:04:29,280 --> 00:04:32,180
факториел од n минус 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
Значи за секој факториел (n), тоа е
производ на n и

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
факториел од n минус 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
кој ги зема цел број n и се враќа на
Збирот на сите последователни позитивни

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
ако може да се идентификуваат
модел за сума (n).

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
идентификување на моделот за било n.

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
Функцијата, foo, се нарекува на левата
под-дрво прво, па на лево јазол

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
на цел број, n, како влез.

170
00:09:09,212 --> 00:09:11,020
Основното сценарио се случи прво.

171
00:09:11,020 --> 00:09:14,240
Ако n е помал од 0, печатење
"Збогум" и да се врати.

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