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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Ahhoz, hogy megértsük
rekurzió, meg kell

3
00:00:10,190 --> 00:00:13,820
először megérteni, rekurzió.

4
00:00:13,820 --> 00:00:17,280
Miután rekurziót program tervezése eszközök
hogy van ön-referenciális

5
00:00:17,280 --> 00:00:18,570
definíciók.

6
00:00:18,570 --> 00:00:21,520
Rekurzív adatstruktúrák, például,
olyan adat struktúrák

7
00:00:21,520 --> 00:00:23,990
közé magukat
a definíciók.

8
00:00:23,990 --> 00:00:27,160
De ma fogunk összpontosítani
A rekurzív függvények.

9
00:00:27,160 --> 00:00:31,160
>> Emlékezzünk vissza, hogy működik, hogy bemenet,
érveket, és vissza értéket, mint a

10
00:00:31,160 --> 00:00:34,480
kimenet által képviselt
ez a rajz itt.

11
00:00:34,480 --> 00:00:38,060
Majd kitalálunk a doboz, mint a test
a funkciót, amely tartalmazza a készlet

12
00:00:38,060 --> 00:00:42,340
utasításokat, hogy értelmezze a
bemeneti, és kimeneti.

13
00:00:42,340 --> 00:00:45,660
A kezelés ideje alatt egy közelebbi pillantást a testben
A funkció fedhet hívások

14
00:00:45,660 --> 00:00:47,430
más funkciókat is.

15
00:00:47,430 --> 00:00:51,300
Vegyük ezt az egyszerű funkciót, ize, hogy
vesz egy string bemeneti és

16
00:00:51,300 --> 00:00:54,630
kiírja, hogy hány betű
hogy a húr van.

17
00:00:54,630 --> 00:00:58,490
A funkció strlen, string hossza,
nevezik, melynek kimenete

18
00:00:58,490 --> 00:01:01,890
szükséges a hívás printf.

19
00:01:01,890 --> 00:01:05,770
>> Most, mitől lesz egy rekurzív függvény
különös az, hogy saját magát hívja meg.

20
00:01:05,770 --> 00:01:09,610
Mi is képviseli ezt a rekurzív
hívják ezt a narancs nyíl

21
00:01:09,610 --> 00:01:11,360
hurok vissza önmagához.

22
00:01:11,360 --> 00:01:15,630
De végrehajtása magát újra csak akkor
újabb rekurzív hívást, és

23
00:01:15,630 --> 00:01:17,150
egy másik, és egy másik.

24
00:01:17,150 --> 00:01:19,100
De a rekurzív függvények
nem lehet végtelen.

25
00:01:19,100 --> 00:01:23,490
Ők a végére valahogy, vagy a
a program fog örökké.

26
00:01:23,490 --> 00:01:27,680
>> Tehát meg kell találni a módját, hogy megtörje
ki a rekurzív hívások.

27
00:01:27,680 --> 00:01:29,900
Ezt nevezzük az alapeset.

28
00:01:29,900 --> 00:01:33,570
Amikor az alapeset feltétel teljesül,
A függvény nélkül

29
00:01:33,570 --> 00:01:34,950
egy rekurzív hívást.

30
00:01:34,950 --> 00:01:39,610
Vegyük ezt a funkciót, hi, void függvény
hogy vesz egy int n, mint bemenet.

31
00:01:39,610 --> 00:01:41,260
Az alapeset az első.

32
00:01:41,260 --> 00:01:46,220
Ha n kisebb, mint nulla, nyomtatási szia és
Cserébe minden más esetben, a

33
00:01:46,220 --> 00:01:49,400
funkció kiírja hi és végrehajtási
a rekurzív hívás.

34
00:01:49,400 --> 00:01:53,600
Egy másik függvény hívása hi-vel
A csökkenhet bemeneti értéket.

35
00:01:53,600 --> 00:01:56,790
>> Most, még akkor is nyomtatni hi, a
funkció nem szünteti meg, amíg meg nem

36
00:01:56,790 --> 00:02:00,370
vissza a visszatérési típus,
ebben az esetben érvénytelen.

37
00:02:00,370 --> 00:02:04,830
Így minden n kívüli alapeset,
ez a funkció hi visszatér hi

38
00:02:04,830 --> 00:02:06,890
n mínusz 1.

39
00:02:06,890 --> 00:02:10,050
Mivel ez a funkció érvénytelen mégis, akkor
nem kifejezetten írja térjen ide vissza.

40
00:02:10,050 --> 00:02:12,000
Majd csak futtasd a funkciót.

41
00:02:12,000 --> 00:02:16,960
Így hívás hi (3) nyomtatja hi és
végre hi (2), amely végrehajtja a hi (1) egy

42
00:02:16,960 --> 00:02:20,560
amely végrehajtja a hi (0), ahol a
alapeset feltétel teljesül.

43
00:02:20,560 --> 00:02:24,100
Tehát hi (0) nyomtat szia és visszatér.

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

45
00:02:24,990 --> 00:02:28,690
Tehát most, hogy megértjük az alapjait
rekurzív függvények, hogy szükség van

46
00:02:28,690 --> 00:02:32,730
legalább egy bázis esetében, valamint egy
rekurzív hívás, menjünk tovább, hogy a

47
00:02:32,730 --> 00:02:34,120
több értelmes példa.

48
00:02:34,120 --> 00:02:37,830
Az egyik, hogy nem csak vissza
elvesztésével nem számít, mit.

49
00:02:37,830 --> 00:02:41,340
>> Vessünk egy pillantást a faktoriális
működés használják leggyakrabban

50
00:02:41,340 --> 00:02:43,660
valószínűség számítás.

51
00:02:43,660 --> 00:02:48,120
Faktoriális n a termék minden
pozitív egész szám kisebb, mint

52
00:02:48,120 --> 00:02:49,400
és egyenlő n.

53
00:02:49,400 --> 00:02:56,731
Tehát faktoriális öt 5-ször 4-szer
3-szor 2-szer 1, hogy 120.

54
00:02:56,731 --> 00:03:01,400
Four faktoriális 4-szer 3-szor
2-szer 1, így 24.

55
00:03:01,400 --> 00:03:04,910
És ugyanaz a szabály vonatkozik
bármilyen pozitív egész szám.

56
00:03:04,910 --> 00:03:08,670
>> Szóval, hogyan lehet, hogy írunk egy rekurzív
funkció, amely kiszámítja a faktoriális

57
00:03:08,670 --> 00:03:09,960
a szám?

58
00:03:09,960 --> 00:03:14,700
Nos, akkor meg kell határozni azokat mind a
alapeset a rekurzív hívást.

59
00:03:14,700 --> 00:03:18,250
A rekurzív hívás ugyanaz lesz
minden esetben, kivéve a bázis

60
00:03:18,250 --> 00:03:21,420
eset, ami azt jelenti, hogy meg kell
találni egy mintát, hogy megadja nekünk a

61
00:03:21,420 --> 00:03:23,350
kívánt eredményt.

62
00:03:23,350 --> 00:03:30,270
>> Ebben a példában, hogyan 5 faktoriális
magában megszorozzuk 4 3 2 1

63
00:03:30,270 --> 00:03:33,010
És, hogy ugyanazon a szorzás
itt található, a

64
00:03:33,010 --> 00:03:35,430
meghatározása 4. faktoriális.

65
00:03:35,430 --> 00:03:39,810
Tehát azt látjuk, hogy 5 faktoriális van
mindössze 5-ször 4 faktoriális.

66
00:03:39,810 --> 00:03:43,360
Most azonban ez a minta vonatkozik
4 faktoriális is?

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

68
00:03:44,280 --> 00:03:49,120
Látjuk, hogy a 4 faktoriális tartalmazó
szorzás 3-szor 2-szer 1, akkor a

69
00:03:49,120 --> 00:03:51,590
ugyanazon definíció 3. faktoriális.

70
00:03:51,590 --> 00:03:56,950
Tehát 4 faktoriális egyenlő 3-4-szer
faktoriális, és így tovább és így tovább a mi

71
00:03:56,950 --> 00:04:02,170
minta tapad 1-ig faktoriális, amely
definíció szerint egyenlő 1-gyel.

72
00:04:02,170 --> 00:04:04,950
>> Nincs más pozitív
egész maradt.

73
00:04:04,950 --> 00:04:07,870
Tehát a mintát
a rekurzív hívás.

74
00:04:07,870 --> 00:04:13,260
n faktoriális egyenlő n-szer
A faktoriális n mínusz 1.

75
00:04:13,260 --> 00:04:14,370
És a alapeset?

76
00:04:14,370 --> 00:04:17,370
Ez majd csak a definíció
1 faktoriális.

77
00:04:17,370 --> 00:04:19,995
>> Így most már lépni írás
kódot a funkciót.

78
00:04:19,995 --> 00:04:24,110
Az alapeset, mi lesz a
n értéke feltétel egyenlők 1, ahol

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

80
00:04:25,780 --> 00:04:29,280
Ezután mozgó rá a rekurzív hívás,
visszafizetjük n-szer a

81
00:04:29,280 --> 00:04:32,180
faktoriális n mínusz 1.

82
00:04:32,180 --> 00:04:33,590
>> Most teszteljük ezt a.

83
00:04:33,590 --> 00:04:35,900
Próbáljuk faktoriális 4..

84
00:04:35,900 --> 00:04:39,420
Per a funkció, hogy ez egyenlő
-4-szer faktoriális (3).

85
00:04:39,420 --> 00:04:43,040
Faktoriális (3) egyenlő
3 alkalommal faktoriális (2).

86
00:04:43,040 --> 00:04:48,700
Faktoriális (2) egyenlő 2-szer
faktoriális (1), amely visszaadja 1..

87
00:04:48,700 --> 00:04:52,490
Faktoriális (2) most visszatér 2-szer 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktoriális (3) most visszatér
3-szor 2 6.

89
00:04:55,960 --> 00:05:02,490
És végül, faktoriális (4)
4-szer visszatér 6., 24..

90
00:05:02,490 --> 00:05:06,780
>> Ha találkozik bármilyen nehézség
a rekurzív hívás, úgy, mintha

91
00:05:06,780 --> 00:05:09,660
A funkció már.

92
00:05:09,660 --> 00:05:13,450
Mit jelent ez, hogy meg kell
bízni a rekurzív hívások vissza

93
00:05:13,450 --> 00:05:15,100
a megfelelő értékeket.

94
00:05:15,100 --> 00:05:18,960
Például, ha tudom, hogy
faktoriális (5) értéke 5-ször

95
00:05:18,960 --> 00:05:24,870
faktoriális (4), fogok benne, hogy
faktoriális (4) ad nekem 24.

96
00:05:24,870 --> 00:05:28,510
Gondold azt, hogy egy változó, ha
lesz, mintha már definiált

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

98
00:05:30,070 --> 00:05:33,850
Így minden faktoros (n), akkor
a termék-és n

99
00:05:33,850 --> 00:05:35,360
Az előző faktoriális.

100
00:05:35,360 --> 00:05:38,130
És ez az előző factorial
kapjuk meghívásával

101
00:05:38,130 --> 00:05:41,330
faktoriális n mínusz 1.

102
00:05:41,330 --> 00:05:45,130
>> Most nézd meg, hogy végre egy
rekurzív függvény magad.

103
00:05:45,130 --> 00:05:50,490
Töltse fel a terminál, vagy run.cs50.net,
és írni egy függvény összeget

104
00:05:50,490 --> 00:05:54,770
hogy vesz egy n egész számot, és visszaadja a
összessége egymást követő pozitív

105
00:05:54,770 --> 00:05:57,490
egész n 1-re.

106
00:05:57,490 --> 00:06:01,000
Én írtam ki az összegeket néhány
értékeket, hogy segítsen a.

107
00:06:01,000 --> 00:06:04,030
Először is, kitalálni a
alapeset állapotban.

108
00:06:04,030 --> 00:06:06,170
Aztán nézd meg az összeget (5).

109
00:06:06,170 --> 00:06:09,270
Tudod kifejezni, hogy mind
egy másik összeget?

110
00:06:09,270 --> 00:06:11,290
Nos, mi a helyzet az összeget (4)?

111
00:06:11,290 --> 00:06:15,630
Hogyan lehet kifejezni sum (4)
szempontjából egy másik összeget?

112
00:06:15,630 --> 00:06:19,655
>> Miután sum (5) és összege (4)
kifejezett egyéb kifizetést, lásd

113
00:06:19,655 --> 00:06:22,970
ha tudod azonosítani a
mintát összeg (n).

114
00:06:22,970 --> 00:06:26,190
Ha nem, néhány más számot
és kifejezni összegekkel

115
00:06:26,190 --> 00:06:28,410
szempontjából egy másik számot.

116
00:06:28,410 --> 00:06:31,930
Azonosításával minták diszkrét
számokat, akkor is az utat, hogy

117
00:06:31,930 --> 00:06:34,320
azonosítja a minta minden n.

118
00:06:34,320 --> 00:06:38,040
>> Rekurzió egy nagyon hatékony eszköz,
így természetesen ez nem csak a

119
00:06:38,040 --> 00:06:39,820
matematikai funkciókat.

120
00:06:39,820 --> 00:06:44,040
Rekurzió használható nagyon hatékonyan
kezelése során fákat például.

121
00:06:44,040 --> 00:06:47,210
Nézze meg a rövid a fák a
alaposabb áttekintését, de most

122
00:06:47,210 --> 00:06:51,140
Emlékeztetünk arra, hogy bináris keresés fák, a
Különösen, alkotják a csomópontok, amelyek mindegyike

123
00:06:51,140 --> 00:06:53,820
értékű és két csomópont mutatók.

124
00:06:53,820 --> 00:06:57,270
Általában ez képviseli a
szülő csomópont, amelynek egy sor mutató

125
00:06:57,270 --> 00:07:01,870
a bal oldalon, és egy gyermek csomópont
jobbra gyermek csomópont.

126
00:07:01,870 --> 00:07:04,510
A szerkezet egy bináris keresés
fa alkalmas arra is,

127
00:07:04,510 --> 00:07:05,940
a rekurzív keresést.

128
00:07:05,940 --> 00:07:09,730
A rekurzív hívás sem halad a
a bal vagy a jobb csomópont, de sokkal

129
00:07:09,730 --> 00:07:10,950
az, hogy a fa rövid.

130
00:07:10,950 --> 00:07:15,690
>> Mondja el, hogy szeretne végre egy műveletet
minden egyes csomópont egy bináris fa.

131
00:07:15,690 --> 00:07:17,410
Hogy lehet, hogy megy róla?

132
00:07:17,410 --> 00:07:20,600
Nos, meg tudná írni a rekurzív
funkció, amely végrehajtja a műveletet

133
00:07:20,600 --> 00:07:24,450
A szülő csomópont és teszi a rekurzív
hívja ugyanazt a funkciót,

134
00:07:24,450 --> 00:07:27,630
halad a bal és
jobb gyermek csomópont.

135
00:07:27,630 --> 00:07:31,650
Például, ez a funkció, ize, hogy
megváltoztatja az értéke egy adott csomópont és

136
00:07:31,650 --> 00:07:33,830
valamennyi gyermek 1-re.

137
00:07:33,830 --> 00:07:37,400
Az alapeset a null csomópont okai
a függvényt, jelezve,

138
00:07:37,400 --> 00:07:41,290
hogy nincsenek csomópontok
maradt, hogy az al-fa.

139
00:07:41,290 --> 00:07:42,620
>> Sétáljunk át rajta.

140
00:07:42,620 --> 00:07:44,340
Az első szülő 13.

141
00:07:44,340 --> 00:07:47,930
Mi változik az érték 1-re, majd hívja
a funkció a bal oldalon, valamint

142
00:07:47,930 --> 00:07:49,600
mint a jobb.

143
00:07:49,600 --> 00:07:53,910
A funkció, ize, nevezzük a bal oldalon
al-fa első, így a bal oldali csomópont

144
00:07:53,910 --> 00:07:57,730
majd áthelyezték az 1-es és ize lesz
felszólította, hogy a csomópont gyermekei,

145
00:07:57,730 --> 00:08:01,900
először, majd a bal és a jobb oldalon,
és így tovább és így tovább.

146
00:08:01,900 --> 00:08:05,630
És mondd meg nekik, hogy ágai nem
több gyereket, így ugyanaz a folyamat

147
00:08:05,630 --> 00:08:09,700
továbbra is a megfelelő gyermekek számára
amíg az egész fa csomópontok

148
00:08:09,700 --> 00:08:11,430
áthelyezték 1-re.

149
00:08:11,430 --> 00:08:15,390
>> Mint látható, akkor nem csak
csak egy rekurzív hívást.

150
00:08:15,390 --> 00:08:17,930
Csak annyi, mint majd a munkát.

151
00:08:17,930 --> 00:08:21,200
Mi van, ha volt egy fa, ahol minden egyes
csomópont volt három gyermek,

152
00:08:21,200 --> 00:08:23,100
Bal, középsõ és jobb?

153
00:08:23,100 --> 00:08:24,886
Hogyan szerkeszteni foo?

154
00:08:24,886 --> 00:08:25,860
Nos, egyszerű.

155
00:08:25,860 --> 00:08:30,250
Csak egy újabb rekurzív hívás
át a középső csomópont mutatót.

156
00:08:30,250 --> 00:08:34,549
>> Rekurzió nagyon erős, és nem
beszélve elegáns, de ez lehet egy

157
00:08:34,549 --> 00:08:38,010
nehéz fogalom az első, ezért
betegre, és vegye be időben.

158
00:08:38,010 --> 00:08:39,370
Kezdje az alapeset.

159
00:08:39,370 --> 00:08:42,650
Ez általában a legkönnyebb azonosítani,
és akkor lehet dolgozni

160
00:08:42,650 --> 00:08:43,830
visszafelé onnan.

161
00:08:43,830 --> 00:08:46,190
Tudod, hogy meg kell, hogy elérje a
alapeset, hogy a hatalom

162
00:08:46,190 --> 00:08:47,760
kapsz néhány tippet.

163
00:08:47,760 --> 00:08:53,120
Próbáld kifejezni egy adott esetben
mind az egyéb esetekben, vagy al-készletek.

164
00:08:53,120 --> 00:08:54,700
>> Köszönöm, hogy néz ez a rövid.

165
00:08:54,700 --> 00:08:58,920
Legalábbis, most már tudod
érti a vicceket, mint ez.

166
00:08:58,920 --> 00:09:01,250
A nevem Zamyla, és ez CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Vegyük ezt a funkciót, hi, a
érvénytelen funkciója, amely

169
00:09:07,170 --> 00:09:09,212
int, n, mint bemenet.

170
00:09:09,212 --> 00:09:11,020
Az alapeset az első.

171
00:09:11,020 --> 00:09:14,240
Ha n kisebb, mint 0, print
"Bye" és vissza.

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