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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Da bi razumeli
rekurzija, morate

3
00:00:10,190 --> 00:00:13,820
najprej razumeti rekurzijo.

4
00:00:13,820 --> 00:00:17,280
Ob rekurzijo v program za načrtovanje sredstev
da imate avtoreferenčni

5
00:00:17,280 --> 00:00:18,570
opredelitve.

6
00:00:18,570 --> 00:00:21,520
Rekurzivne podatkovne strukture, na primer,
so podatkovne strukture, ki

7
00:00:21,520 --> 00:00:23,990
se vključujejo v
njihove definicije.

8
00:00:23,990 --> 00:00:27,160
Toda danes se bomo osredotočili
na rekurzivnih funkcij.

9
00:00:27,160 --> 00:00:31,160
>> Spomnimo se, da funkcije, da vložkov,
argumente, in vrne vrednost kot njihovi

10
00:00:31,160 --> 00:00:34,480
izhod, ki ga zastopa
Ta diagram tukaj.

11
00:00:34,480 --> 00:00:38,060
Mi bomo pomislite na polja v telesu
funkcijo, ki vsebuje niz

12
00:00:38,060 --> 00:00:42,340
navodila, ki razlagajo
vhod in izhodno.

13
00:00:42,340 --> 00:00:45,660
Ob podrobnejši pogled v notranjost telesa
funkcijo bi lahko razkrili klicev na

14
00:00:45,660 --> 00:00:47,430
druge funkcije, kot tudi.

15
00:00:47,430 --> 00:00:51,300
Vzemite to preprosto funkcijo, foo, da
traja samo en niz, kot vhod in

16
00:00:51,300 --> 00:00:54,630
natisne, koliko črk
da ima niz.

17
00:00:54,630 --> 00:00:58,490
Funkcija strlen, za dolžino niza,
se imenuje, katerih proizvodnja je

18
00:00:58,490 --> 00:01:01,890
potrebna za klic v printf.

19
00:01:01,890 --> 00:01:05,770
>> Zdaj, kaj naredi rekurzivno funkcijo
Posebno je, da je sama zahteva.

20
00:01:05,770 --> 00:01:09,610
Lahko zastopajo to rekurzivno
Klicanje s tem oranžna puščica

21
00:01:09,610 --> 00:01:11,360
vračanjem na sebi.

22
00:01:11,360 --> 00:01:15,630
Samo, ampak se je spet izvršitvena
vzpostavite nov rekurzivni klic, in

23
00:01:15,630 --> 00:01:17,150
drugo in drugo.

24
00:01:17,150 --> 00:01:19,100
Ampak rekurzivne funkcije
ne more biti neskončna.

25
00:01:19,100 --> 00:01:23,490
Imajo na koncu nekako, ali vaš
Program bo trajal večno.

26
00:01:23,490 --> 00:01:27,680
>> Zato moramo najti način, da bi prekinil
ven iz rekurzivnih klicev.

27
00:01:27,680 --> 00:01:29,900
Osnovna pravimo tega.

28
00:01:29,900 --> 00:01:33,570
Ko je izpolnjen pogoj osnovna izpolnjen,
funkcija vrne, ne da bi

29
00:01:33,570 --> 00:01:34,950
en rekurzivni klic.

30
00:01:34,950 --> 00:01:39,610
Vzemite to funkcijo, hi, funkcijo void
ki traja int n kot vhod.

31
00:01:39,610 --> 00:01:41,260
Osnovna na prvem mestu.

32
00:01:41,260 --> 00:01:46,220
Če je n manj kot nič, tiskanje in adijo
vrnitev vseh drugih primerih,

33
00:01:46,220 --> 00:01:49,400
Funkcija bo izpisal hi in izvršitev
rekurzivni klic.

34
00:01:49,400 --> 00:01:53,600
Še en klic funkcije hi s
decremented vhodna vrednost.

35
00:01:53,600 --> 00:01:56,790
>> Sedaj, čeprav smo natisniti hi,
funkcija ne preneha, dokler ne bomo

36
00:01:56,790 --> 00:02:00,370
vrnitev svoje vrste vračanja,
v tem primeru praznini.

37
00:02:00,370 --> 00:02:04,830
Torej za vsak n razen osnovnem scenariju
ta funkcija hi hi bo vrnil

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

39
00:02:06,890 --> 00:02:10,050
Ker je ta funkcija ničen, čeprav smo
ne bo vrnitve izrecno vpišite tukaj.

40
00:02:10,050 --> 00:02:12,000
Mi bomo samo izvršitev funkcije.

41
00:02:12,000 --> 00:02:16,960
Torej kliče hi (3), se natisne in hi
izvršiti hi (2), ki izvaja hi (1) en

42
00:02:16,960 --> 00:02:20,560
ki izvaja hi (0), kjer je
Pogoj osnovna izpolnjen.

43
00:02:20,560 --> 00:02:24,100
Torej, hi (0) natisne adijo in se vrne.

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

45
00:02:24,990 --> 00:02:28,690
Torej sedaj, da smo razumeli osnove
rekurzivne funkcije, ki jih potrebujejo

46
00:02:28,690 --> 00:02:32,730
vsaj ene baze primera, kakor tudi
rekurzivni klic, gremo na

47
00:02:32,730 --> 00:02:34,120
bolj smiselno primer.

48
00:02:34,120 --> 00:02:37,830
Tisti, ki ne samo vrnitev
izničijo ni važno kaj.

49
00:02:37,830 --> 00:02:41,340
>> Oglejmo si na fakulteto
Delovanje uporabljajo najpogosteje v

50
00:02:41,340 --> 00:02:43,660
izračuni verjetnosti.

51
00:02:43,660 --> 00:02:48,120
Fakulteta n je produkt vsak
pozitivno celo število manj kot

52
00:02:48,120 --> 00:02:49,400
in enako n.

53
00:02:49,400 --> 00:02:56,731
Torej faktorski pet je 5 krat 4 krat
3 krat 2-krat 1, da dobimo 120.

54
00:02:56,731 --> 00:03:01,400
Štiri faktorski je 4 krat 3 krat
2-krat 1, da dobimo 24.

55
00:03:01,400 --> 00:03:04,910
In velja enako pravilo
za vsako pozitivno celo število.

56
00:03:04,910 --> 00:03:08,670
>> Torej, kako bi lahko napišemo rekurzivno
Funkcija, ki izračuna fakulteto

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

58
00:03:09,960 --> 00:03:14,700
No, bomo morali opredeliti tako
osnovna in rekurzivni klic.

59
00:03:14,700 --> 00:03:18,250
Rekurzivni klic, bo enaka
v vseh primerih, razen za bazo

60
00:03:18,250 --> 00:03:21,420
primera, kar pomeni, da bomo morali
najti vzorec, ki nam bo dala našim

61
00:03:21,420 --> 00:03:23,350
želeni rezultat.

62
00:03:23,350 --> 00:03:30,270
>> Za ta primer, kako 5 faktorjev
vključuje pomnoži 4 za 3 za 2 za 1

63
00:03:30,270 --> 00:03:33,010
In to zelo isto razmnoževanje
najdemo tod

64
00:03:33,010 --> 00:03:35,430
definicija 4. fakulteto.

65
00:03:35,430 --> 00:03:39,810
Tako vidimo, da je 5 faktorjev
le 5 krat 4 fakulteto.

66
00:03:39,810 --> 00:03:43,360
Zdaj se uporablja ta vzorec
do 4 fakulteto, pa tudi?

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

68
00:03:44,280 --> 00:03:49,120
Vidimo, da je 4. faktorjev vsebuje
množenje 3 krat 2 krat 1,

69
00:03:49,120 --> 00:03:51,590
Zelo enaka opredelitev kot 3 fakulteto.

70
00:03:51,590 --> 00:03:56,950
Torej 4 faktorski je enako 4-krat 3
faktorski, in tako naprej in tako naprej naši

71
00:03:56,950 --> 00:04:02,170
Vzorec palice do 1. fakulteto, ki
po definiciji je enak 1.

72
00:04:02,170 --> 00:04:04,950
>> Ni druge pozitivne
cela levo.

73
00:04:04,950 --> 00:04:07,870
Torej imamo vzorec za
naš rekurzivni klic.

74
00:04:07,870 --> 00:04:13,260
n faktorski je enako n krat
fakulteta n minus 1.

75
00:04:13,260 --> 00:04:14,370
In naša baza primer?

76
00:04:14,370 --> 00:04:17,370
Da bom samo naša definicija
1. fakulteto.

77
00:04:17,370 --> 00:04:19,995
>> Sedaj se lahko premaknemo na pisno
koda za funkcijo.

78
00:04:19,995 --> 00:04:24,110
Pri osnovnem scenariju, bomo morali
pogoj n enak enak 1, kjer je

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

80
00:04:25,780 --> 00:04:29,280
Nato pa se gibljejo na rekurzivnega klica,
bomo vrnili n-krat

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

82
00:04:32,180 --> 00:04:33,590
>> Zdaj pa se preizkusite to naša.

83
00:04:33,590 --> 00:04:35,900
Poskusimo fakulteto 4.

84
00:04:35,900 --> 00:04:39,420
Na našem funkcijo je enaka
do 4-krat faktorski (3).

85
00:04:39,420 --> 00:04:43,040
Faktorski (3) je enak
3-krat faktorski (2).

86
00:04:43,040 --> 00:04:48,700
Faktorski (2) je enak 2 krat
faktorski (1), ki vrne 1.

87
00:04:48,700 --> 00:04:52,490
Faktorski (2) sedaj vrne 2 krat 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktorski (3), lahko sedaj vrnete
3 krat 2, 6.

89
00:04:55,960 --> 00:05:02,490
In končno, faktorski (4)
vrne 4-krat 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Če ste naleteli na težave
z rekurzivnega klica, se pretvarjamo, da

91
00:05:06,780 --> 00:05:09,660
Funkcija deluje že.

92
00:05:09,660 --> 00:05:13,450
Kaj mislim s tem je, da bi morala
zaupajo svoje rekurzivne klice, da se vrnete

93
00:05:13,450 --> 00:05:15,100
prave vrednote.

94
00:05:15,100 --> 00:05:18,960
Na primer, če vem, da je
faktorski (5) je enaka 5-krat

95
00:05:18,960 --> 00:05:24,870
faktorski (4), bom zaupal, da
faktorski (4), mi bo dal 24.

96
00:05:24,870 --> 00:05:28,510
Think of it kot spremenljivko, če
bo, kot če že opredeljena

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

98
00:05:30,070 --> 00:05:33,850
Torej za vsako fakulteto (n), to je
produkt n in

99
00:05:33,850 --> 00:05:35,360
Predhodna fakulteto.

100
00:05:35,360 --> 00:05:38,130
In ta prejšnja fakulteto
dobimo tako, da zahteva

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

102
00:05:41,330 --> 00:05:45,130
>> Zdaj pa poglej, če lahko izvajajo
rekurzivna funkcija sami.

103
00:05:45,130 --> 00:05:50,490
Vstavite vaš terminal, ali run.cs50.net,
in napisati funkcijo SUM

104
00:05:50,490 --> 00:05:54,770
ki traja celo število n in vrne
Vsota vseh zaporedni pozitivni

105
00:05:54,770 --> 00:05:57,490
cela števila od n do 1.

106
00:05:57,490 --> 00:06:01,000
Napisal sem ven vsote nekaterih
Vrednosti, ki vam pomaga naša.

107
00:06:01,000 --> 00:06:04,030
Najprej ugotovimo,
Pogoj osnovna.

108
00:06:04,030 --> 00:06:06,170
Potem, poglej vsoto (5).

109
00:06:06,170 --> 00:06:09,270
Lahko si ga izraziti
druge vsote?

110
00:06:09,270 --> 00:06:11,290
Zdaj, kaj pa vsota (4)?

111
00:06:11,290 --> 00:06:15,630
Kako lahko izrazite vsoto (4)
V smislu drugega vsote?

112
00:06:15,630 --> 00:06:19,655
>> Ko imate vsoto (5) in vsota (4)
izražene v drugih zneskov, glej

113
00:06:19,655 --> 00:06:22,970
če se lahko opredelijo
Vzorec za vsoto (n).

114
00:06:22,970 --> 00:06:26,190
Če ni, poskusite nekaj drugih številk
in izrazijo svoje zneske

115
00:06:26,190 --> 00:06:28,410
Pogoji nadaljnjih številk.

116
00:06:28,410 --> 00:06:31,930
S prepoznavanjem vzorcev za diskretnih
številke, ste na dobri poti, da

117
00:06:31,930 --> 00:06:34,320
identifikacijo vzorec za vsak n.

118
00:06:34,320 --> 00:06:38,040
>> Rekurzija je zelo močno orodje,
Tako seveda ni omejen samo na

119
00:06:38,040 --> 00:06:39,820
matematične funkcije.

120
00:06:39,820 --> 00:06:44,040
Rekurzija se lahko zelo učinkovito uporablja
ko se ukvarjajo z drevesi, na primer.

121
00:06:44,040 --> 00:06:47,210
Oglejte si kratko o drevesih
bolj temeljit pregled, vendar za zdaj

122
00:06:47,210 --> 00:06:51,140
opozarjajo, da binarnih iskalnih dreves, v
Zlasti so sestavljeni iz vozlišč, vsak

123
00:06:51,140 --> 00:06:53,820
z vrednostjo in dveh vozlišč kazalcev.

124
00:06:53,820 --> 00:06:57,270
Ponavadi je to zastopa
nadrejeno vozlišče, ki ima eno vrstico kazanje

125
00:06:57,270 --> 00:07:01,870
na levo vozlišča in eno
na desni vozlišča.

126
00:07:01,870 --> 00:07:04,510
Strukturo binarnega iskanja
Drevo je zelo primerna tudi

127
00:07:04,510 --> 00:07:05,940
na rekurzivnega iskanja.

128
00:07:05,940 --> 00:07:09,730
Rekurzivni klic, bodisi prehaja v
levo ali desno vozlišče, ampak bolj

129
00:07:09,730 --> 00:07:10,950
od tega v drevo kratkega stika.

130
00:07:10,950 --> 00:07:15,690
>> Da želite izvesti operacijo na
vsak vozlišče v binarnem drevesu.

131
00:07:15,690 --> 00:07:17,410
Kako lahko greste o tem?

132
00:07:17,410 --> 00:07:20,600
No, lahko napišete rekurzivno
Funkcija, ki izvaja operacijo

133
00:07:20,600 --> 00:07:24,450
na starša in naredi rekurzivno
klic na isto funkcijo,

134
00:07:24,450 --> 00:07:27,630
poteka v levo in
pravica otrok vozlišča.

135
00:07:27,630 --> 00:07:31,650
Na primer, ta funkcija, foo, da
spremeni vrednost danega vozlišča in

136
00:07:31,650 --> 00:07:33,830
vsi njeni otroci do 1.

137
00:07:33,830 --> 00:07:37,400
Osnova primeru ničelnih vozlišču vzrokov
Funkcija za vrnitev, kar pomeni,

138
00:07:37,400 --> 00:07:41,290
da ni vsa vozlišča
ostane v tem sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Sprehodimo se skozi to.

140
00:07:42,620 --> 00:07:44,340
Prvi staršev je 13.

141
00:07:44,340 --> 00:07:47,930
Spremenimo vrednost na 1, nato pa pokličite
Naša funkcija na levi kot tudi

142
00:07:47,930 --> 00:07:49,600
kot je prav.

143
00:07:49,600 --> 00:07:53,910
Funkcija, foo, se imenuje na levi
sub-tree prvi, tako levi vozlišče

144
00:07:53,910 --> 00:07:57,730
bo premeščen na 1. in foo bo
se imenuje za otroke, ki vozlišča,

145
00:07:57,730 --> 00:08:01,900
najprej levo in nato desno
in tako naprej in tako naprej.

146
00:08:01,900 --> 00:08:05,630
In jim povedal, da jim podružnice nimajo
več otrok tako enak postopek

147
00:08:05,630 --> 00:08:09,700
bo še za pravico otrok
dokler so vozlišča celemu drevesa

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

149
00:08:11,430 --> 00:08:15,390
>> Kot lahko vidite, niste omejeni
samo en rekurzivni klic.

150
00:08:15,390 --> 00:08:17,930
Ravno toliko, kot bo dobil delo opravljeno.

151
00:08:17,930 --> 00:08:21,200
Kaj če bi imeli na drevo, kjer je vsak
vozlišče imela tri otroke,

152
00:08:21,200 --> 00:08:23,100
Levi, srednji in desni?

153
00:08:23,100 --> 00:08:24,886
Kako bi vi uredite foo?

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

155
00:08:25,860 --> 00:08:30,250
Dodajte še en rekurzivni klic in
prenese na kazalec srednji vozlišča.

156
00:08:30,250 --> 00:08:34,549
>> Rekurzija je zelo močna in da ne
portalu elegantno, vendar je lahko

157
00:08:34,549 --> 00:08:38,010
zapleten pojem na prvi, zato bodite
bolnika in si vzemite čas.

158
00:08:38,010 --> 00:08:39,370
Začnite z osnovnim scenarijem.

159
00:08:39,370 --> 00:08:42,650
To je običajno najlažje ugotoviti,
in potem si lahko delo

160
00:08:42,650 --> 00:08:43,830
nazaj od tam.

161
00:08:43,830 --> 00:08:46,190
Saj veš, kar potrebujete, da bi dosegli svoj
referenčnem primeru, tako da bi

162
00:08:46,190 --> 00:08:47,760
vam nekaj namigov.

163
00:08:47,760 --> 00:08:53,120
Poskusi, da izrazi en poseben primer v
Pogoji ostalih primerih ali v pod-sklopov.

164
00:08:53,120 --> 00:08:54,700
>> Hvala za gledanje ta kratko.

165
00:08:54,700 --> 00:08:58,920
Vsaj, sedaj lahko
razumejo šale, kot je ta.

166
00:08:58,920 --> 00:09:01,250
Ime je Zamyla, in to je CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Vzemite to funkcijo, hi,
void funkcija, ki traja

169
00:09:07,170 --> 00:09:09,212
int n, kot vhod.

170
00:09:09,212 --> 00:09:11,020
Osnovna na prvem mestu.

171
00:09:11,020 --> 00:09:14,240
Če je n manj kot 0, tiskanje
"Adijo" in povratka.

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