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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Lai saprastu
rekursijas, jums ir

3
00:00:10,190 --> 00:00:13,820
vispirms ir jāsaprot rekursija.

4
00:00:13,820 --> 00:00:17,280
Ņemot rekursijas programmā dizaina līdzekļiem
ka jums ir self-godbijīgs

5
00:00:17,280 --> 00:00:18,570
definīcijas.

6
00:00:18,570 --> 00:00:21,520
Progresiju datu struktūras, piemēram,
ir datu struktūras, kas

7
00:00:21,520 --> 00:00:23,990
ietver sevi
to definīcijas.

8
00:00:23,990 --> 00:00:27,160
Bet šodien, mēs spēsim koncentrēties
gada rekursīvs funkcijas.

9
00:00:27,160 --> 00:00:31,160
>> Atgādināt, ka funkcijas veikt ieguldījumus,
argumenti, un atgriež vērtību, kā to

10
00:00:31,160 --> 00:00:34,480
produkciju pārstāv
šī shēma šeit.

11
00:00:34,480 --> 00:00:38,060
Mēs domājam par kastes, kā ķermeņa
funkcija, kas satur kopu

12
00:00:38,060 --> 00:00:42,340
instrukcijas, kas interpretē
ievades un nodrošināt produkciju.

13
00:00:42,340 --> 00:00:45,660
Ņemot tuvāk apskatīt ķermeņa iekšpusē
funkcija varētu atklāt zvanus

14
00:00:45,660 --> 00:00:47,430
citas funkcijas, kā arī.

15
00:00:47,430 --> 00:00:51,300
Veikt šo vienkāršo funkciju, foo, ka
aizņem vienu virkni kā ievade un

16
00:00:51,300 --> 00:00:54,630
izdrukas, cik daudz burtus
ka string ir.

17
00:00:54,630 --> 00:00:58,490
Funkciju strlen, stīgu garumu,
sauc, kuru produkcija

18
00:00:58,490 --> 00:01:01,890
kas nepieciešama, lai zvanu uz printf.

19
00:01:01,890 --> 00:01:05,770
>> Tagad, kas padara rekursīvā funkcija
īpašs ir tas, ka tā sevi dēvē.

20
00:01:05,770 --> 00:01:09,610
Mēs varam pārstāvēt šo rekursīvā
zvanu ar šo oranža bultiņa

21
00:01:09,610 --> 00:01:11,360
looping atpakaļ uz sevi.

22
00:01:11,360 --> 00:01:15,630
Bet izpildot sevi atkal būs tikai
veikt citu rekursīvas zvanu, un

23
00:01:15,630 --> 00:01:17,150
vēl un vēl.

24
00:01:17,150 --> 00:01:19,100
Bet rekursīvas funkcijas
nevar būt bezgalīgs.

25
00:01:19,100 --> 00:01:23,490
Viņiem ir beigt kaut kā, vai jūsu
Programma darbosies uz visiem laikiem.

26
00:01:23,490 --> 00:01:27,680
>> Tāpēc mums ir nepieciešams, lai atrastu veidu, kā lauzt
ārā no rekursīvas zvanu.

27
00:01:27,680 --> 00:01:29,900
Mēs to saucam par bāzes scenārijs.

28
00:01:29,900 --> 00:01:33,570
Ja bāzes scenārijs nosacījums ir izpildīts,
funkcija atgriež neveicot

29
00:01:33,570 --> 00:01:34,950
cits rekursīvas zvanu.

30
00:01:34,950 --> 00:01:39,610
Veikt šo funkciju, hi, tukšumu Function
kas ņem int n kā priekšnodokli.

31
00:01:39,610 --> 00:01:41,260
Bāzes scenārijs ir pirmajā vietā.

32
00:01:41,260 --> 00:01:46,220
Ja n ir mazāks par nulli, print bye un
atgriezties Visos citos gadījumos,

33
00:01:46,220 --> 00:01:49,400
funkcija drukāt hi un izpildīt
rekursīvas zvanu.

34
00:01:49,400 --> 00:01:53,600
Vēl viens zvans uz funkciju hi ar
decremented ievades vērtība.

35
00:01:53,600 --> 00:01:56,790
>> Tagad, pat ja mēs drukāt hi,
funkcija nebeidzas, kamēr mēs

36
00:01:56,790 --> 00:02:00,370
atpakaļ atgriešanas veidu,
šajā gadījumā spēkā neesošu.

37
00:02:00,370 --> 00:02:04,830
Tā, lai katrs n izņemot bāzes gadījumā
šī funkcija hi atgriezīsies hi

38
00:02:04,830 --> 00:02:06,890
mīnus n 1.

39
00:02:06,890 --> 00:02:10,050
Jo šī funkcija nav spēkā, lai gan, mēs
nav skaidri ierakstīt šeit atgriezties.

40
00:02:10,050 --> 00:02:12,000
Mēs vienkārši izpildīt funkciju.

41
00:02:12,000 --> 00:02:16,960
Tāpēc zvanot hi (3) tiks izdrukātas hi un
izpildīt hi (2), kas izpilda hi (1), viena

42
00:02:16,960 --> 00:02:20,560
kas izpilda hi (0), kurā
bāzes scenārijs nosacījums ir izpildīts.

43
00:02:20,560 --> 00:02:24,100
Tāpēc hi (0) drukā bye un atdevi.

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

45
00:02:24,990 --> 00:02:28,690
Tāpēc tagad, ka mēs saprotam pamatus
rekursīvas funkcijas, kas tiem nepieciešams

46
00:02:28,690 --> 00:02:32,730
vismaz vienu gadījumu, kā arī
rekursīvs zvanu, pieņemsim pāriet uz

47
00:02:32,730 --> 00:02:34,120
vairāk jēgpilnu piemērs.

48
00:02:34,120 --> 00:02:37,830
Viens, kas ne tikai atgriezties
neesošu vienalga ko.

49
00:02:37,830 --> 00:02:41,340
>> Pieņemsim apskatīt faktoriāliem
operācija izmanto visbiežāk

50
00:02:41,340 --> 00:02:43,660
varbūtības aprēķini.

51
00:02:43,660 --> 00:02:48,120
Faktorilāls no n ir produkts, katru
pozitīvs vesels skaitlis mazāks par

52
00:02:48,120 --> 00:02:49,400
un ir vienāds ar n.

53
00:02:49,400 --> 00:02:56,731
Tāpēc faktoriāls pieci ir 5 reizes 4 reizes
3 reizes 2 reizes 1, lai sniegtu 120.

54
00:02:56,731 --> 00:03:01,400
Četri faktoriāls ir 4 reizes 3 reizes
2 reizes 1, lai sniegtu 24.

55
00:03:01,400 --> 00:03:04,910
Un tas pats noteikums attiecas
jebkuram pozitīvam skaitlim.

56
00:03:04,910 --> 00:03:08,670
>> Tātad, kā mēs varbūt uzrakstīt rekursīvs
funkcija, kas aprēķina faktoriālu

57
00:03:08,670 --> 00:03:09,960
no vairākiem?

58
00:03:09,960 --> 00:03:14,700
Nu, mums būs nepieciešams, lai noteiktu gan
gadījumu, un rekursīvas zvanu.

59
00:03:14,700 --> 00:03:18,250
Rekursīvas zvans ir tāds pats
visos gadījumos, izņemot pamatnes

60
00:03:18,250 --> 00:03:21,420
gadījumā, kas nozīmē, ka mums būs
atrast modeli, kas dos mums mūsu

61
00:03:21,420 --> 00:03:23,350
vēlamais rezultāts.

62
00:03:23,350 --> 00:03:30,270
>> Šim piemēram, redzēt, kā 5 faktoriāls
ietver reizinot 4 3 ar 2 līdz 1

63
00:03:30,270 --> 00:03:33,010
Un ka tas pats pavairošana
ir atrodams šeit

64
00:03:33,010 --> 00:03:35,430
definīcija 4 faktori.

65
00:03:35,430 --> 00:03:39,810
Tātad mēs redzam, ka 5 faktoriāls ir
tikai 5 reizes 4 faktori.

66
00:03:39,810 --> 00:03:43,360
Tagad tas modelis piemērojams
4 Faktoriāls, kā arī?

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

68
00:03:44,280 --> 00:03:49,120
Mēs redzam, ka 4 faktoriāls satur
reizināšanas 3 reizes 2 reizes 1,

69
00:03:49,120 --> 00:03:51,590
Pašā definīcija 3 faktori.

70
00:03:51,590 --> 00:03:56,950
Tātad 4 faktoriāls ir vienāds ar 4 reizes 3
faktoriālo, un tā tālāk, un tā tālāk mūsu

71
00:03:56,950 --> 00:04:02,170
modelis pielīp līdz 1 faktoriāliem, kas
pēc būtības ir vienāds ar 1.

72
00:04:02,170 --> 00:04:04,950
>> Nav neviena cita pozitīva
veseli skaitļi pa kreisi.

73
00:04:04,950 --> 00:04:07,870
Tāpēc mums ir modeli
Mūsu rekursīvas zvanu.

74
00:04:07,870 --> 00:04:13,260
n faktoriāls ir vienāds ar n reizes
faktoriāls n mīnus 1.

75
00:04:13,260 --> 00:04:14,370
Un mūsu bāzes scenārijs?

76
00:04:14,370 --> 00:04:17,370
Tas būs vienkārši mūsu definīcija
1 faktori.

77
00:04:17,370 --> 00:04:19,995
>> Tāpēc tagad mēs varam virzīties uz rakstiski
kods funkciju.

78
00:04:19,995 --> 00:04:24,110
Attiecībā uz pamata lietas, mums būs
nosacījums n vienāds vienāds ar 1, ja

79
00:04:24,110 --> 00:04:25,780
mēs atgrieztos 1.

80
00:04:25,780 --> 00:04:29,280
Tad pārvietojas uz rekursīvo zvanu,
mēs atpakaļ n reizes

81
00:04:29,280 --> 00:04:32,180
faktoriāls no n mīnus 1.

82
00:04:32,180 --> 00:04:33,590
>> Tagad pieņemsim pārbaudīt šo mūsu.

83
00:04:33,590 --> 00:04:35,900
Pamēģināsim faktoriālu 4.

84
00:04:35,900 --> 00:04:39,420
Per mūsu funkcijas, tas ir vienāds
līdz 4 reizes faktoriālā (3).

85
00:04:39,420 --> 00:04:43,040
Faktorilāls (3) ir vienāda
3 reizes faktoriālās (2).

86
00:04:43,040 --> 00:04:48,700
Faktorilāls (2), ir vienāda ar 2 reizes
faktoriāls (1), kas atgriež 1.

87
00:04:48,700 --> 00:04:52,490
Faktoriāls (2), kas tagad atgriežas 2 reizes 1, 2.

88
00:04:52,490 --> 00:04:55,960
Faktoriāls (3), tagad var atgriezties
3 reizes 2, 6.

89
00:04:55,960 --> 00:05:02,490
Un, visbeidzot, faktoriālā (4)
atgriež 4 reizes 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Ja radušās kādas grūtības
ar rekursīvas zvanu, izlikties, ka

91
00:05:06,780 --> 00:05:09,660
funkcija darbojas jau.

92
00:05:09,660 --> 00:05:13,450
Ko es domāju ar šo ir tas, ka jums vajadzētu
uzticēties jūsu rekursīvas zvanu, lai atgrieztos

93
00:05:13,450 --> 00:05:15,100
pareizās vērtības.

94
00:05:15,100 --> 00:05:18,960
Piemēram, ja es zinu, ka
faktoriāls (5) ir vienāds ar 5 reizes

95
00:05:18,960 --> 00:05:24,870
faktoriāls (4), es esmu gatavojas ticu, ka
faktoriāls (4) dos man 24.

96
00:05:24,870 --> 00:05:28,510
Domājiet par to kā mainīgo, ja jūs
, tāpat kā tad, ja jūs jau ir definēts

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

98
00:05:30,070 --> 00:05:33,850
Tātad jebkuram faktoriāliem (n), tas ir
n produktu un

99
00:05:33,850 --> 00:05:35,360
iepriekšējā faktori.

100
00:05:35,360 --> 00:05:38,130
Un šī iepriekšējā faktoriāls
iegūst zvanot

101
00:05:38,130 --> 00:05:41,330
faktoriāls no n mīnus 1.

102
00:05:41,330 --> 00:05:45,130
>> Tagad, redzēt, ja jūs varat īstenot
rekursīvā funkcija sevi.

103
00:05:45,130 --> 00:05:50,490
Ielādēt savu terminālu, vai run.cs50.net,
un rakstīt funkciju summu

104
00:05:50,490 --> 00:05:54,770
kas notiek veselu n un atgriež
summa visiem pēc kārtas pozitīvs

105
00:05:54,770 --> 00:05:57,490
veseli skaitļi no n līdz 1.

106
00:05:57,490 --> 00:06:01,000
Es esmu rakstiski no summas dažu
vērtībām, lai palīdzētu jums mūsu.

107
00:06:01,000 --> 00:06:04,030
Pirmkārt, izdomāt
bāzes scenārijs stāvoklī.

108
00:06:04,030 --> 00:06:06,170
Tad, apskatīt summa (5).

109
00:06:06,170 --> 00:06:09,270
Vai jūs varat izteikt to ziņā
cita summa?

110
00:06:09,270 --> 00:06:11,290
Tagad, ko par summu (4)?

111
00:06:11,290 --> 00:06:15,630
Kā jūs varat izteikt summu (4)
ziņā citā summa?

112
00:06:15,630 --> 00:06:19,655
>> Kad jums ir summa, (5), un summa (4)
izteikts citu summu, sk

113
00:06:19,655 --> 00:06:22,970
ja jūs varat noteikt
Paraugs summu (n).

114
00:06:22,970 --> 00:06:26,190
Ja tā nav, mēģiniet daži citi skaitļi
un izteikt savas summas

115
00:06:26,190 --> 00:06:28,410
noteikumi citu numuru.

116
00:06:28,410 --> 00:06:31,930
Nosakot modeļus diskrēti
numuru, jūs labi pa ceļam uz

117
00:06:31,930 --> 00:06:34,320
identificējot modeli jebkuru n.

118
00:06:34,320 --> 00:06:38,040
>> Rekursija ir ļoti spēcīgs instruments,
tāpēc, protams, tas neattiecas tikai uz

119
00:06:38,040 --> 00:06:39,820
matemātiskās funkcijas.

120
00:06:39,820 --> 00:06:44,040
Recursion var izmantot ļoti efektīvi
, strādājot ar kokiem, piemēram.

121
00:06:44,040 --> 00:06:47,210
Pārbaudiet īsi par koku
rūpīgāka pārskatīšana, bet tagad

122
00:06:47,210 --> 00:06:51,140
atgādināt, ka bināro meklēšanas koku, kas
Konkrēti, ir izgatavoti no mezgliem, katrs

123
00:06:51,140 --> 00:06:53,820
ar vērtību un diviem mezglu norādes.

124
00:06:53,820 --> 00:06:57,270
Parasti tas pārstāv
mātes mezglā ar vienu līniju kas norāda

125
00:06:57,270 --> 00:07:01,870
uz kreiso bērnu mezglu un vienu
uz labo bērnu mezglā.

126
00:07:01,870 --> 00:07:04,510
Bināro meklēšanu struktūra
koku pakļauj sevi labi

127
00:07:04,510 --> 00:07:05,940
uz rekursīvo meklēšanu.

128
00:07:05,940 --> 00:07:09,730
Rekursīvas zvanu, vai nu iet uz
pa kreisi vai pa labi mezglā, bet vairāk

129
00:07:09,730 --> 00:07:10,950
un ka koka īss.

130
00:07:10,950 --> 00:07:15,690
>> Saka, jūs vēlaties, lai veiktu operāciju
katru mezglu bināro koku.

131
00:07:15,690 --> 00:07:17,410
Kā jūs varētu iet par to?

132
00:07:17,410 --> 00:07:20,600
Nu, jūs varētu uzrakstīt rekursīvo
funkcija, kas veic darbību

133
00:07:20,600 --> 00:07:24,450
mātes mezglā un padara rekursīvo
zvanu uz to pašu funkciju,

134
00:07:24,450 --> 00:07:27,630
kas iet pa kreisi un
Tiesības bērnu mezgliem.

135
00:07:27,630 --> 00:07:31,650
Piemēram, šī funkcija, foo, ka
maina konkrētā mezgla vērtību un

136
00:07:31,650 --> 00:07:33,830
visiem saviem bērniem pret 1.

137
00:07:33,830 --> 00:07:37,400
Bāze gadījums null mezglu cēloņiem
darbība, lai atgrieztos, norādot

138
00:07:37,400 --> 00:07:41,290
ka tajā nav mezgli
kreisi šajā sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Let 's staigāt pa to.

140
00:07:42,620 --> 00:07:44,340
Pirmais no vecākiem ir 13.

141
00:07:44,340 --> 00:07:47,930
Mēs mainīt vērtību 1, un tad zvana
Mūsu uzdevums pa kreisi, kā arī

142
00:07:47,930 --> 00:07:49,600
kā labi.

143
00:07:49,600 --> 00:07:53,910
Funkcija, foo, sauc pa kreisi
sub-tree, pirmkārt, tāpēc kreisā mezgls

144
00:07:53,910 --> 00:07:57,730
tiks atkal 1 un foo būs
izsaukt uz attiecīgās mezglā bērniem,

145
00:07:57,730 --> 00:08:01,900
vispirms pa kreisi un tad pa labi,
un tā tālāk, un tā tālāk.

146
00:08:01,900 --> 00:08:05,630
Un pateikt viņiem, ka filiāles nav
vairāk bērnu, lai pats process

147
00:08:05,630 --> 00:08:09,700
turpināsies pareizos bērniem
līdz brīdim, kad viss koks ir mezgli

148
00:08:09,700 --> 00:08:11,430
nodot līdz 1.

149
00:08:11,430 --> 00:08:15,390
>> Kā jūs varat redzēt, jums ir ne tikai
tikai vienu rekursīvas zvans.

150
00:08:15,390 --> 00:08:17,930
Tikpat daudz, cik saņems darba darīts.

151
00:08:17,930 --> 00:08:21,200
Ko darīt, ja jums bija koku, kur katra
mezgls bija trīs bērni,

152
00:08:21,200 --> 00:08:23,100
Pa kreisi, vidū un pa labi?

153
00:08:23,100 --> 00:08:24,886
Kā jūs rediģēt foo?

154
00:08:24,886 --> 00:08:25,860
Nu, vienkārši.

155
00:08:25,860 --> 00:08:30,250
Vienkārši pievienot citu rekursīvas zvanu un
iet pa vidu mezglā rādītājs.

156
00:08:30,250 --> 00:08:34,549
>> Rekursija ir ļoti spēcīgs, un nav
min elegant, bet tas var būt

157
00:08:34,549 --> 00:08:38,010
sarežģīts jēdziens sākumā, tāpēc
pacientu un veikt savu laiku.

158
00:08:38,010 --> 00:08:39,370
Sāciet ar pamata lietu.

159
00:08:39,370 --> 00:08:42,650
Tas parasti ir visvieglāk noteikt,
un tad jūs varat strādāt

160
00:08:42,650 --> 00:08:43,830
atpakaļ no turienes.

161
00:08:43,830 --> 00:08:46,190
Jūs zināt, jums ir nepieciešams, lai sasniegtu savu
bāzes scenārijs, lai varenība

162
00:08:46,190 --> 00:08:47,760
sniegt jums dažus padomus.

163
00:08:47,760 --> 00:08:53,120
Mēģināt izteikt vienu konkrētu lietu
noteikumi citos gadījumos, vai sub-kopas.

164
00:08:53,120 --> 00:08:54,700
>> Paldies, skatoties šo īso.

165
00:08:54,700 --> 00:08:58,920
Vismaz, tagad jūs varat
saprast jokus, kā šis.

166
00:08:58,920 --> 00:09:01,250
Mans vārds ir Zamyla, un tas ir CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Veikt šo funkciju, hi,
neesošu funkciju, kas notiek

169
00:09:07,170 --> 00:09:09,212
int, n, kā ieejas.

170
00:09:09,212 --> 00:09:11,020
Bāzes scenārijs ir pirmajā vietā.

171
00:09:11,020 --> 00:09:14,240
Ja n ir mazāks par 0, print
"Bye" un atgriešanās.

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