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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Selleks, et mõista
rekursioon, peate

3
00:00:10,190 --> 00:00:13,820
kõigepealt aru rekursioon.

4
00:00:13,820 --> 00:00:17,280
Võttes rekursioon on programmi koostamisel tähendab,
et teil on eneseleosutavad

5
00:00:17,280 --> 00:00:18,570
mõisted.

6
00:00:18,570 --> 00:00:21,520
Rekursiivne andmestruktuuride näiteks
on andmestruktuurid

7
00:00:21,520 --> 00:00:23,990
sisaldama ise
nende definitsioonid.

8
00:00:23,990 --> 00:00:27,160
Aga täna me ei kavatse keskenduda
on rekursiivne funktsioone.

9
00:00:27,160 --> 00:00:31,160
>> Tuletame meelde, et ülesandeid võtma sisendite
argumente ning tagastab väärtuse kui nende

10
00:00:31,160 --> 00:00:34,480
väljund esindajad
see skeem siin.

11
00:00:34,480 --> 00:00:38,060
Me mõtleme kasti kehas
Funktsiooni sisaldav komplekt

12
00:00:38,060 --> 00:00:42,340
juhiseid, et tõlgendada
sisend ja annab väljundi.

13
00:00:42,340 --> 00:00:45,660
Võttes lähemalt kehas
funktsioon võiks paljastada kõned

14
00:00:45,660 --> 00:00:47,430
muud funktsioonid samuti.

15
00:00:47,430 --> 00:00:51,300
Võtke see lihtne ülesanne, suva, et
võtab ühe stringi sisendiks ja

16
00:00:51,300 --> 00:00:54,630
prindib mitu tähte
et string on.

17
00:00:54,630 --> 00:00:58,490
Funktsioon strlen, keelpilliorkestrile pikkus,
nimetatakse, kelle toodang on

18
00:00:58,490 --> 00:01:01,890
vajalik helistage printf.

19
00:01:01,890 --> 00:01:05,770
>> Nüüd teebki rekursiivne funktsioon
eriline on see, et ta nimetab ennast.

20
00:01:05,770 --> 00:01:09,610
Me ei esinda see rekursiivne
kutsuvad seda oranž arrow

21
00:01:09,610 --> 00:01:11,360
silmukoiminen tagasi ise.

22
00:01:11,360 --> 00:01:15,630
Aga täidesaatva ennast uuesti alles
teha teise rekursiivne kõne ja

23
00:01:15,630 --> 00:01:17,150
teine ​​ja teine.

24
00:01:17,150 --> 00:01:19,100
Aga rekursiivne funktsioone
ei saa olla lõpmatu.

25
00:01:19,100 --> 00:01:23,490
Nad peavad lõpetama kuidagi, või oma
Programm kestab igavesti.

26
00:01:23,490 --> 00:01:27,680
>> Nii et me peame leidma viisi, kuidas murda
välja rekursiivne kõne.

27
00:01:27,680 --> 00:01:29,900
Me nimetame seda tugipunkti.

28
00:01:29,900 --> 00:01:33,570
Kui tugipunkti tingimus on täidetud,
tagastab funktsioon tegemata

29
00:01:33,570 --> 00:01:34,950
teine ​​rekursiivne kõne.

30
00:01:34,950 --> 00:01:39,610
Võta see funktsioon, hi, tühine funktsioon
mis võtab int n sisendiks.

31
00:01:39,610 --> 00:01:41,260
Baasjuhtumi jõuab.

32
00:01:41,260 --> 00:01:46,220
Kui n on väiksem kui null, print bye ja
tagasi Kõikidel muudel juhtudel,

33
00:01:46,220 --> 00:01:49,400
funktsioon prindib hi ja ellu
rekursiivne kõne.

34
00:01:49,400 --> 00:01:53,600
Teine kõne funktsioon hi koos
decremented sisendkäibemaks.

35
00:01:53,600 --> 00:01:56,790
>> Nüüd, kuigi me printida hi,
funktsioon ei lõpe enne, kui me

36
00:01:56,790 --> 00:02:00,370
tagasi tema naasmise tüüp
sel juhul tühine.

37
00:02:00,370 --> 00:02:04,830
Seega iga n peale baasi juhul
Selle funktsiooni hi naaseb hi

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

39
00:02:06,890 --> 00:02:10,050
Kuna see funktsioon on tühine küll, me
ei ole selgesõnaliselt kirjuta siia tagasi.

40
00:02:10,050 --> 00:02:12,000
Me lihtsalt funktsiooni täitmiseks.

41
00:02:12,000 --> 00:02:16,960
Nii kutsutakse hi (3) prinditakse hi ja
täita hi (2), mis käivitab hi (1) üks

42
00:02:16,960 --> 00:02:20,560
täitval hi (0), kus
tugipunkti tingimus on täidetud.

43
00:02:20,560 --> 00:02:24,100
Nii hi (0) prindib bye ja tagastab.

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

45
00:02:24,990 --> 00:02:28,690
Nüüd, kui me aru põhitõdesid
rekursiivne funktsioone, mida nad vajavad

46
00:02:28,690 --> 00:02:32,730
vähemalt ühe aluse puhul samuti
rekursiivne kõne, liigume edasi

47
00:02:32,730 --> 00:02:34,120
otstarbekam näiteks.

48
00:02:34,120 --> 00:02:37,830
Üks, mis ei ole lihtsalt tagasi
tühistada ükskõik mida.

49
00:02:37,830 --> 00:02:41,340
>> Võtame pilk faktoriaal
toiming, mida kasutatakse kõige sagedamini

50
00:02:41,340 --> 00:02:43,660
tõenäosuse arvutused.

51
00:02:43,660 --> 00:02:48,120
Faktoriaal n on toote iga
positiivse täisarvu alla

52
00:02:48,120 --> 00:02:49,400
ja võrdne n.

53
00:02:49,400 --> 00:02:56,731
Nii faktoriaal viis on 5 korda 4 korda
3 korda 2 korda 1, saades 120.

54
00:02:56,731 --> 00:03:01,400
Neli faktoriaal on 4 korda 3 korda
2 korda 1, saadi 24.

55
00:03:01,400 --> 00:03:04,910
Ja sama reegel kehtib
mistahes positiivse täisarvu.

56
00:03:04,910 --> 00:03:08,670
>> Niisiis, kuidas võiks me kirjutada rekursiivne
funktsioon, mis arvutab faktoriaali

57
00:03:08,670 --> 00:03:09,960
on number?

58
00:03:09,960 --> 00:03:14,700
Noh, me peame kindlaks nii
tugipunkti ja rekursiivne kõne.

59
00:03:14,700 --> 00:03:18,250
Kirjutan üleskutse on sama
Kõigi juhtudel arvatud aluse

60
00:03:18,250 --> 00:03:21,420
puhul, mis tähendab, et me peame
leida muster, mis annab meile meie

61
00:03:21,420 --> 00:03:23,350
soovitud tulemus.

62
00:03:23,350 --> 00:03:30,270
>> Selle näiteks näha, kuidas 5 faktoriaalses
hõlmab korrutades 4 3 2 1

63
00:03:30,270 --> 00:03:33,010
Ja selsamal korrutamine
leidub siin

64
00:03:33,010 --> 00:03:35,430
määratlus 4 faktoriaal.

65
00:03:35,430 --> 00:03:39,810
Nii me näeme, et 5 faktoriaal on
ainult 5 korda 4 faktoriaal.

66
00:03:39,810 --> 00:03:43,360
Nüüd see muster kohaldatakse
4 faktoriaal ka?

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

68
00:03:44,280 --> 00:03:49,120
Me näeme, et 4 faktoriaal sisaldab
korrutamine 3 korda 2 korda 1,

69
00:03:49,120 --> 00:03:51,590
väga määratlusega 3 faktoriaal.

70
00:03:51,590 --> 00:03:56,950
Nii 4 faktoriaal on võrdne 4 korda 3
faktorilise, ja nii edasi ja nii edasi meie

71
00:03:56,950 --> 00:04:02,170
muster paistab kuni 1 faktoriaal, mis
definitsiooni on võrdne 1.

72
00:04:02,170 --> 00:04:04,950
>> Ei ole muid positiivseid
täisarvud vasakule.

73
00:04:04,950 --> 00:04:07,870
Nii et meil on mustri
meie rekursiivne kõne.

74
00:04:07,870 --> 00:04:13,260
n faktoriaal on võrdne n korda
faktoriaali n miinus 1.

75
00:04:13,260 --> 00:04:14,370
Ja meie baasi puhul?

76
00:04:14,370 --> 00:04:17,370
See lihtsalt on meie definitsioon
1 faktoriaal.

77
00:04:17,370 --> 00:04:19,995
>> Nüüd me saame liikuda kirjalikult
kood funktsiooni.

78
00:04:19,995 --> 00:04:24,110
Baastestis juhul on meil
tingimus n on võrdne 1, kus

79
00:04:24,110 --> 00:04:25,780
me tagasi 1.

80
00:04:25,780 --> 00:04:29,280
Siis lähevad peale rekursiivne kõne,
me tagasi n korda

81
00:04:29,280 --> 00:04:32,180
faktoriaali n miinus 1.

82
00:04:32,180 --> 00:04:33,590
>> Nüüd testida meie.

83
00:04:33,590 --> 00:04:35,900
Proovime faktoriaal 4.

84
00:04:35,900 --> 00:04:39,420
Per meie funktsioon on võrdne
4 korda faktoriaal (3).

85
00:04:39,420 --> 00:04:43,040
Faktoriaali (3) on võrdne
3 korda faktoriaal (2).

86
00:04:43,040 --> 00:04:48,700
Faktoriaali (2) on võrdne 2 korda
faktoriaal (1), mis tagastab 1.

87
00:04:48,700 --> 00:04:52,490
Faktoriaali (2) nüüd tagasi 2 korda 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktoriaali (3) saab nüüd tagasi
3 korda 2, 6.

89
00:04:55,960 --> 00:05:02,490
Ja lõpuks, faktoriaal (4)
tagasi 4 korda 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Kui sul tekib mingeid raskusi
koos kirjutan Kõne teeselda, et

91
00:05:06,780 --> 00:05:09,660
funktsioon töötab juba.

92
00:05:09,660 --> 00:05:13,450
Mida ma mõtlen on see, et sa peaksid
usalda oma rekursiivne kõne tagasi

93
00:05:13,450 --> 00:05:15,100
õigeid väärtusi.

94
00:05:15,100 --> 00:05:18,960
Näiteks, kui ma tean, et
faktoriaali (5) võrdub 5 korda

95
00:05:18,960 --> 00:05:24,870
faktoriaal (4) ma usun, et
faktoriaali (4) annab mulle 24.

96
00:05:24,870 --> 00:05:28,510
Mõtle seda muutujat, kui te
Will, kui sa juba määratletud

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

98
00:05:30,070 --> 00:05:33,850
Nii tahes faktoriaalses (n), on see
produkti n ja

99
00:05:33,850 --> 00:05:35,360
Eelmise faktoriaal.

100
00:05:35,360 --> 00:05:38,130
Ja see eelmine faktoriaal
Saadakse helistades

101
00:05:38,130 --> 00:05:41,330
faktoriaali n miinus 1.

102
00:05:41,330 --> 00:05:45,130
>> Nüüd, vaata kui saad rakendada
rekursiivne funktsioon ise.

103
00:05:45,130 --> 00:05:50,490
Laadi üles oma terminali või run.cs50.net,
ja kirjutada funktsiooni summa

104
00:05:50,490 --> 00:05:54,770
mis võtab täisarv n ja tagastab
summa kõikide järjestikust positiivset

105
00:05:54,770 --> 00:05:57,490
täisarvud n 1.

106
00:05:57,490 --> 00:06:01,000
Olen kirjutanud välja summasid mõne
väärtused, mis aitavad teil oma.

107
00:06:01,000 --> 00:06:04,030
Esiteks, selgitada,
tugipunkti seisukorras.

108
00:06:04,030 --> 00:06:06,170
Siis vaatame summa (5).

109
00:06:06,170 --> 00:06:09,270
Kas sa väljendada seda
teise summa?

110
00:06:09,270 --> 00:06:11,290
Nüüd, kuidas summa (4)?

111
00:06:11,290 --> 00:06:15,630
Kuidas saab väljendada summa (4)
poolest teine ​​summa?

112
00:06:15,630 --> 00:06:19,655
>> Kui teil on summa (5) ja summa (4)
väljendatud muude summade, vt

113
00:06:19,655 --> 00:06:22,970
kui saate tuvastada
mustrit koguhulk (n).

114
00:06:22,970 --> 00:06:26,190
Kui ei, siis proovige mõne muu numbrid
ja väljendada oma summasid

115
00:06:26,190 --> 00:06:28,410
tingimustel teise numbrid.

116
00:06:28,410 --> 00:06:31,930
Tuues välja patterns diskreetne
numbrid, sa oled hästi oma viis

117
00:06:31,930 --> 00:06:34,320
identifitseerimiseks mustri tahes n.

118
00:06:34,320 --> 00:06:38,040
>> Recursion on tõesti võimas vahend,
nii et muidugi see ei ole piiratud

119
00:06:38,040 --> 00:06:39,820
matemaatilisi funktsioone.

120
00:06:39,820 --> 00:06:44,040
Rekursioon saab kasutada väga tõhusalt
kui tegemist on puud näiteks.

121
00:06:44,040 --> 00:06:47,210
Tutvu lühike puud
põhjalikumat läbivaatamist, kuid nüüd

122
00:06:47,210 --> 00:06:51,140
Meenutame, et binaarne otsing puud sisse
Eelkõige koosnevad sõlmed, iga

123
00:06:51,140 --> 00:06:53,820
väärtusega ja kaks sõlme suunanäitajaks.

124
00:06:53,820 --> 00:06:57,270
Tavaliselt on see esindab
ematipp on üks joon suunaga

125
00:06:57,270 --> 00:07:01,870
vasakule Järglassõlme ja üks
paremal Järglassõlme.

126
00:07:01,870 --> 00:07:04,510
Struktuuri binaarne otsing
puu sobib hästi

127
00:07:04,510 --> 00:07:05,940
et rekursiivne otsing.

128
00:07:05,940 --> 00:07:09,730
Rekursiivne kõne kas möödub
vasakule või paremale sõlme, kuid rohkem

129
00:07:09,730 --> 00:07:10,950
Selle puu lühike.

130
00:07:10,950 --> 00:07:15,690
>> Ütle, et tahad teha operatsioon
iga sõlme kahendpuu.

131
00:07:15,690 --> 00:07:17,410
Kuidas võiks edasi minna on?

132
00:07:17,410 --> 00:07:20,600
Noh, sa võiksid kirjutada rekursiivne
funktsioon, mis täidab operatsiooni

133
00:07:20,600 --> 00:07:24,450
vanemale sõlme ja teeb rekursiivne
kõne on sama funktsioon,

134
00:07:24,450 --> 00:07:27,630
kulgeb vasakule ja
õige tütartippu.

135
00:07:27,630 --> 00:07:31,650
Näiteks see funktsioon, suva, mis
muudab väärtust antud sõlm ja

136
00:07:31,650 --> 00:07:33,830
kõik tema lapsed 1.

137
00:07:33,830 --> 00:07:37,400
Baasi puhul null sõlme põhjused
funktsioon tagastama, näidates

138
00:07:37,400 --> 00:07:41,290
et seal ei ole sõlmede
jäänud, et sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Vaatame seda.

140
00:07:42,620 --> 00:07:44,340
Esimene vanem on 13.

141
00:07:44,340 --> 00:07:47,930
Muudame väärtus 1 ja seejärel kõne
Meie ülesanne vasakul samuti

142
00:07:47,930 --> 00:07:49,600
kui paremale.

143
00:07:49,600 --> 00:07:53,910
Funktsioon, suva, mida nimetatakse vasakul
sub-tree esiteks nii vasaku sõlme

144
00:07:53,910 --> 00:07:57,730
saab ümber jaotada 1 ja foo
kutsutakse, et sõlm lapsed

145
00:07:57,730 --> 00:08:01,900
esimene vasakule ja seejärel paremale
ja nii edasi ja nii edasi.

146
00:08:01,900 --> 00:08:05,630
Ja ütle neile, et oksad ei ole
veel lapsi nii sama protsessi

147
00:08:05,630 --> 00:08:09,700
jätkub õiges lapsed
kuni kogu puu sõlmed

148
00:08:09,700 --> 00:08:11,430
ümber jaotada 1.

149
00:08:11,430 --> 00:08:15,390
>> Nagu näete, siis ei ole piiratud
ainult ühe rekursiivse helistada.

150
00:08:15,390 --> 00:08:17,930
Just nii palju kui saad töö tehtud.

151
00:08:17,930 --> 00:08:21,200
Mida teha, kui teil on olnud puu, kus iga
sõlm oli kolm last,

152
00:08:21,200 --> 00:08:23,100
Vasakpoolne, keskmine ja parempoolne?

153
00:08:23,100 --> 00:08:24,886
Kuidas sa muuta suva?

154
00:08:24,886 --> 00:08:25,860
Noh, lihtne.

155
00:08:25,860 --> 00:08:30,250
Lihtsalt lisada veel rekursiivne kõne ja
edasi keset sõlme pointer.

156
00:08:30,250 --> 00:08:34,549
>> Recursion on väga võimas ja mitte
mainida elegantne, kuid see võib olla

157
00:08:34,549 --> 00:08:38,010
keeruline mõiste esimesel, nii et
patsient ja võtke aega.

158
00:08:38,010 --> 00:08:39,370
Alusta tugipunkti.

159
00:08:39,370 --> 00:08:42,650
See on tavaliselt kõige lihtsam selgitada,
ja siis saate töötada

160
00:08:42,650 --> 00:08:43,830
tagasi sealt.

161
00:08:43,830 --> 00:08:46,190
Sa tead, mida vajate, et saavutada oma
tugipunkti, nii et võiks

162
00:08:46,190 --> 00:08:47,760
teile mõned vihjed.

163
00:08:47,760 --> 00:08:53,120
Püüdke väljendada ühe konkreetse juhtumi
Muid juhtumeid või sub-komplekti.

164
00:08:53,120 --> 00:08:54,700
>> Täname vaadates seda lühike.

165
00:08:54,700 --> 00:08:58,920
Vähemalt nüüd saab
mõista nalja nagu see.

166
00:08:58,920 --> 00:09:01,250
Minu nimi on Zamyla ja see on CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Võta see funktsioon, hi,
void funktsioon, mis võtab

169
00:09:07,170 --> 00:09:09,212
int n, kui sisend.

170
00:09:09,212 --> 00:09:11,020
Baasjuhtumi jõuab.

171
00:09:11,020 --> 00:09:14,240
Kui n on väiksem kui 0, print
"Bye" ja tagasi.

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