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

2
00:00:07,800 --> 00:00:10,190
>> ЗАМИЛА: Да бисмо разумели
рекурзије, морате

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

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
Узми ову функцију, здраво, празнина функција
који заузима инт н као улаз.

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
који се извршава хи (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
Убаците свој терминал, или рун.цс50.нет,
и написати функцију Сум

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
На пример, ова функција, фоо, то
мења вредност датог чвора и

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. и ФОО ће
бити позван на децу тог чвора,

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
Како бисте уредили фоо?

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
Моје име је Замила, а то је ЦС50.

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