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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: În scopul de a înțelege
recursivitate, trebuie să vă

3
00:00:10,190 --> 00:00:13,820
înțelegem mai întâi recursivitate.

4
00:00:13,820 --> 00:00:17,280
Având recursivitate în programul de mijloace de proiectare
care le-au auto-referențială

5
00:00:17,280 --> 00:00:18,570
definiții.

6
00:00:18,570 --> 00:00:21,520
Structuri de date recursive, de exemplu,
sunt structuri de date care

7
00:00:21,520 --> 00:00:23,990
se includ în
definițiile lor.

8
00:00:23,990 --> 00:00:27,160
Dar astăzi, am de gând să se concentreze
pe functii recursive.

9
00:00:27,160 --> 00:00:31,160
>> Amintiti-va ca funcțiile lua intrări,
argumente, și să se întoarcă o valoare ca lor

10
00:00:31,160 --> 00:00:34,480
reprezentată de ieșire
această schemă de aici.

11
00:00:34,480 --> 00:00:38,060
Ne vom gândi din cutie ca organism de
funcția, care conține setul de

12
00:00:38,060 --> 00:00:42,340
instrucțiuni care să interpreteze
de intrare și să ofere o ieșire.

13
00:00:42,340 --> 00:00:45,660
Având o privire mai atentă în interiorul corpului
funcția ar putea dezvălui apeluri la

14
00:00:45,660 --> 00:00:47,430
alte funcții, precum și.

15
00:00:47,430 --> 00:00:51,300
Ia această funcție simplă, foo, că
are un singur șir ca intrare și

16
00:00:51,300 --> 00:00:54,630
printuri cât de multe scrisori
că șir are.

17
00:00:54,630 --> 00:00:58,490
Funcția strlen, de lungime șir,
este numit, a cărui ieșire este

18
00:00:58,490 --> 00:01:01,890
necesar pentru apelul la printf.

19
00:01:01,890 --> 00:01:05,770
>> Acum, ceea ce face o funcție recursive
special este că se numește.

20
00:01:05,770 --> 00:01:09,610
Ne putem reprezenta această recursive
numesc cu acest Săgeată portocalie

21
00:01:09,610 --> 00:01:11,360
looping înapoi la sine.

22
00:01:11,360 --> 00:01:15,630
Dar executarea se din nou numai ca va
face un alt apel recursiv, și

23
00:01:15,630 --> 00:01:17,150
altul și altul.

24
00:01:17,150 --> 00:01:19,100
Dar funcțiile recursive
nu poate fi infinit.

25
00:01:19,100 --> 00:01:23,490
Ei trebuie să se încheie într-un fel, sau dvs.
Programul va rula pentru totdeauna.

26
00:01:23,490 --> 00:01:27,680
>> Deci, avem nevoie pentru a găsi o modalitate de a sparge
din apelurile recursive.

27
00:01:27,680 --> 00:01:29,900
Noi numim acest caz de bază.

28
00:01:29,900 --> 00:01:33,570
În cazul în care condiția caz de bază este îndeplinită,
funcția returnează fără a face

29
00:01:33,570 --> 00:01:34,950
un alt apel recursiv.

30
00:01:34,950 --> 00:01:39,610
Ia această funcție, hi, o funcție gol
care are o int n ca intrare.

31
00:01:39,610 --> 00:01:41,260
Scenariul de bază este pe primul loc.

32
00:01:41,260 --> 00:01:46,220
Dacă n este mai mică decât zero, la revedere de imprimare și
Pentru a reveni toate celelalte cazuri,

33
00:01:46,220 --> 00:01:49,400
Funcția va imprima hi și executa
apelul recursiv.

34
00:01:49,400 --> 00:01:53,600
Un alt apel la funcția de hi cu
o valoare de intrare decrementat.

35
00:01:53,600 --> 00:01:56,790
>> Acum, chiar dacă ne-am imprima hi,
Funcția nu se va termina până când vom

36
00:01:56,790 --> 00:02:00,370
reveni tip de întoarcere,
în acest caz nule.

37
00:02:00,370 --> 00:02:04,830
Deci, pentru orice n alta decât cazul de bază,
această funcție va întoarce hi hi

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

39
00:02:06,890 --> 00:02:10,050
Din moment ce această funcție este nulă, deși, ne-am
nu va tip în mod explicit reveni aici.

40
00:02:10,050 --> 00:02:12,000
Vom executa doar funcția.

41
00:02:12,000 --> 00:02:16,960
Deci, de asteptare hi (3) se vor imprima hi și
executa hi (2), care execută hi (1), un

42
00:02:16,960 --> 00:02:20,560
care execută hi (0), unde
condiție caz de bază este îndeplinită.

43
00:02:20,560 --> 00:02:24,100
Deci, hi (0) imprimă revedere și se întoarce.

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

45
00:02:24,990 --> 00:02:28,690
Deci, acum că ne-am înțeles elementele de bază ale
functii recursive, de care au nevoie

46
00:02:28,690 --> 00:02:32,730
cel puțin un caz de bază, precum și un
apel recursiv, haideți să trecem la o

47
00:02:32,730 --> 00:02:34,120
exemplu mai semnificativ.

48
00:02:34,120 --> 00:02:37,830
Unul care nu doar întoarce
nule, indiferent de ce.

49
00:02:37,830 --> 00:02:41,340
>> Să aruncăm o privire la factorial
operație utilizate cel mai frecvent în

50
00:02:41,340 --> 00:02:43,660
calcule de probabilitate.

51
00:02:43,660 --> 00:02:48,120
Factorial n este produs de fiecare
întreg pozitiv mai puțin

52
00:02:48,120 --> 00:02:49,400
și egal cu n.

53
00:02:49,400 --> 00:02:56,731
Cinci astfel factorial este de 5 ori de 4 ori
De 3 ori 2 ori 1 pentru a da 120.

54
00:02:56,731 --> 00:03:01,400
Patru factorial este de 4 ori de 3 ori
De 2 ori pentru a da un 24.

55
00:03:01,400 --> 00:03:04,910
Și se aplică aceeași regulă
pentru orice număr întreg pozitiv.

56
00:03:04,910 --> 00:03:08,670
>> Deci, cum am putea scrie un recursiv
functie care calculeaza factorialul

57
00:03:08,670 --> 00:03:09,960
de un număr?

58
00:03:09,960 --> 00:03:14,700
Ei bine, avem nevoie pentru a identifica atât
cazul de bază și apelul recursiv.

59
00:03:14,700 --> 00:03:18,250
Apelul recursiv va fi la fel
pentru toate cazurile, cu excepția bazei

60
00:03:18,250 --> 00:03:21,420
caz, ceea ce înseamnă că va trebui să
găsi un model care ne va da noastre

61
00:03:21,420 --> 00:03:23,350
rezultatul dorit.

62
00:03:23,350 --> 00:03:30,270
>> Pentru acest exemplu, a se vedea cât de 5 factorial
implică înmulțirea 4 de 3 până la 2 până la 1

63
00:03:30,270 --> 00:03:33,010
Și că foarte același multiplicare
este găsit aici,

64
00:03:33,010 --> 00:03:35,430
definiție de 4 factorial.

65
00:03:35,430 --> 00:03:39,810
Deci, vedem că 5 factorial este
doar de 5 ori 4 factorial.

66
00:03:39,810 --> 00:03:43,360
Acum, se aplică acest model
la 4 factoriale, precum și?

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

68
00:03:44,280 --> 00:03:49,120
Vedem că 4 factorial conține
multiplicare de 3 ori de 2 ori 1,

69
00:03:49,120 --> 00:03:51,590
foarte aceeași definiție ca și 3 factorial.

70
00:03:51,590 --> 00:03:56,950
Deci 4 factorial este egală cu de 4 ori 3
factorială, și așa mai departe și așa mai departe noastră

71
00:03:56,950 --> 00:04:02,170
model lipeste până la 1 factorial, care
prin definiție este egal cu 1.

72
00:04:02,170 --> 00:04:04,950
>> Nu există nici o altă pozitiv
numere întregi stânga.

73
00:04:04,950 --> 00:04:07,870
Așa că avem modelul de
apelul nostru recursiv.

74
00:04:07,870 --> 00:04:13,260
n factorial este egal cu de n ori
factorialul lui n minus 1.

75
00:04:13,260 --> 00:04:14,370
Și cazul nostru de bază?

76
00:04:14,370 --> 00:04:17,370
Care va fi doar definiția noastră
din 1 factorial.

77
00:04:17,370 --> 00:04:19,995
>> Deci, acum putem trece la scris
cod pentru funcția.

78
00:04:19,995 --> 00:04:24,110
Pentru cazul de bază, vom avea
condiție n este egal cu 1, unde

79
00:04:24,110 --> 00:04:25,780
ne vom intoarce 1.

80
00:04:25,780 --> 00:04:29,280
Apoi se deplasează pe apelul recursiv,
ne vom intoarce de n ori

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

82
00:04:32,180 --> 00:04:33,590
>> Acum, haideți să testați acest noastră.

83
00:04:33,590 --> 00:04:35,900
Să încercăm factorial 4.

84
00:04:35,900 --> 00:04:39,420
Pe funcția noastră este egal
la 4 ori factorial (3).

85
00:04:39,420 --> 00:04:43,040
Factorial (3) este egal cu
De 3 ori factoriale (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) este egală cu de 2 ori
factorial (1), care returnează 1.

87
00:04:48,700 --> 00:04:52,490
Factorial (2) se întoarce acum de 2 ori 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3) se pot întoarce acum
3 ori 2, 6.

89
00:04:55,960 --> 00:05:02,490
Și, în sfârșit, factorial (4)
returnează 4 ori 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Dacă sunteți întâmpină nici o dificultate
cu apelul recursiv, pretinde că

91
00:05:06,780 --> 00:05:09,660
funcția funcționează deja.

92
00:05:09,660 --> 00:05:13,450
Ce vreau să spun prin asta este că ar trebui să
încredere în apelurile recursive pentru a reveni

93
00:05:13,450 --> 00:05:15,100
valorile corecte.

94
00:05:15,100 --> 00:05:18,960
De exemplu, dacă știu că
factorial (5) este egal cu de 5 ori

95
00:05:18,960 --> 00:05:24,870
factorial (4), am de gând să aibă încredere că
factorial (4), va da-mi 24.

96
00:05:24,870 --> 00:05:28,510
Ganditi-va ca o variabilă, dacă
va fi, ca si cum ai deja definit

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

98
00:05:30,070 --> 00:05:33,850
Deci, pentru orice factorial (n), este
produsul de n și

99
00:05:33,850 --> 00:05:35,360
factorialul anterior.

100
00:05:35,360 --> 00:05:38,130
Și acest factorial anterior
este obținut prin apelarea

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

102
00:05:41,330 --> 00:05:45,130
>> Acum, vezi dacă poți să pună în aplicare un
funcționeze recursiv-te.

103
00:05:45,130 --> 00:05:50,490
Încărcați până terminalul, sau run.cs50.net,
și de a scrie o sumă funcție

104
00:05:50,490 --> 00:05:54,770
care are un număr întreg n și returnează
Suma de toate pozitive consecutive

105
00:05:54,770 --> 00:05:57,490
numere întregi de la 1 la n.

106
00:05:57,490 --> 00:06:01,000
I-am scris din sumele de unele
valori pentru a vă ajuta nostru.

107
00:06:01,000 --> 00:06:04,030
În primul rând, dau seama de
condiție caz de bază.

108
00:06:04,030 --> 00:06:06,170
Apoi, uita-te la suma (5).

109
00:06:06,170 --> 00:06:09,270
Poți să-l exprime în termeni
de altă sumă?

110
00:06:09,270 --> 00:06:11,290
Acum, ce putem spune despre suma (4)?

111
00:06:11,290 --> 00:06:15,630
Cum vă puteți exprima suma (4)
în ceea ce privește o altă sumă?

112
00:06:15,630 --> 00:06:19,655
>> Odată ce aveți suma (5) și suma (4)
exprimată în termeni de alte sume, a se vedea

113
00:06:19,655 --> 00:06:22,970
dacă vă puteți identifica un
model pentru suma (n).

114
00:06:22,970 --> 00:06:26,190
Dacă nu, încercați alte câteva numere
și exprima sumele lor în

115
00:06:26,190 --> 00:06:28,410
ceea ce privește alte numere.

116
00:06:28,410 --> 00:06:31,930
Prin identificarea modele de discret
numere, esti bine pe cale de a

117
00:06:31,930 --> 00:06:34,320
identificarea model pentru orice n.

118
00:06:34,320 --> 00:06:38,040
>> Recursivitate este un instrument foarte puternic,
astfel, desigur, nu se limitează la

119
00:06:38,040 --> 00:06:39,820
funcții matematice.

120
00:06:39,820 --> 00:06:44,040
Recursivitatea poate fi folosit foarte eficient
atunci când se ocupă cu copaci, de exemplu.

121
00:06:44,040 --> 00:06:47,210
Check out scurt pe copaci pentru o
mai mult analiză amănunțită, dar pentru acum

122
00:06:47,210 --> 00:06:51,140
amintesc că arbori de căutare binare, în
special, sunt formate din noduri, fiecare

123
00:06:51,140 --> 00:06:53,820
cu o valoare și două indicii nod.

124
00:06:53,820 --> 00:06:57,270
De obicei, aceasta este reprezentată de
nod părinte având o linie de indicare

125
00:06:57,270 --> 00:07:01,870
la nodul copil din stânga și cea
la nodul copil din dreapta.

126
00:07:01,870 --> 00:07:04,510
Structura unei căutări binare
copac se pretează bine

127
00:07:04,510 --> 00:07:05,940
la o căutare recursive.

128
00:07:05,940 --> 00:07:09,730
Apelul recursiv trece fie în
la stânga sau la nodul din dreapta, dar mai mult

129
00:07:09,730 --> 00:07:10,950
din care în scurt copac.

130
00:07:10,950 --> 00:07:15,690
>> Presupunem că doriți să efectuați o operație pe
fiecare nod într-un arbore binar.

131
00:07:15,690 --> 00:07:17,410
Cum s-ar putea merge despre asta?

132
00:07:17,410 --> 00:07:20,600
Ei bine, ai putea scrie o recursive
funcție care efectuează operația

133
00:07:20,600 --> 00:07:24,450
pe nodul părinte și face o recursiv
apela la aceeași funcție,

134
00:07:24,450 --> 00:07:27,630
trece în stânga și
noduri copil dreapta.

135
00:07:27,630 --> 00:07:31,650
De exemplu, această funcție, foo, că
schimba valoarea unui nod dat și

136
00:07:31,650 --> 00:07:33,830
toți copii săi la 1.

137
00:07:33,830 --> 00:07:37,400
Cazul de bază a unei cauze nod nule
funcția de a reveni, indicând

138
00:07:37,400 --> 00:07:41,290
că nu există noduri
a lăsat în care sub-arbore.

139
00:07:41,290 --> 00:07:42,620
>> Să mergem prin ea.

140
00:07:42,620 --> 00:07:44,340
Primul-mamă este de 13.

141
00:07:44,340 --> 00:07:47,930
Vom schimba valoarea la 1, și apoi apel
Funcția noastră pe stânga, precum și

142
00:07:47,930 --> 00:07:49,600
ca dreapta.

143
00:07:49,600 --> 00:07:53,910
Funcția, foo, este numit pe stânga
sub-arbore întâi, așa nodul stâng

144
00:07:53,910 --> 00:07:57,730
vor fi realocate la 1 și va fi foo
fi numit pe copii că nod,

145
00:07:57,730 --> 00:08:01,900
întâi stânga și apoi dreapta,
și așa mai departe și așa mai departe.

146
00:08:01,900 --> 00:08:05,630
Și spune-le că sucursalele nu au
orice mai mulți copii, astfel încât același proces

147
00:08:05,630 --> 00:08:09,700
va continua pentru copii potrivite
până noduri întreg arborele sunt

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

149
00:08:11,430 --> 00:08:15,390
>> După cum puteți vedea, nu sunt limitate
la doar un apel recursiv.

150
00:08:15,390 --> 00:08:17,930
La fel de multe ca va face treaba.

151
00:08:17,930 --> 00:08:21,200
Ce se întâmplă dacă ați avut un copac în care fiecare
nod a avut trei copii,

152
00:08:21,200 --> 00:08:23,100
Stânga, de mijloc, și nu?

153
00:08:23,100 --> 00:08:24,886
Cum ar fi editarea foo?

154
00:08:24,886 --> 00:08:25,860
Ei bine, simplu.

155
00:08:25,860 --> 00:08:30,250
Trebuie doar să adăugați un alt apel recursiv și
trece la indicatorul nod de mijloc.

156
00:08:30,250 --> 00:08:34,549
>> Recursivitate este foarte puternic și nu a
menționa elegant, dar poate fi un

157
00:08:34,549 --> 00:08:38,010
concept greu la început, astfel încât să fie
pacient și ia timp.

158
00:08:38,010 --> 00:08:39,370
Începeți cu cazul de bază.

159
00:08:39,370 --> 00:08:42,650
Este, de obicei, cel mai ușor de a identifica,
și apoi puteți lucra

160
00:08:42,650 --> 00:08:43,830
înapoi de acolo.

161
00:08:43,830 --> 00:08:46,190
Stii ca ai nevoie pentru a ajunge la dvs.
cazul de bază, astfel încât s-ar putea

162
00:08:46,190 --> 00:08:47,760
vă dau câteva indicii.

163
00:08:47,760 --> 00:08:53,120
Încercați să-și exprime un caz specific în
ceea ce privește alte cazuri, sau în sub-seturi.

164
00:08:53,120 --> 00:08:54,700
>> Vă mulțumim pentru vizionarea acestui scurt.

165
00:08:54,700 --> 00:08:58,920
Cel puțin, acum aveți posibilitatea să
înțelege glumele de acest gen.

166
00:08:58,920 --> 00:09:01,250
Numele meu este Zamyla, iar acest lucru este CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Ia această funcție, hi, o
Funcția gol care ia

169
00:09:07,170 --> 00:09:09,212
un int, n, ca intrare.

170
00:09:09,212 --> 00:09:11,020
Scenariul de bază este pe primul loc.

171
00:09:11,020 --> 00:09:14,240
Dacă n este mai mic decât 0, print
"La revedere" și retur.

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