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