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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Abychom pochopili,
rekurze, musíte

3
00:00:10,190 --> 00:00:13,820
nejprve pochopit rekurzi.

4
00:00:13,820 --> 00:00:17,280
S rekurzi v návrhu programu prostřednictvím
že máte sebereferenční

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

6
00:00:18,570 --> 00:00:21,520
Rekurzivní datové struktury, například,
jsou datové struktury, které

7
00:00:21,520 --> 00:00:23,990
zahrnují se do
jejich definice.

8
00:00:23,990 --> 00:00:27,160
Ale dnes, budeme se soustředit
na rekurzivních funkcí.

9
00:00:27,160 --> 00:00:31,160
>> Připomeňme, že funkce se vstupy,
argumenty a vrátí hodnotu jako jejich

10
00:00:31,160 --> 00:00:34,480
Výstup zastoupené
Tento diagram zde.

11
00:00:34,480 --> 00:00:38,060
Budeme přemýšlet z krabice jako orgán
funkce, která obsahuje soubor

12
00:00:38,060 --> 00:00:42,340
pokyny, které interpretují
vstup a poskytovat výstup.

13
00:00:42,340 --> 00:00:45,660
Při bližším pohledu uvnitř těla
funkce může odhalit volání

14
00:00:45,660 --> 00:00:47,430
další funkce stejně.

15
00:00:47,430 --> 00:00:51,300
Vezměte si tuto jednoduchou funkci, foo, že
trvá jeden řetězec jako vstup a

16
00:00:51,300 --> 00:00:54,630
vytiskne, kolik písmen
že řetězec má.

17
00:00:54,630 --> 00:00:58,490
Funkce strlen, pro délku řetězce,
se nazývá, jehož výstup je

18
00:00:58,490 --> 00:01:01,890
potřebné pro volání printf.

19
00:01:01,890 --> 00:01:05,770
>> A teď, co je rekurzivní funkce
Zvláštní je, že volá sama sebe.

20
00:01:05,770 --> 00:01:09,610
Můžeme reprezentovat tuto rekurzivní
volání s touto oranžovou šipkou

21
00:01:09,610 --> 00:01:11,360
looping zpět k sobě.

22
00:01:11,360 --> 00:01:15,630
Ale pouze se znovu spuštěním bude
provést další rekurzivní volání, a

23
00:01:15,630 --> 00:01:17,150
další a další.

24
00:01:17,150 --> 00:01:19,100
Ale rekurzivní funkce
nemůže být nekonečný.

25
00:01:19,100 --> 00:01:23,490
Musí skončit nějakým způsobem, nebo vaše
Program poběží navždy.

26
00:01:23,490 --> 00:01:27,680
>> Takže musíme najít způsob, jak zlomit
z rekurzivních volání.

27
00:01:27,680 --> 00:01:29,900
Říkáme tomu referenční případ.

28
00:01:29,900 --> 00:01:33,570
Je-li splněna základní podmínka případ,
Funkce vrací, aniž by

29
00:01:33,570 --> 00:01:34,950
další rekurzivní volání.

30
00:01:34,950 --> 00:01:39,610
Vezměte si tuto funkci, hi, funkci void
že trvá int n jako vstup.

31
00:01:39,610 --> 00:01:41,260
Referenční případ nastane dříve.

32
00:01:41,260 --> 00:01:46,220
Pokud n je menší než nula, tisk bye a
návrat Ve všech ostatních případech,

33
00:01:46,220 --> 00:01:49,400
Funkce vytiskne hi a provést
rekurzivní volání.

34
00:01:49,400 --> 00:01:53,600
Další volání funkce hi se
sníží vstupní hodnota.

35
00:01:53,600 --> 00:01:56,790
>> Nyní, i když jsme vytisknout hi,
funkce se neukončí, dokud se

36
00:01:56,790 --> 00:02:00,370
vrátí jeho návratový typ,
v tomto případě prázdnotě.

37
00:02:00,370 --> 00:02:04,830
Takže pro každé n jiné než základní věci,
tato funkce hi vrátí hi

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

39
00:02:06,890 --> 00:02:10,050
Protože tato funkce je neplatné i když jsme
nebude výslovně napište sem vracet.

40
00:02:10,050 --> 00:02:12,000
Budeme jen spustit funkci.

41
00:02:12,000 --> 00:02:16,960
Takže volání hi (3) bude tisknout hi a
spustit hi (2), který vykonává hi (1) jeden

42
00:02:16,960 --> 00:02:20,560
který vykonává hi (0), kde
referenční případ, podmínka je splněna.

43
00:02:20,560 --> 00:02:24,100
Takže ahoj (0) vytiskne bye a vrátí se.

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

45
00:02:24,990 --> 00:02:28,690
Takže teď, že jsme pochopili základy
rekurzivní funkce, které potřebují

46
00:02:28,690 --> 00:02:32,730
alespoň jeden referenční případ, jakož i
rekurzivní volání, pojďme se přesunout na

47
00:02:32,730 --> 00:02:34,120
více smysluplné příklad.

48
00:02:34,120 --> 00:02:37,830
Jeden, který není jen návrat
ztrátu bez ohledu na to, co.

49
00:02:37,830 --> 00:02:41,340
>> Pojďme se podívat na faktoriálu
Provoz používá nejčastěji v

50
00:02:41,340 --> 00:02:43,660
pravděpodobnostní výpočty.

51
00:02:43,660 --> 00:02:48,120
Faktoriál n je součin každý
kladné celé číslo menší než

52
00:02:48,120 --> 00:02:49,400
a rovná se n.

53
00:02:49,400 --> 00:02:56,731
Takže faktoriál pět je 5 krát 4 krát
3 krát 2 krát 1, čímž se získá 120.

54
00:02:56,731 --> 00:03:01,400
Čtyři faktoriál je 4 krát 3 krát
2 krát 1 za vzniku 24.

55
00:03:01,400 --> 00:03:04,910
A platí stejné pravidlo
na jakékoli kladné číslo.

56
00:03:04,910 --> 00:03:08,670
>> Takže, jak můžeme napsat rekurzivní
funkce, která vypočítá faktoriál

57
00:03:08,670 --> 00:03:09,960
z řady?

58
00:03:09,960 --> 00:03:14,700
No, budeme muset zjistit jak
referenční případ, a rekurzivní volání.

59
00:03:14,700 --> 00:03:18,250
Rekurzivní volání bude stejný
pro všechny případy s výjimkou základny

60
00:03:18,250 --> 00:03:21,420
případ, což znamená, že budeme muset
najít model, který vám dá nám naše

61
00:03:21,420 --> 00:03:23,350
požadovaný výsledek.

62
00:03:23,350 --> 00:03:30,270
>> V tomto příkladu je vidět, jak 5 faktoriál
zahrnuje násobení 4 na 3 o 2 o 1

63
00:03:30,270 --> 00:03:33,010
A to samý násobení
je zde,

64
00:03:33,010 --> 00:03:35,430
Definice 4. faktoriálu.

65
00:03:35,430 --> 00:03:39,810
Takže vidíme, že 5 faktoriál je
jen 5 krát 4 faktoriál.

66
00:03:39,810 --> 00:03:43,360
Nyní se platí tento vzorec
až 4 faktoriál i?

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

68
00:03:44,280 --> 00:03:49,120
Vidíme, že 4 faktoriál obsahuje
násobení 3 krát 2 krát 1,

69
00:03:49,120 --> 00:03:51,590
velmi stejná definice jako 3 faktoriálu.

70
00:03:51,590 --> 00:03:56,950
Takže 4 faktoriál se rovná 4 krát 3
faktoriál, a tak dále a tak dále naše

71
00:03:56,950 --> 00:04:02,170
vzor tyčinky do 1 faktoriálu, který
podle definice je roven 1.

72
00:04:02,170 --> 00:04:04,950
>> Neexistuje žádný další pozitivní
vlevo celá čísla.

73
00:04:04,950 --> 00:04:07,870
Takže máme vzor pro
naše rekurzivní volání.

74
00:04:07,870 --> 00:04:13,260
n faktoriál se rovná n krát
faktoriál n minus 1.

75
00:04:13,260 --> 00:04:14,370
A náš základní scénář?

76
00:04:14,370 --> 00:04:17,370
Bude to jen naše definice
1 faktoriálu.

77
00:04:17,370 --> 00:04:19,995
>> Takže teď můžeme přejít k psaní
kód funkce.

78
00:04:19,995 --> 00:04:24,110
Pro základní případ, budeme mít
stav n se rovná rovná 1, kde

79
00:04:24,110 --> 00:04:25,780
vrátíme 1.

80
00:04:25,780 --> 00:04:29,280
Pak se pohybuje na rekurzivní volání,
vrátíme n-krát

81
00:04:29,280 --> 00:04:32,180
faktoriál n minus 1.

82
00:04:32,180 --> 00:04:33,590
>> Nyní pojďme vyzkoušet tuto dotazy.

83
00:04:33,590 --> 00:04:35,900
Zkusme faktoriál 4.

84
00:04:35,900 --> 00:04:39,420
Na naší funkce je rovna
se 4 krát faktoriál (3).

85
00:04:39,420 --> 00:04:43,040
Faktoriál (3) je rovna
3 krát faktoriál (2).

86
00:04:43,040 --> 00:04:48,700
Faktoriál (2) je rovna 2 krát
faktoriál (1), která vrací 1.

87
00:04:48,700 --> 00:04:52,490
Faktoriál (2) se vrací 2 krát 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktoriál (3), mohou nyní vrátit
3 x 2, 6.

89
00:04:55,960 --> 00:05:02,490
A konečně, faktoriál (4)
vrátí 4x 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Pokud jste narazila na problémy
s rekurzivní volání, předstírat, že

91
00:05:06,780 --> 00:05:09,660
funkce pracuje již.

92
00:05:09,660 --> 00:05:13,450
Co tím chci říct je to, že byste měli
věřit svým rekurzivní volání k návratu

93
00:05:13,450 --> 00:05:15,100
správné hodnoty.

94
00:05:15,100 --> 00:05:18,960
Například, když vím, že
faktoriál (5) se rovná 5 krát

95
00:05:18,960 --> 00:05:24,870
faktoriál (4), budu věřit, že
faktoriál (4) bude mi 24..

96
00:05:24,870 --> 00:05:28,510
Ber to jako proměnnou, pokud
bude, jako byste již definován

97
00:05:28,510 --> 00:05:30,070
faktoriál (4).

98
00:05:30,070 --> 00:05:33,850
Takže pro jakékoliv faktoriál (n), je to
produkt z n a

99
00:05:33,850 --> 00:05:35,360
předchozí faktoriál.

100
00:05:35,360 --> 00:05:38,130
A to předchozí faktoriál
se získá voláním

101
00:05:38,130 --> 00:05:41,330
faktoriál n minus 1.

102
00:05:41,330 --> 00:05:45,130
>> Teď uvidíme, jestli můžete implementovat
rekurzivní funkce sami.

103
00:05:45,130 --> 00:05:50,490
Vložte svůj terminál, nebo run.cs50.net,
a napsat funkci částku

104
00:05:50,490 --> 00:05:54,770
že má celočíselnou n a vrátí
součet všech po sobě jdoucích pozitivní

105
00:05:54,770 --> 00:05:57,490
celá čísla od N do 1..

106
00:05:57,490 --> 00:06:01,000
Napsal jsem z částky některých
Hodnoty, které vám pomohou naše.

107
00:06:01,000 --> 00:06:04,030
Za prvé, zjistit,
base case stav.

108
00:06:04,030 --> 00:06:06,170
Pak se podívejte na součtu (5).

109
00:06:06,170 --> 00:06:09,270
Můžete to vyjádřit v rámci
jiné částky?

110
00:06:09,270 --> 00:06:11,290
A teď, co součet (4)?

111
00:06:11,290 --> 00:06:15,630
Jak můžete vyjádřit součet (4)
, pokud jde o jiné částky?

112
00:06:15,630 --> 00:06:19,655
>> Jakmile budete mít součet (5) a součtem (4)
vyjádřeno v jiné částky, viz

113
00:06:19,655 --> 00:06:22,970
pokud můžete identifikovat
vzor pro součet (n).

114
00:06:22,970 --> 00:06:26,190
Pokud ne, zkuste několik dalších čísel
a vyjádřit své částky v

115
00:06:26,190 --> 00:06:28,410
podmínky dalších čísel.

116
00:06:28,410 --> 00:06:31,930
Tím, že pozná vzory pro diskrétní
čísla, jste na dobré cestě k

117
00:06:31,930 --> 00:06:34,320
identifikaci vzor pro libovolné n.

118
00:06:34,320 --> 00:06:38,040
>> Rekurze je opravdu mocný nástroj,
tak samozřejmě, že to není omezeno na

119
00:06:38,040 --> 00:06:39,820
matematické funkce.

120
00:06:39,820 --> 00:06:44,040
Rekurze může být velmi efektivně využity
pokud se jedná o stromy na instanci.

121
00:06:44,040 --> 00:06:47,210
Podívejte se na krátký na stromy pro
důkladnější přezkum, ale pro tuto chvíli

122
00:06:47,210 --> 00:06:51,140
připomenout, že binární vyhledávací stromy, v
zejména, jsou vyrobeny z uzlů, z nichž každý

123
00:06:51,140 --> 00:06:53,820
s hodnotou a dvou uzlů ukazatele.

124
00:06:53,820 --> 00:06:57,270
Obvykle to představuje
nadřazený uzel má jeden řádek bodování

125
00:06:57,270 --> 00:07:01,870
do uzlu levé dítě a jeden
na pravé podřízený uzel.

126
00:07:01,870 --> 00:07:04,510
Struktura binární vyhledávání
strom půjčuje sebe dobře

127
00:07:04,510 --> 00:07:05,940
na rekurzivní vyhledávání.

128
00:07:05,940 --> 00:07:09,730
Rekurzivní volání buď projde
levý nebo pravý uzel, ale více

129
00:07:09,730 --> 00:07:10,950
z toho stromu zkratu.

130
00:07:10,950 --> 00:07:15,690
>> Řekněme, že chcete provést operaci
každý uzel v binárním stromu.

131
00:07:15,690 --> 00:07:17,410
Jak byste mohli jít na to?

132
00:07:17,410 --> 00:07:20,600
No, mohl bys napsat rekurzivní
funkce, která provádí operace

133
00:07:20,600 --> 00:07:24,450
Na nadřazeného uzlu a je rekurzivní
volat na stejnou funkci,

134
00:07:24,450 --> 00:07:27,630
procházející v levém a
právo podřízené uzly.

135
00:07:27,630 --> 00:07:31,650
Například, tato funkce foo, že
změní hodnotu daného uzlu a

136
00:07:31,650 --> 00:07:33,830
všechny své děti do 1.

137
00:07:33,830 --> 00:07:37,400
Referenční případ, z Null uzel příčin
funkce vrátit, což znamená,

138
00:07:37,400 --> 00:07:41,290
, že zde nejsou žádné uzly
odešel v tomto podstromu.

139
00:07:41,290 --> 00:07:42,620
>> Pojďme si projít to.

140
00:07:42,620 --> 00:07:44,340
První rodič je 13.

141
00:07:44,340 --> 00:07:47,930
Změníme hodnotu 1, a pak volat
naše funkce na levé straně, jakož

142
00:07:47,930 --> 00:07:49,600
jako pravé.

143
00:07:49,600 --> 00:07:53,910
Funkce foo, se nazývá nalevo
sub-tree první, tak levý uzel

144
00:07:53,910 --> 00:07:57,730
bude přidělen 1 a foo bude
být volán na děti, které nodu,

145
00:07:57,730 --> 00:08:01,900
první vlevo a pak vpravo,
a tak dále a tak dále.

146
00:08:01,900 --> 00:08:05,630
A řekněte jim, že pobočky nemají
každá další děti, takže stejný proces

147
00:08:05,630 --> 00:08:09,700
bude pokračovat správným děti
dokud uzly celého stromu jsou

148
00:08:09,700 --> 00:08:11,430
převelen k 1..

149
00:08:11,430 --> 00:08:15,390
>> Jak můžete vidět, nejste omezeni
jen jeden rekurzivní volání.

150
00:08:15,390 --> 00:08:17,930
Stejně jako mnoho, jak se dostat práci.

151
00:08:17,930 --> 00:08:21,200
Co kdyby jste měli na strom, kde každý
Uzel měl tři děti,

152
00:08:21,200 --> 00:08:23,100
Levá, střední a pravá?

153
00:08:23,100 --> 00:08:24,886
Jak byste upravit foo?

154
00:08:24,886 --> 00:08:25,860
No, jednoduše.

155
00:08:25,860 --> 00:08:30,250
Stačí přidat další rekurzivní volání a
předat ukazatel na střed uzlu.

156
00:08:30,250 --> 00:08:34,549
>> Rekurze je velmi silný, a ne
zmínit, elegantní, ale to může být

157
00:08:34,549 --> 00:08:38,010
obtížné koncept na první, tak se
pacienta a vzít si na čas.

158
00:08:38,010 --> 00:08:39,370
Začněte se základním případu.

159
00:08:39,370 --> 00:08:42,650
Je to obvykle nejjednodušší určit,
a pak můžete pracovat

160
00:08:42,650 --> 00:08:43,830
zpět odtamtud.

161
00:08:43,830 --> 00:08:46,190
Víte, že je třeba dosáhnout svého
referenční případ, takže síla

162
00:08:46,190 --> 00:08:47,760
vám několik rad.

163
00:08:47,760 --> 00:08:53,120
Pokuste se vyjádřit jeden konkrétní případ
podmínky ostatních případech, nebo v dílčích sadách.

164
00:08:53,120 --> 00:08:54,700
>> Díky za sledování této krátké.

165
00:08:54,700 --> 00:08:58,920
Přinejmenším, nyní můžete
pochopit, vtipy, jako je tento.

166
00:08:58,920 --> 00:09:01,250
Jmenuji se Zamyla, a to je CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Vezměte si tuto funkci, hi,
void funkce, která vezme

169
00:09:07,170 --> 00:09:09,212
int, n, jako vstup.

170
00:09:09,212 --> 00:09:11,020
Referenční případ nastane dříve.

171
00:09:11,020 --> 00:09:14,240
Pokud n je menší než 0, tisk
"Na shledanou" a návrat.

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