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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Jotta ymmärtäisimme
rekursio, sinun on

3
00:00:10,190 --> 00:00:13,820
ensin ymmärtää rekursio.

4
00:00:13,820 --> 00:00:17,280
Ottaa rekursio ohjelmien suunnitteluun keinoin
että sinulla on itseensä viittaavan

5
00:00:17,280 --> 00:00:18,570
määritelmiä.

6
00:00:18,570 --> 00:00:21,520
Rekursiivinen tietorakenteita, esimerkiksi
ovat tietorakenteita, jotka

7
00:00:21,520 --> 00:00:23,990
sisältyvät itse
niiden määritelmät.

8
00:00:23,990 --> 00:00:27,160
Mutta tänään, aiomme keskittyä
rekursiiviseen toimintoja.

9
00:00:27,160 --> 00:00:31,160
>> Muista, että funktiot tuloa,
argumentteja, ja palauttaa arvon niiden

10
00:00:31,160 --> 00:00:34,480
tuotos edustaa
Tämä kaavio täällä.

11
00:00:34,480 --> 00:00:38,060
Keksimme laatikon ruumis
toiminto, joka sisältää joukon

12
00:00:38,060 --> 00:00:42,340
ohjeet, jotka tulkitsevat
tulo ja antaa lähdön.

13
00:00:42,340 --> 00:00:45,660
Tarkastella lähemmin kehossa
toiminnon voi paljastaa puhelut

14
00:00:45,660 --> 00:00:47,430
myös muita toimintoja.

15
00:00:47,430 --> 00:00:51,300
Ota tämä yksinkertainen tehtävä, foo, että
ottaa yhden merkkijonon tulo-ja

16
00:00:51,300 --> 00:00:54,630
tulostaa kuinka monta kirjettä
että merkkijono on.

17
00:00:54,630 --> 00:00:58,490
Toiminto strlen, jousikvartetille pituus,
kutsutaan, joiden tuotanto on

18
00:00:58,490 --> 00:01:01,890
tarvitaan puhelun printf.

19
00:01:01,890 --> 00:01:05,770
>> Nyt, mitä tekee rekursiivinen funktio
erityisen se, että se kutsuu itseään.

20
00:01:05,770 --> 00:01:09,610
Voimme edustaa tämän rekursiivinen
soittaa tällä oranssi nuoli

21
00:01:09,610 --> 00:01:11,360
silmukoiden takaisin itselleen.

22
00:01:11,360 --> 00:01:15,630
Mutta täytäntöönpanosta itse uudestaan ​​vain
tee uusi rekursiokutsu, ja

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

24
00:01:17,150 --> 00:01:19,100
Mutta rekursiivinen toiminnot
ei voi olla ääretön.

25
00:01:19,100 --> 00:01:23,490
Heidän täytyy lopettaa jotenkin, tai
Ohjelmaa toteutetaan ikuisesti.

26
00:01:23,490 --> 00:01:27,680
>> Joten meidän täytyy löytää keino murtaa
ulos rekursiokutsua.

27
00:01:27,680 --> 00:01:29,900
Kutsumme tätä perustapaus.

28
00:01:29,900 --> 00:01:33,570
Kun pohja tapauksessa ehto täyttyy,
funktio palauttaa tekemättä

29
00:01:33,570 --> 00:01:34,950
toinen rekursiokutsu.

30
00:01:34,950 --> 00:01:39,610
Ota tämä toiminto, hi, void funktio
joka vie int n syötteenä.

31
00:01:39,610 --> 00:01:41,260
Perustapauksessa tulee ensin.

32
00:01:41,260 --> 00:01:46,220
Jos n on pienempi kuin nolla, tulosta bye ja
palata Kaikissa muissa tapauksissa

33
00:01:46,220 --> 00:01:49,400
toiminto tulostaa hi ja toteuttaa
rekursiokutsu.

34
00:01:49,400 --> 00:01:53,600
Toinen puhelu toiminto hi kanssa
pienennetään syötetty arvo.

35
00:01:53,600 --> 00:01:56,790
>> Nyt, vaikka me painamme hi,
toiminto ei lopeta ennen kuin olemme

36
00:01:56,790 --> 00:02:00,370
palauttaa sen paluuarvon tyyppi,
tässä tapauksessa mitätön.

37
00:02:00,370 --> 00:02:04,830
Joten jokaisella n muiden kuin perusversion,
Tämän toiminnon hi palaa hi

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

39
00:02:06,890 --> 00:02:10,050
Koska tämä toiminto on mitätön, vaikka me
ei nimenomaisesti kirjoita palata tänne.

40
00:02:10,050 --> 00:02:12,000
Me vain suorittaa toiminnon.

41
00:02:12,000 --> 00:02:16,960
Joten soittaa hi (3) tulostaa hi ja
suorita hi (2), joka toteuttaa hi (1) yksi

42
00:02:16,960 --> 00:02:20,560
joka toteuttaa hi (0), jossa
Perustapauksessa ehto täyttyy.

43
00:02:20,560 --> 00:02:24,100
Joten hi (0) tulostaa bye ja palaa.

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

45
00:02:24,990 --> 00:02:28,690
Joten nyt ymmärrämme perusasiat
rekursiivinen toiminnot, että he tarvitsevat

46
00:02:28,690 --> 00:02:32,730
vähintään yhden emäksen tapauksessa sekä
rekursiokutsu, nyt siirtyä

47
00:02:32,730 --> 00:02:34,120
mielekkäämmäksi esimerkki.

48
00:02:34,120 --> 00:02:37,830
Joka ei vain palaa
mitätöidä mitä tahansa.

49
00:02:37,830 --> 00:02:41,340
>> Katsotaanpa katsomaan factorial
toimintaa käytetään yleisimmin

50
00:02:41,340 --> 00:02:43,660
todennäköisyys laskelmat.

51
00:02:43,660 --> 00:02:48,120
Kertoma n on tuote, joka
pienempi positiivinen kokonaisluku

52
00:02:48,120 --> 00:02:49,400
ja suuruudeltaan n.

53
00:02:49,400 --> 00:02:56,731
Joten kertoma viisi on 5 kertaa 4 kertaa
3 kertaa 2 kertaa 1, jolloin saatiin 120.

54
00:02:56,731 --> 00:03:01,400
Neljä kertoma on 4 kertaa 3 kertaa
2 kertaa 1 antaa 24.

55
00:03:01,400 --> 00:03:04,910
Ja sama sääntö pätee
Minkä tahansa positiivinen kokonaisluku.

56
00:03:04,910 --> 00:03:08,670
>> Joten miten me saatamme kirjoittaa rekursiivinen
joka laskee kertoman

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

58
00:03:09,960 --> 00:03:14,700
No, meidän täytyy tunnistaa sekä
perustapauksen ja rekursiokutsu.

59
00:03:14,700 --> 00:03:18,250
Rekursiokutsu on sama
kaikissa tapauksissa paitsi pohja

60
00:03:18,250 --> 00:03:21,420
tapauksessa, mikä tarkoittaa, että meidän täytyy
löytää malli, joka antaa meille

61
00:03:21,420 --> 00:03:23,350
halutun tuloksen.

62
00:03:23,350 --> 00:03:30,270
>> Tästä esimerkiksi tarkistaa, kuinka 5 kertoma
liittyy kertomalla 4 3 2 1

63
00:03:30,270 --> 00:03:33,010
Ja jo samana kertominen
löytyy täältä,

64
00:03:33,010 --> 00:03:35,430
määritelmä 4 kertoma.

65
00:03:35,430 --> 00:03:39,810
Näemme siis, että 5 kertoma on
vain 5 kertaa 4 kertoma.

66
00:03:39,810 --> 00:03:43,360
Nyt tämä malli sovelletaan
4 kertoma samoin?

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

68
00:03:44,280 --> 00:03:49,120
Näemme, että 4 kertoma sisältää
kertomalla 3 kertaa 2 kertaa 1,

69
00:03:49,120 --> 00:03:51,590
Aivan sama määritelmä kuin 3 kertoma.

70
00:03:51,590 --> 00:03:56,950
Joten 4 kertoma on yhtä kuin 4 kertaa 3
kertoma, ja niin edelleen ja niin edelleen meidän

71
00:03:56,950 --> 00:04:02,170
kuvio tikkuja kunnes 1 kertoma, joka
määritelmän on yhtä suuri kuin 1.

72
00:04:02,170 --> 00:04:04,950
>> Ei ole muita myönteisiä
kokonaislukuja vasemmalle.

73
00:04:04,950 --> 00:04:07,870
Joten meillä on malli
meidän rekursiokutsu.

74
00:04:07,870 --> 00:04:13,260
n kertoma on yhtä kuin n kertaa
kertoma n miinus 1.

75
00:04:13,260 --> 00:04:14,370
Ja meidän tukikohta tapauksessa?

76
00:04:14,370 --> 00:04:17,370
Että olette vain meidän määritelmä
1 kertoma.

77
00:04:17,370 --> 00:04:19,995
>> Joten nyt voimme siirtyä kirjallisesti
funktion koodin.

78
00:04:19,995 --> 00:04:24,110
Peruskoron tapauksessa meillä on
ehto n on on 1, jos

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

80
00:04:25,780 --> 00:04:29,280
Sitten siirryn rekursiokutsu,
palaamme n kertaa

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

82
00:04:32,180 --> 00:04:33,590
>> Nyt testata tätä meidän.

83
00:04:33,590 --> 00:04:35,900
Kokeillaan kertoma 4.

84
00:04:35,900 --> 00:04:39,420
Per meidän tehtävämme on yhtä
4 kertaa factorial (3).

85
00:04:39,420 --> 00:04:43,040
Kertoma (3) on yhtä suuri kuin
3 kertaa kertoma (2).

86
00:04:43,040 --> 00:04:48,700
Kertoma (2) on yhtä kuin 2 kertaa
kertoma (1), joka palauttaa 1.

87
00:04:48,700 --> 00:04:52,490
Kertoma (2) nyt palauttaa 2 kertaa 1, 2.

88
00:04:52,490 --> 00:04:55,960
Kertoma (3) voidaan nyt palata
3 kertaa 2, 6.

89
00:04:55,960 --> 00:05:02,490
Ja lopuksi, kertoma (4)
palauttaa 4 kertaa 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Jos olet kohtaaminen vaikeuksia
kanssa rekursiokutsu, teeskennellä, että

91
00:05:06,780 --> 00:05:09,660
toiminto toimii jo.

92
00:05:09,660 --> 00:05:13,450
Mitä tarkoitan tällä, että sinun pitäisi
luota rekursiokutsua palata

93
00:05:13,450 --> 00:05:15,100
oikeita arvoja.

94
00:05:15,100 --> 00:05:18,960
Esimerkiksi, jos tiedän, että
kertoma (5) on yhtä kuin 5 kertaa

95
00:05:18,960 --> 00:05:24,870
kertoma (4), aion luottaa siihen, että
kertoma (4) antaa minulle 24.

96
00:05:24,870 --> 00:05:28,510
Ajattele sitä muuttuja, jos
on, kuten jos olet jo määritelty

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

98
00:05:30,070 --> 00:05:33,850
Joten mistään kertoma (n), se on
tuote n ja

99
00:05:33,850 --> 00:05:35,360
edellinen kertoma.

100
00:05:35,360 --> 00:05:38,130
Ja tämä edellinen kertoma
saadaan soittamalla

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

102
00:05:41,330 --> 00:05:45,130
>> Nyt, katso jos voit toteuttaa
rekursiivinen funktio itse.

103
00:05:45,130 --> 00:05:50,490
Kuormitus terminaalin tai run.cs50.net,
ja kirjoittaa funktio summa

104
00:05:50,490 --> 00:05:54,770
joka vie kokonaisluku n ja palauttaa
summa peräkkäistä positiivista

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

106
00:05:57,490 --> 00:06:01,000
Olen kirjoittanut ulos summia joidenkin
arvot auttaa sinua meidän.

107
00:06:01,000 --> 00:06:04,030
Ensinnäkin selvittää
perustapauksen kunnossa.

108
00:06:04,030 --> 00:06:06,170
Sitten, katso summa (5).

109
00:06:06,170 --> 00:06:09,270
Voitko ilmaisevat sen
toisen summa?

110
00:06:09,270 --> 00:06:11,290
Nyt, entä summa (4)?

111
00:06:11,290 --> 00:06:15,630
Miten voit ilmaista summan (4)
toisen suhteen summa?

112
00:06:15,630 --> 00:06:19,655
>> Kun olet summa (5) ja summa (4)
ilmaistuna muut summat, katso

113
00:06:19,655 --> 00:06:22,970
jos voit tunnistaa
malli summa (n).

114
00:06:22,970 --> 00:06:26,190
Jos ei, kokeile muutamia muita numeroita
ja ilmaista summia

115
00:06:26,190 --> 00:06:28,410
toisen suhteen numeroita.

116
00:06:28,410 --> 00:06:31,930
Tunnistamalla kaavoja diskreetti
numerot, olet hyvin teidän tapa

117
00:06:31,930 --> 00:06:34,320
tunnistaa malli tahansa n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursio on todella tehokas työkalu,
niin tietysti se ei rajoitu

119
00:06:38,040 --> 00:06:39,820
matemaattisia funktioita.

120
00:06:39,820 --> 00:06:44,040
Rekursio voidaan käyttää hyvin tehokkaasti
käsitellessään puita esimerkiksi.

121
00:06:44,040 --> 00:06:47,210
Tutustu lyhyttä puita
perusteellisempi tarkastelu, mutta nyt

122
00:06:47,210 --> 00:06:51,140
Muistutan, että binäärihaku puita, vuonna
Erityisesti koostuvat solmuja, kukin

123
00:06:51,140 --> 00:06:53,820
joiden arvo ja kaksi solmun viitteitä.

124
00:06:53,820 --> 00:06:57,270
Yleensä tämä edustaa
isäsolmuun ottaa yksi rivi osoittaa

125
00:06:57,270 --> 00:07:01,870
vasemmalle lapsisolmuun ja yksi
oikealle lapsisolmuun.

126
00:07:01,870 --> 00:07:04,510
Rakenne binäärihaku
puu soveltuu hyvin

127
00:07:04,510 --> 00:07:05,940
to rekursiivinen haku.

128
00:07:05,940 --> 00:07:09,730
Rekursiokutsu joko kulkee
vasemmalle tai oikealle solmu, mutta enemmän

129
00:07:09,730 --> 00:07:10,950
Kyseisen puussa lyhyt.

130
00:07:10,950 --> 00:07:15,690
>> Sano haluat suorittaa toimintansa
jokainen solmu binääripuun.

131
00:07:15,690 --> 00:07:17,410
Miten voi mennä siitä?

132
00:07:17,410 --> 00:07:20,600
No, voisit kirjoittaa rekursiivinen
toiminto, joka suorittaa operaation

133
00:07:20,600 --> 00:07:24,450
vanhemman solmun ja tekee rekursiivinen
soittaa sama tehtävä,

134
00:07:24,450 --> 00:07:27,630
kulkee vasemmalle ja
oikea lapsi solmut.

135
00:07:27,630 --> 00:07:31,650
Esimerkiksi tämä toiminto, foo, että
Arvo vaihtuu tietyn solmun ja

136
00:07:31,650 --> 00:07:33,830
kaikki sen lapset 1.

137
00:07:33,830 --> 00:07:37,400
Base kyseessä null solmun syitä
funktio palauttaa, mikä osoittaa,

138
00:07:37,400 --> 00:07:41,290
että ei ole mitään solmuja
jäljellä, että sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Katsotaanpa kulkea läpi.

140
00:07:42,620 --> 00:07:44,340
Ensimmäinen vanhempi on 13.

141
00:07:44,340 --> 00:07:47,930
Muutamme arvoksi 1 ja soita
meidän tehtävämme vasemmalla samoin

142
00:07:47,930 --> 00:07:49,600
kuin oikea.

143
00:07:49,600 --> 00:07:53,910
Toiminto, foo, kutsutaan vasemmalla
sub-tree ensin, niin vasen solmu

144
00:07:53,910 --> 00:07:57,730
tulee määrittää uudelleen 1 ja foo
voidaan kutsua että solmun lapset,

145
00:07:57,730 --> 00:08:01,900
ensin vasemmalle ja sitten oikealle,
ja niin edelleen ja niin edelleen.

146
00:08:01,900 --> 00:08:05,630
Ja kertoa heille, että oksat eivät ole
enempää lapsia niin sama prosessi

147
00:08:05,630 --> 00:08:09,700
jatkuu oikealle lapsille
kunnes koko puun solmut ovat

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

149
00:08:11,430 --> 00:08:15,390
>> Kuten näette, et ole rajoitettu
vain yksi rekursiokutsu.

150
00:08:15,390 --> 00:08:17,930
Yhtä monta kuin saavat työnsä tehtyä.

151
00:08:17,930 --> 00:08:21,200
Mitä jos sinulla olisi puu, jossa kukin
solmu oli kolme lasta,

152
00:08:21,200 --> 00:08:23,100
Vasen, keskimmäinen ja oikea?

153
00:08:23,100 --> 00:08:24,886
Miten muokkaat foo?

154
00:08:24,886 --> 00:08:25,860
No, yksinkertainen.

155
00:08:25,860 --> 00:08:30,250
Vain lisätä toisen rekursiokutsu ja
kulkea keskellä solmu osoitin.

156
00:08:30,250 --> 00:08:34,549
>> Rekursio on hyvin voimakas eikä
mainitse elegantti, mutta se voi olla

157
00:08:34,549 --> 00:08:38,010
vaikea käsite aluksi, joten
potilaaseen ja vie aikaa.

158
00:08:38,010 --> 00:08:39,370
Aloita perustapaus.

159
00:08:39,370 --> 00:08:42,650
Se on yleensä helpoin tunnistaa,
ja sitten voit työskennellä

160
00:08:42,650 --> 00:08:43,830
taaksepäin sieltä.

161
00:08:43,830 --> 00:08:46,190
Tiedät mitä tarvitset saavuttaaksesi
base tapauksessa, niin että voima

162
00:08:46,190 --> 00:08:47,760
antaa sinulle muutamia vinkkejä.

163
00:08:47,760 --> 00:08:53,120
Yritä ilmaista erityistapaus
kannalta muissa tapauksissa, tai osa-sarjaa.

164
00:08:53,120 --> 00:08:54,700
>> Kiitos katsomassa tämä lyhyt.

165
00:08:54,700 --> 00:08:58,920
Ainakin, nyt voit
ymmärtää vitsejä kuten tämä.

166
00:08:58,920 --> 00:09:01,250
Nimeni on Zamyla, ja tämä on CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Ota tämä toiminto, hi,
void funktio, joka ottaa

169
00:09:07,170 --> 00:09:09,212
int, n, syötteenä.

170
00:09:09,212 --> 00:09:11,020
Perustapauksessa tulee ensin.

171
00:09:11,020 --> 00:09:14,240
Jos n on pienempi kuin 0, tulosta
"Hei" ja palata.

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