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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Siekiant suprasti
rekursija, turite

3
00:00:10,190 --> 00:00:13,820
pirmiausia suprasti rekursija.

4
00:00:13,820 --> 00:00:17,280
Atsižvelgdama rekursija programų kūrimo priemones
kad jūs turite nuorodų į save

5
00:00:17,280 --> 00:00:18,570
apibrėžimai.

6
00:00:18,570 --> 00:00:21,520
Rekursinės duomenų struktūras, pavyzdžiui,
yra duomenų struktūros,

7
00:00:21,520 --> 00:00:23,990
įtraukti save
jų apibrėžimai.

8
00:00:23,990 --> 00:00:27,160
Tačiau šiandien mes ketiname sutelkti
ant rekursyvinių funkcijas.

9
00:00:27,160 --> 00:00:31,160
>> Prisiminkite, kad funkcijos imtis įėjimai,
argumentus ir grąžina reikšmę, nes jų

10
00:00:31,160 --> 00:00:34,480
išėjimo atstovaujamos
tai schema čia.

11
00:00:34,480 --> 00:00:38,060
Mes manote dėžutės kaip kūno
funkcija, kuriame yra nustatyti

12
00:00:38,060 --> 00:00:42,340
nurodymai, interpretuoti
įvesties ir pateikti rezultatus.

13
00:00:42,340 --> 00:00:45,660
Atidžiau pažvelgti viduje kūno
funkcija gali atskleisti skambučius

14
00:00:45,660 --> 00:00:47,430
kitas funkcijas, taip pat.

15
00:00:47,430 --> 00:00:51,300
Paimkite šį paprastą funkciją foo, kad
užima vieną eilutę kaip įvesties ir

16
00:00:51,300 --> 00:00:54,630
spausdina kiek raidžių
kad eilutė yra.

17
00:00:54,630 --> 00:00:58,490
Funkcija strlen, styginių ilgio,
vadinamas, kurio išėjimas yra

18
00:00:58,490 --> 00:01:01,890
reikalingas su printf skambutį.

19
00:01:01,890 --> 00:01:05,770
>> Dabar, ką daro rekursinį funkciją
ypatinga tuo, kad ji save vadina.

20
00:01:05,770 --> 00:01:09,610
Mes galime atstovauti šiam rekursyvūs
skambinti šiuo oranžinė rodyklė

21
00:01:09,610 --> 00:01:11,360
apsisukimo atgal į save.

22
00:01:11,360 --> 00:01:15,630
Bet vykdyti pati vėl bus tik
atlikti kitą rekursinį skambutį, ir

23
00:01:15,630 --> 00:01:17,150
kitą, ir kitą.

24
00:01:17,150 --> 00:01:19,100
Bet rekursyvūs funkcijos
negali būti begalinis.

25
00:01:19,100 --> 00:01:23,490
Jie turi baigtis kažkaip, arba savo
programa bus amžinai.

26
00:01:23,490 --> 00:01:27,680
>> Taigi mums reikia rasti būdą, kaip sulaužyti
iš grįžtamojo skambučius.

27
00:01:27,680 --> 00:01:29,900
Mes tai vadiname bazinį scenarijų.

28
00:01:29,900 --> 00:01:33,570
Kai bazinį scenarijų sąlyga yra įvykdyta,
Funkcija grąžina nedarant

29
00:01:33,570 --> 00:01:34,950
kitas grįžtamojo skambutis.

30
00:01:34,950 --> 00:01:39,610
Pasinaudokite šia funkcija, hi, tuštumą Function
kad mano int n, kaip įvestį.

31
00:01:39,610 --> 00:01:41,260
Bazinį scenarijų ateina pirmiausia.

32
00:01:41,260 --> 00:01:46,220
Jei n yra mažesnis už nulį, spausdinti bye ir
grįžti Visais kitais atvejais,

33
00:01:46,220 --> 00:01:49,400
funkcija spausdinti aukštųjų ir vykdyti
rekursinis skambutis.

34
00:01:49,400 --> 00:01:53,600
Kitas skambutis funkcija hi su
decremented įvesties vertė.

35
00:01:53,600 --> 00:01:56,790
>> Dabar, nors mes spausdinti Sveiki,
funkcija nebus nutraukti, kol mes

36
00:01:56,790 --> 00:02:00,370
grįžti savo grįžimo tipo,
šiuo atveju negalioja.

37
00:02:00,370 --> 00:02:04,830
Taigi, kas n Asmenys, kiti nei bazinė atveju
ši funkcija hi grįš hi

38
00:02:04,830 --> 00:02:06,890
n atėmus 1.

39
00:02:06,890 --> 00:02:10,050
Kadangi ši funkcija yra niekinis, nors mes
nebus aiškiai įrašykite grįžti čia.

40
00:02:10,050 --> 00:02:12,000
Mes tik atlikti funkciją.

41
00:02:12,000 --> 00:02:16,960
Taigi skambina hi (3) bus atspausdinti aukštųjų ir
vykdyti hi (2), kuris vykdo hi (1) vienas

42
00:02:16,960 --> 00:02:20,560
kuris vykdo Hi (0), kur
bazinį scenarijų sąlyga yra įvykdyta.

43
00:02:20,560 --> 00:02:24,100
Taigi, labas (0) spausdina bye ir grįžta.

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

45
00:02:24,990 --> 00:02:28,690
Taigi dabar, kad mes suprantame pagrindai
rekursyvūs funkcijas, kad jie turi

46
00:02:28,690 --> 00:02:32,730
bent vieną bazinį scenarijų, taip pat
grįžtamojo ryšio, pereikime prie

47
00:02:32,730 --> 00:02:34,120
prasmingesnis pavyzdys.

48
00:02:34,120 --> 00:02:37,830
Vienas, kad ne tik grįžti
negalioja, nesvarbu koks.

49
00:02:37,830 --> 00:02:41,340
>> Leiskite pažvelgti į faktorialas atrodo
operacija naudojama dažniausiai

50
00:02:41,340 --> 00:02:43,660
tikimybiniai skaičiavimai.

51
00:02:43,660 --> 00:02:48,120
Faktorinė n yra kiekvienas produktas
teigiamas sveikasis skaičius mažesnis negu

52
00:02:48,120 --> 00:02:49,400
ir lygus n.

53
00:02:49,400 --> 00:02:56,731
Taigi faktorinė penki yra 5 kartus 4 kartus
3 kartus 2 kartus 1 duoti 120.

54
00:02:56,731 --> 00:03:01,400
Keturi faktorialas yra 4 kartus 3 kartus
2 kartus 1 duoti 24.

55
00:03:01,400 --> 00:03:04,910
Ir taikoma ta pati taisyklė
bet teigiamas sveikasis skaičius.

56
00:03:04,910 --> 00:03:08,670
>> Taigi, kaip gali mes rašome rekursinį
funkcija, kuri apskaičiuoja faktorialas

57
00:03:08,670 --> 00:03:09,960
iš skaičių?

58
00:03:09,960 --> 00:03:14,700
Na, mes turime nustatyti tiek
bazinį scenarijų ir grįžtamojo skambutis.

59
00:03:14,700 --> 00:03:18,250
Rekursinis skambutis bus tas pats
visais atvejais, išskyrus pagrindo

60
00:03:18,250 --> 00:03:21,420
atvejis, kuris reiškia, kad mes turime
rasti modelį, kuris suteiks mums mūsų

61
00:03:21,420 --> 00:03:23,350
norimas rezultatas.

62
00:03:23,350 --> 00:03:30,270
>> Šiame pavyzdyje matyti, kaip 5 faktorialas
apima dauginant 4 3 2 iki 1

63
00:03:30,270 --> 00:03:33,010
Ir kad tą pačią daugyba
randamas čia

64
00:03:33,010 --> 00:03:35,430
apibrėžimas 4 faktorialas.

65
00:03:35,430 --> 00:03:39,810
Taigi matome, kad 5 faktorialas yra
vos 5 kartus 4 faktorialas.

66
00:03:39,810 --> 00:03:43,360
Dabar ji šis modelis taikomas
iki 4 Faktorinė taip pat?

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

68
00:03:44,280 --> 00:03:49,120
Mes matome, kad 4 faktorialas yra
dauginimo 3 kartus 2 kartus 1,

69
00:03:49,120 --> 00:03:51,590
Pačią apibrėžimas 3 faktorialas.

70
00:03:51,590 --> 00:03:56,950
Taigi 4 faktorialas yra lygus 4 kartus 3
faktorialas, ir tt ir tt mūsų

71
00:03:56,950 --> 00:04:02,170
modelis lazdos iki 1 faktorialas, kuris
pagal apibrėžimą yra lygi 1.

72
00:04:02,170 --> 00:04:04,950
>> Nėra kitų teigiamų
sveikieji skaičiai liko.

73
00:04:04,950 --> 00:04:07,870
Taigi, mes turime už raštą
mūsų rekursinis skambutis.

74
00:04:07,870 --> 00:04:13,260
n faktorialas yra lygus n kartų
n faktorialas minus 1.

75
00:04:13,260 --> 00:04:14,370
Ir mūsų bazinį scenarijų?

76
00:04:14,370 --> 00:04:17,370
Tai bus tiesiog mūsų apibrėžimas
1 faktorialas.

77
00:04:17,370 --> 00:04:19,995
>> Taigi dabar mes galime judėti į raštu
kodas funkcija.

78
00:04:19,995 --> 00:04:24,110
Dėl pagrindo atveju, mes turime
sąlyga n lygu lygu 1, jei

79
00:04:24,110 --> 00:04:25,780
mes grąžinsime 1.

80
00:04:25,780 --> 00:04:29,280
Tada keliasi į grįžtamojo ryšio metu,
mes grąžinsime n kartų

81
00:04:29,280 --> 00:04:32,180
faktorialas n atėmus 1.

82
00:04:32,180 --> 00:04:33,590
>> Dabar galime išbandyti šią mūsų.

83
00:04:33,590 --> 00:04:35,900
Pabandykime faktorialas 4.

84
00:04:35,900 --> 00:04:39,420
Už mūsų funkcija tai lygūs
iki 4 kartų faktorialas (3).

85
00:04:39,420 --> 00:04:43,040
Faktorinė (3) yra lygi
3 kartus faktorialas (2).

86
00:04:43,040 --> 00:04:48,700
Faktorinė (2) yra lygus 2 kartus
faktorialas (1), kuri grąžina 1.

87
00:04:48,700 --> 00:04:52,490
Faktorinė (2) dabar grąžina 2 kartus 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktorinė (3) dabar gali grįžti
3 kartus 2, 6.

89
00:04:55,960 --> 00:05:02,490
Ir, pagaliau, faktorialas (4)
grąžina 4 kartus 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Jei iškyla kokių nors sunkumų
su grįžtamojo ryšio metu, apsimesti, kad

91
00:05:06,780 --> 00:05:09,660
funkcija veikia jau.

92
00:05:09,660 --> 00:05:13,450
Ką reiškia tai, kad jums reikia
pasitikėti savo rekursinių skambučius grąžinti

93
00:05:13,450 --> 00:05:15,100
teisingas vertybes.

94
00:05:15,100 --> 00:05:18,960
Pavyzdžiui, jei aš žinau, kad
faktorialas (5) lygu 5 kartus

95
00:05:18,960 --> 00:05:24,870
faktorialas (4), aš tikėti, kad
faktorialas (4) duos man 24.

96
00:05:24,870 --> 00:05:28,510
Pagalvokite apie tai, kaip kintamasis, jei
bus, nes jei jau apibrėžta

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

98
00:05:30,070 --> 00:05:33,850
Taigi bet faktorialas (n), tai
n produktas ir

99
00:05:33,850 --> 00:05:35,360
ankstesnis faktorialas.

100
00:05:35,360 --> 00:05:38,130
Ir tai praėjusią faktorialas
gaunamas telefonu

101
00:05:38,130 --> 00:05:41,330
faktorialas n atėmus 1.

102
00:05:41,330 --> 00:05:45,130
>> Dabar, pamatyti, jei jūs galite įgyvendinti
rekursywny veikti patys.

103
00:05:45,130 --> 00:05:50,490
Įdėkite savo terminalą, arba run.cs50.net,
ir parašyti funkciją SUM

104
00:05:50,490 --> 00:05:54,770
kad užima sveikasis skaičius n ir grąžina
suma visų iš eilės teigiamas

105
00:05:54,770 --> 00:05:57,490
sveikieji skaičiai nuo n iki 1.

106
00:05:57,490 --> 00:06:01,000
Aš parašiau dėmesį į kai sumas
vertes, kad padėtų jums mūsų.

107
00:06:01,000 --> 00:06:04,030
Pirma, išsiaiškinti,
bazinį scenarijų sąlyga.

108
00:06:04,030 --> 00:06:06,170
Tada pažvelgti sumos (5).

109
00:06:06,170 --> 00:06:09,270
Galite išreikšti tai pagal
kitos sumos?

110
00:06:09,270 --> 00:06:11,290
Dabar, ką apie sumą (4)?

111
00:06:11,290 --> 00:06:15,630
Kaip jūs galite išreikšti sumą (4)
kalbant apie kitą sumą?

112
00:06:15,630 --> 00:06:19,655
>> Kai jūs turite sumą (5), ir suma (4)
išreikšta kitomis sumomis, žr

113
00:06:19,655 --> 00:06:22,970
jei jūs galite nustatyti
raštas sumos (n).

114
00:06:22,970 --> 00:06:26,190
Jei ne, pabandykite keletą kitų numerius
ir išreikšti savo pinigų sumas

115
00:06:26,190 --> 00:06:28,410
terminai dar numerius.

116
00:06:28,410 --> 00:06:31,930
Nustatant modelius savarankiška
numeriai, jums gerai jūsų būdas

117
00:06:31,930 --> 00:06:34,320
nustatyti už bet n modelis.

118
00:06:34,320 --> 00:06:38,040
>> Rekursija yra tikrai galingas įrankis,
todėl, žinoma, tai ne tik

119
00:06:38,040 --> 00:06:39,820
matematinės funkcijos.

120
00:06:39,820 --> 00:06:44,040
Rekursija gali būti naudojama labai efektyviai
kai sprendžiami su medžių, pavyzdžiui,.

121
00:06:44,040 --> 00:06:47,210
Patikrinkite medelių trumpas
daugiau kruopščiai peržiūrėti, bet dabar

122
00:06:47,210 --> 00:06:51,140
priminti, kad dvejetainius paieškos medžius, į
pirma, yra sudaryta iš mazgų, kiekvienas

123
00:06:51,140 --> 00:06:53,820
su vertės ir dviejų mazgų rodyklės.

124
00:06:53,820 --> 00:06:57,270
Paprastai tai yra atstovaujama
tėvų mazgas turintis vieną eilutę nukreipta

125
00:06:57,270 --> 00:07:01,870
į kairę vaikų mazgas ir vienas
į tinkamą vaikų mazgas.

126
00:07:01,870 --> 00:07:04,510
Iš dvejetainis paieškos struktūra
medis skolina pati gerai

127
00:07:04,510 --> 00:07:05,940
į grįžtamojo paiešką.

128
00:07:05,940 --> 00:07:09,730
Rekursinis skambutis arba eina
kairę arba į dešinę mazgas, bet daugiau

129
00:07:09,730 --> 00:07:10,950
to medžio trumpas.

130
00:07:10,950 --> 00:07:15,690
>> Tarkime, jūs norite atlikti operaciją
kiekvienas mazgas dvejetainiu medžiu.

131
00:07:15,690 --> 00:07:17,410
Kaip gali jums eiti apie tai?

132
00:07:17,410 --> 00:07:20,600
Na, jums gali rašyti rekursinį
funkcija, kuri atlieka operaciją

133
00:07:20,600 --> 00:07:24,450
patronuojančiai mazgas ir daro rekursyvūs
paskambinti į tą pačią funkciją,

134
00:07:24,450 --> 00:07:27,630
einančios į kairę ir
dešinysis vaikų mazgai.

135
00:07:27,630 --> 00:07:31,650
Pavyzdžiui, ši funkcija, rūšys, kad
keičia tam tikro mazgo vertę ir

136
00:07:31,650 --> 00:07:33,830
visus savo vaikus į 1.

137
00:07:33,830 --> 00:07:37,400
Bazine null mazgas priežasčių
Funkcija grąžina, nurodant

138
00:07:37,400 --> 00:07:41,290
kad nėra jokių mazgų
liko toje sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Leiskite vaikščioti per ją.

140
00:07:42,620 --> 00:07:44,340
Pirmasis iš tėvų yra 13.

141
00:07:44,340 --> 00:07:47,930
Mes pakeisti reikšmę į 1, ir tada skambinti
mūsų funkcija kairėje, taip pat

142
00:07:47,930 --> 00:07:49,600
kaip gerai.

143
00:07:49,600 --> 00:07:53,910
Funkcija, rūšys, vadinamas kairėje
sub-tree pirmas, todėl kairėje mazgas

144
00:07:53,910 --> 00:07:57,730
bus iš naujo 1 ir foo bus
būti paprašyta Šis mazgas vaikų,

145
00:07:57,730 --> 00:08:01,900
pirmas į kairę ir tada į dešinę,
ir taip toliau ir taip toliau.

146
00:08:01,900 --> 00:08:05,630
Ir pasakykite jiems, kad filialai neturi
bet daugiau vaikų, kad pats procesas

147
00:08:05,630 --> 00:08:09,700
toliau už teisę vaikams
kol visą medį mazgai yra

148
00:08:09,700 --> 00:08:11,430
paskiriamas į 1.

149
00:08:11,430 --> 00:08:15,390
>> Kaip matote, jūs ne tik
tik vienas grįžtamojo skambutis.

150
00:08:15,390 --> 00:08:17,930
Tiesiog kiek gaus darbą.

151
00:08:17,930 --> 00:08:21,200
Ką daryti, jei jūs turėjote medį, kur kiekvienas
mazgas turėjo tris vaikus,

152
00:08:21,200 --> 00:08:23,100
Kairysis, vidurinis ir dešinysis?

153
00:08:23,100 --> 00:08:24,886
Kaip redaguoti foo?

154
00:08:24,886 --> 00:08:25,860
Na, paprasta.

155
00:08:25,860 --> 00:08:30,250
Tiesiog pridėkite kitą rekursinį skambutį ir
pereiti į vidurį mazgas žymeklis.

156
00:08:30,250 --> 00:08:34,549
>> Rekursija yra labai galingas ir ne
paminėti elegantiškas, bet jis gali būti

157
00:08:34,549 --> 00:08:38,010
sudėtinga sąvoka ne pirmas, todėl
pacientui ir imtis savo laiką.

158
00:08:38,010 --> 00:08:39,370
Pradėti su bazine.

159
00:08:39,370 --> 00:08:42,650
Tai paprastai lengviausia nustatyti,
ir tada jūs galite dirbti

160
00:08:42,650 --> 00:08:43,830
atgal iš ten.

161
00:08:43,830 --> 00:08:46,190
Jūs žinote, jums reikia pasiekti savo
pagrindą, idant

162
00:08:46,190 --> 00:08:47,760
duoti jums keletą patarimų.

163
00:08:47,760 --> 00:08:53,120
Stenkitės reikšti vieną konkretų atvejį,
sąlygas kitais atvejais, arba pogrupių.

164
00:08:53,120 --> 00:08:54,700
>> Ačiū už žiūrėti šį trumpą.

165
00:08:54,700 --> 00:08:58,920
Bent jau, dabar jūs galite
suprasti, anekdotai, kaip šis.

166
00:08:58,920 --> 00:09:01,250
Mano vardas Zamyla, ir tai yra CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Pasinaudokite šia funkcija, hi,
negaliojančiu funkcija, kuri trunka

169
00:09:07,170 --> 00:09:09,212
int n, kaip įvestį.

170
00:09:09,212 --> 00:09:11,020
Bazinį scenarijų ateina pirmiausia.

171
00:09:11,020 --> 00:09:14,240
Jei n yra mažesnis už 0, spausdinti
"Bye" ir grįžti.

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