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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Për të kuptuar
recursion, ju duhet

3
00:00:10,190 --> 00:00:13,820
së pari të kuptojnë recursion.

4
00:00:13,820 --> 00:00:17,280
Duke recursion në mjetet e programit të projektimit
që ju keni vetë-referencial

5
00:00:17,280 --> 00:00:18,570
përkufizime.

6
00:00:18,570 --> 00:00:21,520
Strukturat e të dhënave gjithkund rekursive, për shembull,
janë strukturat e të dhënave që

7
00:00:21,520 --> 00:00:23,990
përfshijnë veten në
përkufizimet e tyre.

8
00:00:23,990 --> 00:00:27,160
Por sot, ne do të përqëndrohet
mbi funksionet gjithkund rekursive.

9
00:00:27,160 --> 00:00:31,160
>> Kujtojnë se funksionet marrë inpute,
argumente, dhe të kthehet një vlerë e tyre si

10
00:00:31,160 --> 00:00:34,480
Prodhimi përfaqësuar nga
ky diagram këtu.

11
00:00:34,480 --> 00:00:38,060
Ne do të mendojnë kutisë si organ i
funksioni, që përmban tërësinë e

12
00:00:38,060 --> 00:00:42,340
udhëzimet që interpretojnë
input dhe të sigurojë një prodhim.

13
00:00:42,340 --> 00:00:45,660
Duke marrë një vështrim më të afërt brenda trupit të
funksion mund të zbulojë thirrjet për

14
00:00:45,660 --> 00:00:47,430
funksione të tjera si.

15
00:00:47,430 --> 00:00:51,300
Merrni këtë funksion të thjeshtë, foo, që
merr një varg të vetëm si input dhe

16
00:00:51,300 --> 00:00:54,630
printime sa letra
që ka string.

17
00:00:54,630 --> 00:00:58,490
Strlen funksion, për gjatësi string,
quhet, prodhimi i të cilit është

18
00:00:58,490 --> 00:01:01,890
e nevojshme për thirrjen në printf.

19
00:01:01,890 --> 00:01:05,770
>> Tani, ajo që e bën një funksion gjithkund rekursive
veçantë është se ai e quan veten.

20
00:01:05,770 --> 00:01:09,610
Ne mund të përfaqësojnë këtë recursive
telefononi me këtë ngjyrë e shigjeta

21
00:01:09,610 --> 00:01:11,360
looping përsëri në vetvete.

22
00:01:11,360 --> 00:01:15,630
Por ekzekutimin veten përsëri vetëm do
të bëjë një tjetër thirrje rekursive, dhe

23
00:01:15,630 --> 00:01:17,150
një tjetër dhe një tjetër.

24
00:01:17,150 --> 00:01:19,100
Por funksionet gjithkund rekursive
nuk mund të jetë i pafund.

25
00:01:19,100 --> 00:01:23,490
Ata kanë për t'i dhënë fund disi, ose juaj
Programi do të kandidojë përgjithmonë.

26
00:01:23,490 --> 00:01:27,680
>> Pra, ne duhet të gjejnë një mënyrë për të thyer
nga thirrjet gjithkund rekursive.

27
00:01:27,680 --> 00:01:29,900
Ne e quajmë këtë rast bazë.

28
00:01:29,900 --> 00:01:33,570
Kur gjendja rastit bazë është plotësuar,
funksion të kthimit pa bërë

29
00:01:33,570 --> 00:01:34,950
një tjetër thirrje rekursive.

30
00:01:34,950 --> 00:01:39,610
Merrni këtë funksion, hi, një funksion i pavlefshëm
që merr një int n si input.

31
00:01:39,610 --> 00:01:41,260
Rastit bazë vjen e para.

32
00:01:41,260 --> 00:01:46,220
Nëse n është më pak se zero, bye shtypura dhe
kthehen Për të gjitha rastet e tjera,

33
00:01:46,220 --> 00:01:49,400
funksion do të shtypura hi dhe ekzekutuar
thirrje rekursive.

34
00:01:49,400 --> 00:01:53,600
Një tjetër thirrje të funksionit hi me
një vlerë decremented input.

35
00:01:53,600 --> 00:01:56,790
>> Tani, edhe pse kemi shkruar hi,
funksion nuk do të përfundojë deri ne

36
00:01:56,790 --> 00:02:00,370
kthehen llojin e vet të kthimit,
në këtë rast pavlefshme.

37
00:02:00,370 --> 00:02:04,830
Kështu që për çdo n përveç rastit bazë,
ky funksion hi do të kthehet hi

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

39
00:02:06,890 --> 00:02:10,050
Që nga ky funksion është i pavlefshëm edhe pse, ne
nuk do të shkruani në mënyrë të qartë kthimin këtu.

40
00:02:10,050 --> 00:02:12,000
Ne do të ekzekutojë vetëm funksionin.

41
00:02:12,000 --> 00:02:16,960
Pra, duke e quajtur hi (3) do të shtypura hi dhe
ekzekutojë hi (2) e cila kryen hi (1) nje

42
00:02:16,960 --> 00:02:20,560
cila kryen hi (0), ku
kusht rastit bazë është plotësuar.

43
00:02:20,560 --> 00:02:24,100
Pra hi (0) printon bye dhe të kthimit.

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

45
00:02:24,990 --> 00:02:28,690
Pra, tani që ne e kuptojmë bazat e
funksionet gjithkund rekursive, që ata kanë nevojë

46
00:02:28,690 --> 00:02:32,730
të paktën një rast të bazë si dhe një
thirrje rekursive, le të lëvizin për në një

47
00:02:32,730 --> 00:02:34,120
Shembulli më kuptimplotë.

48
00:02:34,120 --> 00:02:37,830
Një që nuk ka vetëm të kthehet
pavlefshme pa marrë parasysh çfarë.

49
00:02:37,830 --> 00:02:41,340
>> Le të bëjmë një vështrim në faktoriale
Operacioni më të përdorura në

50
00:02:41,340 --> 00:02:43,660
Llogaritjet e probabilitetit.

51
00:02:43,660 --> 00:02:48,120
Faktoriali e n eshte produkti i çdo
integer pozitiv pak se

52
00:02:48,120 --> 00:02:49,400
dhe barabartë me n.

53
00:02:49,400 --> 00:02:56,731
Pesë Pra faktoriale është 5 herë 4 herë
3 herë 2 herë 1 për të dhënë 120.

54
00:02:56,731 --> 00:03:01,400
Katër faktoriale është 4 herë 3 herë
2 herë 1 për të dhënë 24.

55
00:03:01,400 --> 00:03:04,910
Dhe e njëjta rregull vlen
në çdo numër i plotë pozitiv.

56
00:03:04,910 --> 00:03:08,670
>> Pra, si mund të kemi shkruar një recursive
funksion që llogarit faktoriale

57
00:03:08,670 --> 00:03:09,960
e një numri?

58
00:03:09,960 --> 00:03:14,700
E pra, ne do të duhet për të identifikuar të dy
rastit bazë dhe thirrja rekursive.

59
00:03:14,700 --> 00:03:18,250
Thirrja recursive do të jetë e njëjtë
për të gjitha rastet me përjashtim të bazës

60
00:03:18,250 --> 00:03:21,420
rasti, që do të thotë se ne do të duhet të
të gjetur një model që do të na japë tonë

61
00:03:21,420 --> 00:03:23,350
rezultati i dëshiruar.

62
00:03:23,350 --> 00:03:30,270
>> Për këtë shembull, të shohim se si 5 faktoriale
përfshin shumëzuar me 4 nga 3 me 2 me 1

63
00:03:30,270 --> 00:03:33,010
Dhe kjo shumë e njëjtë shumëzimit
është gjetur këtu,

64
00:03:33,010 --> 00:03:35,430
Përkufizimi i 4 faktoriale.

65
00:03:35,430 --> 00:03:39,810
Pra, ne shohim se 5 faktoriale është
vetëm 5 herë 4 faktorial.

66
00:03:39,810 --> 00:03:43,360
Tani ka të bëjë ky model
4 Faktoriali si?

67
00:03:43,360 --> 00:03:44,280
Po.

68
00:03:44,280 --> 00:03:49,120
Ne shohim se 4 faktoriale përmban
shumëzimit 3 herë 2 herë 1,

69
00:03:49,120 --> 00:03:51,590
shumë e njëjtë si përkufizim 3 faktoriale.

70
00:03:51,590 --> 00:03:56,950
SO 4 faktoriale është e barabartë me 4 herë 3
faktorial, dhe kështu me radhë e kështu me radhë tonë

71
00:03:56,950 --> 00:04:02,170
model i qëndron deri më 1 faktoriale, e cila
sipas definicionit është e barabartë me 1.

72
00:04:02,170 --> 00:04:04,950
>> Nuk ka asnjë pozitiv të tjera
integers majtë.

73
00:04:04,950 --> 00:04:07,870
Pra, ne kemi model për
Thirrja jonë recursive.

74
00:04:07,870 --> 00:04:13,260
n është e barabartë tek faktorial herë n
faktorial i n minus 1.

75
00:04:13,260 --> 00:04:14,370
Dhe rasti ynë bazë?

76
00:04:14,370 --> 00:04:17,370
Kjo do të jetë vetëm përkufizimi ynë
e 1 faktorial.

77
00:04:17,370 --> 00:04:19,995
>> Deri tani ne mund të lëvizin për shkrim
formuar për funksionin.

78
00:04:19,995 --> 00:04:24,110
Për rastin bazë, ne do të kemi
Gjendja n është e barabartë është e barabartë me 1, ku

79
00:04:24,110 --> 00:04:25,780
ne do të kthehemi me 1.

80
00:04:25,780 --> 00:04:29,280
Pastaj lëviz mbi thirrjes rekursive,
ne do të kthehemi herë n

81
00:04:29,280 --> 00:04:32,180
faktorial i n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Tani le të testuar këtë tona.

83
00:04:33,590 --> 00:04:35,900
Le të përpiqemi faktoriale 4.

84
00:04:35,900 --> 00:04:39,420
Per funksionin tonë është e barabartë
në 4 herë faktorial (3).

85
00:04:39,420 --> 00:04:43,040
Faktoriali (3) është e barabartë me
3 herë faktoriale (2).

86
00:04:43,040 --> 00:04:48,700
Faktoriali (2) është i barabartë me 2 herë
faktorial (1), e cila jep 1.

87
00:04:48,700 --> 00:04:52,490
Faktoriali (2) tani kthen 2 herë 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktorial (3) tani mund të kthehen
3 herë 2, 6.

89
00:04:55,960 --> 00:05:02,490
Dhe së fundi, faktoriale (4)
kthen 4 herë 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Nëse ju jeni ndeshi në ndonjë vështirësi
me thirrjen gjithkund rekursive, pretendon se

91
00:05:06,780 --> 00:05:09,660
funksion punon tashmë.

92
00:05:09,660 --> 00:05:13,450
Çfarë dua të them me këtë është se ju duhet
besim thirrjet tuaja gjithkund rekursive për t'u kthyer

93
00:05:13,450 --> 00:05:15,100
vlerat e duhura.

94
00:05:15,100 --> 00:05:18,960
Për shembull, në qoftë se unë e di se
faktorial (5) është e barabartë me 5 herë

95
00:05:18,960 --> 00:05:24,870
faktorial (4), Unë do të besoj se
faktorial (4) do të më jepni 24.

96
00:05:24,870 --> 00:05:28,510
Mendoni se si një variabël, në qoftë se ju
do, si në qoftë se ju tashmë e definuar

97
00:05:28,510 --> 00:05:30,070
faktorial (4).

98
00:05:30,070 --> 00:05:33,850
Pra, për çdo faktoriale (n), është e
Produkti i N dhe

99
00:05:33,850 --> 00:05:35,360
faktorial mëparshme.

100
00:05:35,360 --> 00:05:38,130
Dhe kjo faktoriale e mëparshme
është marrë duke e quajtur

101
00:05:38,130 --> 00:05:41,330
faktorial i n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Tani, të shohim nëse mund të zbatojë një
recursive funksionojnë veten.

103
00:05:45,130 --> 00:05:50,490
Load up terminali tuaj, ose run.cs50.net,
dhe shkruani një shumë funksion

104
00:05:50,490 --> 00:05:54,770
që merr një numër të plotë n dhe kthimit
Shuma e të gjitha radhazi pozitive

105
00:05:54,770 --> 00:05:57,490
numra te plote nga N me 1.

106
00:05:57,490 --> 00:06:01,000
Unë e kam shkruar nga shumat e disa
Vlerat për t'ju ndihmuar tonë.

107
00:06:01,000 --> 00:06:04,030
Së pari, gjej
kusht rastit bazë.

108
00:06:04,030 --> 00:06:06,170
Pastaj, shikoni në shumën (5).

109
00:06:06,170 --> 00:06:09,270
A mund të shprehin atë në terma
e një tjetër shumës?

110
00:06:09,270 --> 00:06:11,290
Tani, ajo që për shumë (4)?

111
00:06:11,290 --> 00:06:15,630
Si mund të shprehë shumë (4)
në drejtim të një tjetër shumës?

112
00:06:15,630 --> 00:06:19,655
>> Pasi të keni shumë (5) dhe shuma (4)
shprehur në terma të shumave të tjera, shih

113
00:06:19,655 --> 00:06:22,970
në qoftë se ju mund të identifikojë një
model për shumën (n).

114
00:06:22,970 --> 00:06:26,190
Nëse jo, provoni një numër pak të tjera
dhe shprehin shuma e tyre në

115
00:06:26,190 --> 00:06:28,410
kushtet e një tjetër numrave.

116
00:06:28,410 --> 00:06:31,930
Duke identifikuar modele për diskrete
numrat, ju jeni edhe në rrugën tuaj për

117
00:06:31,930 --> 00:06:34,320
identifikuar model për çdo n.

118
00:06:34,320 --> 00:06:38,040
>> Recursion është një mjet me të vërtetë i fuqishëm,
kështu që sigurisht nuk është i kufizuar në

119
00:06:38,040 --> 00:06:39,820
Funksionet matematikore.

120
00:06:39,820 --> 00:06:44,040
Recursion mund të përdoret shumë në mënyrë efektive
kur kanë të bëjnë me pemë për shembull.

121
00:06:44,040 --> 00:06:47,210
Kontrollo të shkurtër në pemë për një
më shumë rishikim i plotë, por tani për tani

122
00:06:47,210 --> 00:06:51,140
kujtojnë se pemët e kërkimit binare, në
veçanti, janë të përbërë nga nyjet, çdo

123
00:06:51,140 --> 00:06:53,820
me vlerë dhe dy nyjeve pointers.

124
00:06:53,820 --> 00:06:57,270
Zakonisht, kjo është përfaqësuar nga
nyja prind që ka një duke treguar linjë

125
00:06:57,270 --> 00:07:01,870
në nyjen e majtë të fëmijëve dhe një
në nyjen e duhur të fëmijëve.

126
00:07:01,870 --> 00:07:04,510
Struktura e një kërkimi binar
pemë jep edhe vetë

127
00:07:04,510 --> 00:07:05,940
në një kërkim gjithkund rekursive.

128
00:07:05,940 --> 00:07:09,730
Thirrja recursive ose kalon në
majtas ose nyjen e drejtë, por më shumë

129
00:07:09,730 --> 00:07:10,950
e që në pemë të shkurtër.

130
00:07:10,950 --> 00:07:15,690
>> Thonë se ju doni të kryer një operacion në
çdo nyje të vetëm në një pemë binare.

131
00:07:15,690 --> 00:07:17,410
Si mund të ju shkoni në lidhje me këtë?

132
00:07:17,410 --> 00:07:20,600
E pra, ju mund të shkruani një recursive
funksion që kryen operacionin

133
00:07:20,600 --> 00:07:24,450
në nyjen prind dhe e bën një recursive
thirrje për të njëjtin funksion,

134
00:07:24,450 --> 00:07:27,630
duke kaluar në të majtë dhe
nyjet e drejtë të fëmijëve.

135
00:07:27,630 --> 00:07:31,650
Për shembull, ky funksion, foo, që
ndryshon vlerën e një nyje të caktuar dhe

136
00:07:31,650 --> 00:07:33,830
gjithë fëmijëve me 1.

137
00:07:33,830 --> 00:07:37,400
Rasti Baza e një shkaqeve null nyjeve
funksion të kthehen, duke treguar

138
00:07:37,400 --> 00:07:41,290
se nuk ka ndonjë nyje
mbetur në këtë nën-pemë.

139
00:07:41,290 --> 00:07:42,620
>> Le të ecin nëpër atë.

140
00:07:42,620 --> 00:07:44,340
Prind i parë është 13.

141
00:07:44,340 --> 00:07:47,930
Ne ndryshoni vlerën në 1, dhe pastaj të telefononi
funksion ynë në të majtë, si dhe

142
00:07:47,930 --> 00:07:49,600
si e drejta.

143
00:07:49,600 --> 00:07:53,910
Funksioni, foo, quhet në të majtë
nën-pemë e parë, kështu që nyja e majtë

144
00:07:53,910 --> 00:07:57,730
do të caktohen për të 1 dhe foo do
të thirret mbi fëmijët se Nyja-së,

145
00:07:57,730 --> 00:08:01,900
pari majtë dhe pastaj të drejtë,
dhe kështu me radhë e kështu me radhë.

146
00:08:01,900 --> 00:08:05,630
Dhe tregoni atyre se degët nuk kanë
më fëmijë aq i njëjti proces

147
00:08:05,630 --> 00:08:09,700
do të vazhdojë për fëmijët drejtë
deri në nyje gjithë pemën janë

148
00:08:09,700 --> 00:08:11,430
ricaktuar në 1.

149
00:08:11,430 --> 00:08:15,390
>> Siç mund ta shikoni, ju nuk janë të kufizuara
të vetëm një telefonatë recursive.

150
00:08:15,390 --> 00:08:17,930
Ashtu të gjithë ata që do të marrë punë të bërë.

151
00:08:17,930 --> 00:08:21,200
Çfarë ndodh nëse keni pasur një pemë ku çdo
nyje kishte tre fëmijë,

152
00:08:21,200 --> 00:08:23,100
Majtas, të mesëm, dhe të drejtë?

153
00:08:23,100 --> 00:08:24,886
Si do ta redaktoni foo?

154
00:08:24,886 --> 00:08:25,860
E pra, e thjeshtë.

155
00:08:25,860 --> 00:08:30,250
Vetëm të shtoni një tjetër thirrje rekursive dhe
të kalojë në treguesin nyjen e mesme.

156
00:08:30,250 --> 00:08:34,549
>> Recursion është shumë i fuqishëm dhe jo të
përmend elegante, por ajo mund të jetë një

157
00:08:34,549 --> 00:08:38,010
koncept i vështirë në fillim, në mënyrë të
pacientit dhe të marrë kohën tuaj.

158
00:08:38,010 --> 00:08:39,370
Filloni me rastin bazë.

159
00:08:39,370 --> 00:08:42,650
Kjo është zakonisht më e lehtë për të identifikuar,
dhe pastaj ju mund të punojnë

160
00:08:42,650 --> 00:08:43,830
prapa nga atje.

161
00:08:43,830 --> 00:08:46,190
Ju e dini që ju duhet për të arritur tuaj
rastit bazë, në mënyrë që fuqia

162
00:08:46,190 --> 00:08:47,760
ju jap disa lë të kuptohet.

163
00:08:47,760 --> 00:08:53,120
Mundohuni për të shprehur një rast të veçantë në
Kushtet e raste të tjera, ose në nën-grupe.

164
00:08:53,120 --> 00:08:54,700
>> Faleminderit për të shikuar këtë short.

165
00:08:54,700 --> 00:08:58,920
Në shumë pak, tani ju mund të
kuptojnë shaka si kjo.

166
00:08:58,920 --> 00:09:01,250
Emri im është Zamyla, dhe kjo është CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Merrni këtë funksion, hi, një
Funksioni i pavlefshëm që merr

169
00:09:07,170 --> 00:09:09,212
një int, n, si hyrje.

170
00:09:09,212 --> 00:09:11,020
Rastit bazë vjen e para.

171
00:09:11,020 --> 00:09:14,240
Nëse n është më pak se 0, print
"Bye" dhe kthim.

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