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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: anlamaq üçün
recursion, siz

3
00:00:10,190 --> 00:00:13,820
ilk recursion başa düşürük.

4
00:00:13,820 --> 00:00:17,280
Proqram dizayn vasitələri recursion olan
Siz öz-özünə sened var ki,

5
00:00:17,280 --> 00:00:18,570
anlayışlar.

6
00:00:18,570 --> 00:00:21,520
Recursive data strukturları, məsələn,
data strukturları var ki,

7
00:00:21,520 --> 00:00:23,990
özlərini daxildir
onların təriflər.

8
00:00:23,990 --> 00:00:27,160
Ancaq bu gün biz diqqət olacaq
recursive funksiyaları.

9
00:00:27,160 --> 00:00:31,160
>> , Funksiyaları giriş almaq Xatırladaq ki,
arqumentlər və kimi bir dəyər qayıtmaq onların

10
00:00:31,160 --> 00:00:34,480
təmsil output
burada bu diagram.

11
00:00:34,480 --> 00:00:38,060
Biz orqanı kimi qutusuna düşünmək lazımdır
toplusunu ibarət funksiyası,

12
00:00:38,060 --> 00:00:42,340
Bu şərh edən təlimat
Giriş və çıxış təmin edir.

13
00:00:42,340 --> 00:00:45,660
Bədən daxilində yaxından nəzər alaraq
funksiyası zənglər aşkar edə bilər

14
00:00:45,660 --> 00:00:47,430
digər funksiyaları həmçinin.

15
00:00:47,430 --> 00:00:51,300
Bu sadə funksiyası, foo edin ki,
giriş kimi bir simli edir və

16
00:00:51,300 --> 00:00:54,630
izləri neçə məktublar
ki, simli var.

17
00:00:54,630 --> 00:00:58,490
String uzunluğu üçün funksiyası strlen,
onun çıxış edir, adlanır

18
00:00:58,490 --> 00:01:01,890
printf zəng üçün tələb olunur.

19
00:01:01,890 --> 00:01:05,770
>> İndi nə recursive funksiyası edir
xüsusi özünü çağırır edir.

20
00:01:05,770 --> 00:01:09,610
Biz bu recursive təmsil edə bilər
bu narıncı arrow ilə zəng

21
00:01:09,610 --> 00:01:11,360
geri özü üçün loop.

22
00:01:11,360 --> 00:01:15,630
Amma yenə özünü həyata yalnız olacaq
başqa recursive zəng etmək, və

23
00:01:15,630 --> 00:01:17,150
başqa, digər.

24
00:01:17,150 --> 00:01:19,100
Amma recursive funksiyaları
sonsuz ola bilməz.

25
00:01:19,100 --> 00:01:23,490
Onlar elə başa, və ya sizin
proqram əbədi davam edəcək.

26
00:01:23,490 --> 00:01:27,680
>> Beləliklə, biz pozmaq üçün bir yol tapmaq lazımdır
recursive zənglər həyata.

27
00:01:27,680 --> 00:01:29,900
Biz baza halda çağırırıq.

28
00:01:29,900 --> 00:01:33,570
Baza halda vəziyyəti görüşüb zaman,
funksiyası etmədən qaytarır

29
00:01:33,570 --> 00:01:34,950
başqa recursive zəng.

30
00:01:34,950 --> 00:01:39,610
Bir boşluq funksiyası, hi, bu funksiyası edin
ki, giriş kimi bir int n edir.

31
00:01:39,610 --> 00:01:41,260
Ėsas birinci gəlir.

32
00:01:41,260 --> 00:01:46,220
N az sıfır, çap bye və əgər
Bütün digər hallarda qayıtmaq

33
00:01:46,220 --> 00:01:49,400
funksiyası hi çap və icra edəcək
recursive zəng.

34
00:01:49,400 --> 00:01:53,600
Ilə funksiyası Şueyb üçün bir zəng
bir endirildiyi giriş dəyər.

35
00:01:53,600 --> 00:01:56,790
>> İndi biz, hi çap baxmayaraq
funksiyası ləğv edəcək biz qədər

36
00:01:56,790 --> 00:02:00,370
onun qaytarılması növü qayıtmaq,
Bu halda etibarsız.

37
00:02:00,370 --> 00:02:04,830
Belə ki, hər n baza halda başqa,
bu funksiya hi hi qayıdacaqlar

38
00:02:04,830 --> 00:02:06,890
n minus 1.

39
00:02:06,890 --> 00:02:10,050
Bu funksiya olsa etibarsız olduğundan, biz
açıq-aydın burada geri yazın deyil.

40
00:02:10,050 --> 00:02:12,000
Biz yalnız funksiyası icra edəcəyik.

41
00:02:12,000 --> 00:02:16,960
Belə ki, hi zəng (3) hi çap və
hi (2) (1) bir hi icra edən icra

42
00:02:16,960 --> 00:02:20,560
hi icra (0), burada
baza halda vəziyyət görüşüb.

43
00:02:20,560 --> 00:02:24,100
Belə ki, hi (0) bye yazdıran və qaytarır.

44
00:02:24,100 --> 00:02:24,990
>> OK.

45
00:02:24,990 --> 00:02:28,690
Belə ki, indi biz əsasları anlamaq ki,
onlar lazımdır ki, recursive funksiyaları,

46
00:02:28,690 --> 00:02:32,730
ən azı bir əsas işi habelə
recursive zəng, bir hərəkət edək

47
00:02:32,730 --> 00:02:34,120
daha mənalı nümunəsidir.

48
00:02:34,120 --> 00:02:37,830
Yalnız geri deyil ki, bir
nə olursa olsun ləğv.

49
00:02:37,830 --> 00:02:41,340
>> Nin faktöryel bir nəzər salaq
əməliyyat ən çox istifadə olunan

50
00:02:41,340 --> 00:02:43,660
ehtimal hesablamaları.

51
00:02:43,660 --> 00:02:48,120
N Faktorial hər məhsuludur
daha müsbət tam ədəddir

52
00:02:48,120 --> 00:02:49,400
və n bərabər.

53
00:02:49,400 --> 00:02:56,731
Belə ki, faktöryel beş 5 dəfə 4 dəfə
3 dəfə 2 dəfə 1 120 vermək.

54
00:02:56,731 --> 00:03:01,400
Dörd faktöryel 4 dəfə 3 dəfə
2 dəfə 1 24 vermək.

55
00:03:01,400 --> 00:03:04,910
Və eyni qayda tətbiq edilir
hər hansı bir müsbət tam.

56
00:03:04,910 --> 00:03:08,670
>> Belə ki, necə biz recursive yazmaq bilər
faktöryel hesablayır ki, funksiyası

57
00:03:08,670 --> 00:03:09,960
Bir sıra?

58
00:03:09,960 --> 00:03:14,700
Yaxşı, biz də müəyyən etmək lazımdır
baza halda və recursive zəng.

59
00:03:14,700 --> 00:03:18,250
Recursive zəng eyni olacaq
baza istisna olmaqla bütün hallarda

60
00:03:18,250 --> 00:03:21,420
halda, biz lazımdır o deməkdir ki,
bizə verəcək bir model tapmaq bizim

61
00:03:21,420 --> 00:03:23,350
istənilən nəticə.

62
00:03:23,350 --> 00:03:30,270
>> Bu, misal üçün, necə 5 faktöryel bax
1-2 3 4 vurulması daxildir

63
00:03:30,270 --> 00:03:33,010
Və ki, çox eyni vurma
, burada aşkar

64
00:03:33,010 --> 00:03:35,430
4 Faktorial definition.

65
00:03:35,430 --> 00:03:39,810
Belə ki, biz 5 faktöryel görürük
yalnız 5 dəfə 4 faktöryel.

66
00:03:39,810 --> 00:03:43,360
İndi bu model tətbiq etmir
4 eləcə də faktöryel?

67
00:03:43,360 --> 00:03:44,280
Bəli.

68
00:03:44,280 --> 00:03:49,120
Biz 4 faktöryel ehtiva görmək
vurma 3 dəfə 2 dəfə 1,

69
00:03:49,120 --> 00:03:51,590
3 Faktorial kimi çox eyni definition.

70
00:03:51,590 --> 00:03:56,950
Belə ki, 4 faktöryel 4 dəfə 3 bərabərdir
faktöryel, və s və s bizim

71
00:03:56,950 --> 00:04:02,170
model 1 Faktorial qədər sərvətdən
Açıklama 1 bərabərdir.

72
00:04:02,170 --> 00:04:04,950
>> Başqa heç bir müsbət var
integers ayrıldı.

73
00:04:04,950 --> 00:04:07,870
Beləliklə, biz üçün model var
bizim recursive zəng.

74
00:04:07,870 --> 00:04:13,260
n faktöryel n dəfə bərabərdir
Bu n faktöryel minus 1.

75
00:04:13,260 --> 00:04:14,370
Və bizim əsas işi?

76
00:04:14,370 --> 00:04:17,370
Ki, yalnız bizim definition olacaq
1 Faktorial.

77
00:04:17,370 --> 00:04:19,995
>> Belə ki, indi biz yazılı üçün hərəkət edə bilər
funksiyası üçün kodu.

78
00:04:19,995 --> 00:04:24,110
Baza halda, biz lazımdır
vəziyyəti n bərabərdir 1, bərabərdir yerləşir

79
00:04:24,110 --> 00:04:25,780
biz 1 qayıtmaq lazımdır.

80
00:04:25,780 --> 00:04:29,280
Sonra recursive zəng üzərində hərəkət,
biz n dəfə qayıtmaq lazımdır

81
00:04:29,280 --> 00:04:32,180
n faktöryel minus 1.

82
00:04:32,180 --> 00:04:33,590
>> İndi bu bizim test imkan verir.

83
00:04:33,590 --> 00:04:35,900
Nin Faktorial 4 cəhd edək.

84
00:04:35,900 --> 00:04:39,420
Bizim funksiyası Per bərabər var
4 dəfə faktöryel (3).

85
00:04:39,420 --> 00:04:43,040
Faktorial (3) bərabərdir
3 dəfə faktöryel (2).

86
00:04:43,040 --> 00:04:48,700
Faktorial (2) 2 dəfə bərabərdir
faktöryel (1), olan 1 qaytarır.

87
00:04:48,700 --> 00:04:52,490
Faktorial (2) indi 2 dəfə 1, 2 qaytarır.

88
00:04:52,490 --> 00:04:55,960
Faktorial (3) indi qayıda bilər
3 dəfə 2, 6.

89
00:04:55,960 --> 00:05:02,490
Və nəhayət, faktöryel (4)
4 dəfə 6, 24 qaytarır.

90
00:05:02,490 --> 00:05:06,780
>> Hər hansı bir çətinlik karşılaşırsanız
recursive zəng ilə, iddia

91
00:05:06,780 --> 00:05:09,660
funksiyası artıq işləyir.

92
00:05:09,660 --> 00:05:13,450
Mən bu demək olmalıdır ki,
qayıtmaq üçün recursive zənglər etibar

93
00:05:13,450 --> 00:05:15,100
sağ dəyərlər.

94
00:05:15,100 --> 00:05:18,960
Məsələn, mən bilirəm ki, əgər
faktöryel (5) 5 dəfə bərabərdir

95
00:05:18,960 --> 00:05:24,870
faktöryel (4), I etibar gedirəm
faktöryel (4) mənə 24 verəcək.

96
00:05:24,870 --> 00:05:28,510
Əgər, bir dəyişən kimi düşünün
olacaq, siz artıq müəyyən kimi

97
00:05:28,510 --> 00:05:30,070
faktöryel (4).

98
00:05:30,070 --> 00:05:33,850
Belə ki, hər hansı bir faktöryel üçün (n), bu
n məhsul və

99
00:05:33,850 --> 00:05:35,360
əvvəlki faktöryel.

100
00:05:35,360 --> 00:05:38,130
Bu əvvəlki faktöryel
zəng etməklə əldə olunur

101
00:05:38,130 --> 00:05:41,330
n faktöryel minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Siz həyata keçirilməsi əgər İndi, bax
recursive özünüzü fəaliyyət göstərir.

103
00:05:45,130 --> 00:05:50,490
Sizin terminal yük, və ya run.cs50.net,
və funksiyası məbləğ yazmaq

104
00:05:50,490 --> 00:05:54,770
ki, bir tam n edir və qaytarır
bütün ardıcıl müsbət məbləği

105
00:05:54,770 --> 00:05:57,490
n-1 integers.

106
00:05:57,490 --> 00:06:01,000
Mən bəzi məbləğləri yazdıq
sizə yardım etmək dəyərlər bizim.

107
00:06:01,000 --> 00:06:04,030
Birincisi, anlamaq
baza halda vəziyyəti.

108
00:06:04,030 --> 00:06:06,170
Sonra məbləğin baxmaq (5).

109
00:06:06,170 --> 00:06:09,270
Siz baxımından bunu ifadə edə bilər
başqa məbləğin?

110
00:06:09,270 --> 00:06:11,290
İndi nə məbləğin haqqında (4)?

111
00:06:11,290 --> 00:06:15,630
Necə məbləğ ifadə edə bilər (4)
başqa məbləğin baxımından?

112
00:06:15,630 --> 00:06:19,655
>> Siz məbləğ var (5) və məbləği (4)
başqa məbləğləri ilə ifadə bax

113
00:06:19,655 --> 00:06:22,970
Bir müəyyən edə bilər
məbləğin (n) üçün model.

114
00:06:22,970 --> 00:06:26,190
Əgər bir neçə digər nömrələr cəhd
və onların məbləğləri ifadə

115
00:06:26,190 --> 00:06:28,410
başqa nömrələri şərtləri.

116
00:06:28,410 --> 00:06:31,930
Diskret üçün nümunələri müəyyən
nömrələri, sizin yol yaxşı deyilik

117
00:06:31,930 --> 00:06:34,320
bir n üçün model müəyyən.

118
00:06:34,320 --> 00:06:38,040
>> Recursion həqiqətən güclü alət var,
belə əlbəttə ki, bu məhdud deyil

119
00:06:38,040 --> 00:06:39,820
riyazi funksiyaları.

120
00:06:39,820 --> 00:06:44,040
Recursion çox səmərəli istifadə edilə bilər
Məsələn ağacları ilə məşğul olan zaman.

121
00:06:44,040 --> 00:06:47,210
Bir ağac haqqında qısa oldu
daha ətraflı baxış, lakin indi

122
00:06:47,210 --> 00:06:51,140
ki, ikili axtarış ağac geri
Xüsusilə, hər qovşaqlarının edilir

123
00:06:51,140 --> 00:06:53,820
bir dəyəri və iki node göstəricilər ilə.

124
00:06:53,820 --> 00:06:57,270
Adətən, bu ilə təmsil olunur
bir line işarə olan valideyn node

125
00:06:57,270 --> 00:07:01,870
sol uşaq node və bir
sağ uşaq node.

126
00:07:01,870 --> 00:07:04,510
Ikili axtarış strukturu
ağac də özü verir

127
00:07:04,510 --> 00:07:05,940
bir recursive axtarış.

128
00:07:05,940 --> 00:07:09,730
Recursive zəng ya keçir
sol və ya sağ node, lakin daha çox

129
00:07:09,730 --> 00:07:10,950
ağac Qisa ildə ki.

130
00:07:10,950 --> 00:07:15,690
>> Siz əməliyyat istəyirəm demək
bir ikili ağac hər bir node.

131
00:07:15,690 --> 00:07:17,410
Necə ki, haqqında getmək bilər?

132
00:07:17,410 --> 00:07:20,600
Yaxşı, bir recursive yazmaq bilər
Əməliyyatı reallaşdıran funksiyası

133
00:07:20,600 --> 00:07:24,450
valideyn node və recursive edir
Eyni funksiyası zəng,

134
00:07:24,450 --> 00:07:27,630
sol keçən və
sağ uşaq qovşaqlarının.

135
00:07:27,630 --> 00:07:31,650
Məsələn, bu funksiya, foo ki,
Bu bir node dəyəri və dəyişikliklər

136
00:07:31,650 --> 00:07:33,830
1 onun uşaqlar bütün.

137
00:07:33,830 --> 00:07:37,400
Bir null node səbəbləri əsas işi
funksiyası ifadə qayıtmaq

138
00:07:37,400 --> 00:07:41,290
bir qovşaqlarının var ki
ki, sub-ağac ayrıldı.

139
00:07:41,290 --> 00:07:42,620
>> Bunun vasitəsilə gəzmək edək.

140
00:07:42,620 --> 00:07:44,340
İlk valideyn 13.

141
00:07:44,340 --> 00:07:47,930
Biz dəyəri 1 dəyişdirmək, və sonra zəng
Bizim sol funksiyası, habelə

142
00:07:47,930 --> 00:07:49,600
hüququ kimi.

143
00:07:49,600 --> 00:07:53,910
Funksiyası, foo, sol adlanır
ilk sub-ağac, belə ki, sol node

144
00:07:53,910 --> 00:07:57,730
1 və foo adına edəcək
ki node uşaqlar adlanır,

145
00:07:57,730 --> 00:08:01,900
ilk sol və sonra sağ,
və s və s.

146
00:08:01,900 --> 00:08:05,630
Və filialları yoxdur ki, onlara
bir daha uşaq belə ki, eyni proses

147
00:08:05,630 --> 00:08:09,700
sağ uşaqlar üçün davam edəcək
bütün ağac qovşaqlarının qədər

148
00:08:09,700 --> 00:08:11,430
1 dəyişdirilmişdir.

149
00:08:11,430 --> 00:08:15,390
>> Gördüyünüz kimi, siz məhdud deyil
yalnız bir recursive zəng.

150
00:08:15,390 --> 00:08:17,930
Iş aparılır almaq kimi bir çox.

151
00:08:17,930 --> 00:08:21,200
Bir ağac nə əgər hər bir
node üç övladı var idi,

152
00:08:21,200 --> 00:08:23,100
Sol, orta, və sağ?

153
00:08:23,100 --> 00:08:24,886
Necə foo redaktə olardı?

154
00:08:24,886 --> 00:08:25,860
Yaxşı, sadə.

155
00:08:25,860 --> 00:08:30,250
Yalnız başqa recursive zəng əlavə və
orta node göstərici keçir.

156
00:08:30,250 --> 00:08:34,549
>> Recursion çox güclü və edir
zərif qeyd, ancaq bir ola bilər

157
00:08:34,549 --> 00:08:38,010
ilk çətin anlayış, belə olacaq
xəstə və vaxt.

158
00:08:38,010 --> 00:08:39,370
Baza işi ilə başlayın.

159
00:08:39,370 --> 00:08:42,650
Bu adətən müəyyən etmək asan deyil,
və sonra işləyə bilər

160
00:08:42,650 --> 00:08:43,830
geri oradan.

161
00:08:43,830 --> 00:08:46,190
Siz olmaq lazımdır bilirik sizin
baza halda, belə ki, hünəri

162
00:08:46,190 --> 00:08:47,760
bir neçə göstərişlər verir.

163
00:08:47,760 --> 00:08:53,120
Müəyyən bir işi ifadə etmək üçün cəhd edin
digər hallarda şərtləri, və ya sub-dəstləri.

164
00:08:53,120 --> 00:08:54,700
>> Bu qısa izləmək üçün təşəkkür edirik.

165
00:08:54,700 --> 00:08:58,920
Ən azı, indi bilərsiniz
bu kimi zarafatlar anlamaq.

166
00:08:58,920 --> 00:09:01,250
My name Zamyla və bu CS50 edir.

167
00:09:01,250 --> 00:09:04,306

168
00:09:04,306 --> 00:09:07,170
>> Hi, bu funksiyası edin, bir
edir ki, boşluq funksiyası

169
00:09:07,170 --> 00:09:09,212
bir int, n, giriş kimi.

170
00:09:09,212 --> 00:09:11,020
Ėsas birinci gəlir.

171
00:09:11,020 --> 00:09:14,240
N az 0, çap əgər
"Bye" və qaytarılması.

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