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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Per tal d'entendre
recursivitat, s'ha de

3
00:00:10,190 --> 00:00:13,820
primer entendre la recursivitat.

4
00:00:13,820 --> 00:00:17,280
Tenir la recursivitat en el programa de disseny de mitjans
que té autoreferencial

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

6
00:00:18,570 --> 00:00:21,520
Estructures de dades recursives, per exemple,
són estructures de dades que

7
00:00:21,520 --> 00:00:23,990
incloure a si mateixos en
les seves definicions.

8
00:00:23,990 --> 00:00:27,160
Però avui en dia, ens centrarem
en funcions recursives.

9
00:00:27,160 --> 00:00:31,160
>> Recordem que les funcions necessiten entrades,
arguments i retorna un valor com el seu

10
00:00:31,160 --> 00:00:34,480
de sortida representat per
aquest diagrama aquí.

11
00:00:34,480 --> 00:00:38,060
Ja pensarem en la caixa com el cos de
la funció, que conté el conjunt de

12
00:00:38,060 --> 00:00:42,340
instruccions que interpreten el
d'entrada i proporcionar una sortida.

13
00:00:42,340 --> 00:00:45,660
Prenent una mirada més propera a l'interior del cos de
la funció podria revelar les trucades a

14
00:00:45,660 --> 00:00:47,430
altres funcions també.

15
00:00:47,430 --> 00:00:51,300
Prengui aquesta funció simple, foo, que
pren una sola cadena com a entrada i

16
00:00:51,300 --> 00:00:54,630
impressions de quantes lletres
aquesta cadena té.

17
00:00:54,630 --> 00:00:58,490
El strlen funció, per longitud de la cadena,
es diu, la sortida és

18
00:00:58,490 --> 00:01:01,890
requerit per la crida a printf.

19
00:01:01,890 --> 00:01:05,770
>> Ara, el que fa una funció recursiva
especial és que es diu a si mateixa.

20
00:01:05,770 --> 00:01:09,610
Podem representar aquest recursiva
trucar amb aquesta fletxa taronja

21
00:01:09,610 --> 00:01:11,360
bucle de nou a si mateix.

22
00:01:11,360 --> 00:01:15,630
Però l'execució en si de nou només es
realitzar una altra crida recursiva, i

23
00:01:15,630 --> 00:01:17,150
altre i un altre.

24
00:01:17,150 --> 00:01:19,100
Però les funcions recursives
no pot ser infinit.

25
00:01:19,100 --> 00:01:23,490
Han d'acabar d'alguna manera, o si
programa s'executarà sempre.

26
00:01:23,490 --> 00:01:27,680
>> Així que hem de trobar una manera de trencar
de les crides recursives.

27
00:01:27,680 --> 00:01:29,900
D'això en diem el cas base.

28
00:01:29,900 --> 00:01:33,570
Quan es compleix la condició de cas base,
la funció retorna sense fer

29
00:01:33,570 --> 00:01:34,950
una altra crida recursiva.

30
00:01:34,950 --> 00:01:39,610
Prengui aquesta funció, hi, una funció void
que pren un sencer n com a entrada.

31
00:01:39,610 --> 00:01:41,260
El cas base és el primer.

32
00:01:41,260 --> 00:01:46,220
Si n és menor que zero, adéu d'impressió i
tornar Per a tots els altres casos, el

33
00:01:46,220 --> 00:01:49,400
funció imprimirà hi i executar
la crida recursiva.

34
00:01:49,400 --> 00:01:53,600
Una altra crida a la funció amb hi
un valor d'entrada decrementa.

35
00:01:53,600 --> 00:01:56,790
>> Ara, tot i que imprimim hi, la
funció no acabarà fins que

36
00:01:56,790 --> 00:02:00,370
retornar el seu tipus de retorn,
en aquest cas sense efecte.

37
00:02:00,370 --> 00:02:04,830
Així, per cada n que no sigui el cas base,
aquesta funció hi hi tornarà

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

39
00:02:06,890 --> 00:02:10,050
Atès que aquesta funció no és vàlida, però, que
no s'escrigui explícitament retorn aquí.

40
00:02:10,050 --> 00:02:12,000
Acabàvem executarem la funció.

41
00:02:12,000 --> 00:02:16,960
Així de trucar hi (3) imprimirà hola i
executar hi (2), que executa hi (1) un

42
00:02:16,960 --> 00:02:20,560
que executa hi (0), en què el
es compleix la condició de cas base.

43
00:02:20,560 --> 00:02:24,100
Així hi (0) imprimeix bye i torna.

44
00:02:24,100 --> 00:02:24,990
>> D'acord.

45
00:02:24,990 --> 00:02:28,690
Així que ara que entenem els fonaments de la
funcions recursives, que necessiten

46
00:02:28,690 --> 00:02:32,730
almenys un cas base, així com un
crida recursiva, anem a passar a un

47
00:02:32,730 --> 00:02:34,120
exemple més significatiu.

48
00:02:34,120 --> 00:02:37,830
Un que no només tornar
anul · lar tant i fa.

49
00:02:37,830 --> 00:02:41,340
>> Anem a fer una ullada a el factorial
operació més comunament utilitzat en

50
00:02:41,340 --> 00:02:43,660
càlculs de probabilitat.

51
00:02:43,660 --> 00:02:48,120
Factorial d'n és el producte de tots els
nombre enter positiu menys

52
00:02:48,120 --> 00:02:49,400
i igual a n.

53
00:02:49,400 --> 00:02:56,731
Així que 5 factorial és 5 vegades 4 vegades
3 vegades 2 cops 1 per a donar 120.

54
00:02:56,731 --> 00:03:01,400
Quatre factorial és 4 vegades 3 vegades
2 cops 1 per a donar 24.

55
00:03:01,400 --> 00:03:04,910
I s'aplica la mateixa regla
a qualsevol nombre enter positiu.

56
00:03:04,910 --> 00:03:08,670
>> Llavors, com podríem escriure una recursiva
funció que calcula el factorial

57
00:03:08,670 --> 00:03:09,960
d'un nombre?

58
00:03:09,960 --> 00:03:14,700
Bé, anem a necessitar per identificar tant el
cas base i la crida recursiva.

59
00:03:14,700 --> 00:03:18,250
La crida recursiva serà el mateix
per a tots els casos excepte per a la base

60
00:03:18,250 --> 00:03:21,420
cas, el que significa que haurem de
trobar un patró que ens donarà la nostra

61
00:03:21,420 --> 00:03:23,350
resultat desitjat.

62
00:03:23,350 --> 00:03:30,270
>> Per a aquest exemple, veure com 5 factorial
implica multiplicar 4 per 3 per 2 per 1

63
00:03:30,270 --> 00:03:33,010
I aquesta mateixa multiplicació
es troba aquí, el

64
00:03:33,010 --> 00:03:35,430
definició de 4 factorial.

65
00:03:35,430 --> 00:03:39,810
Així que veiem que 5 factorial és
a 5 vegades 4 factorial.

66
00:03:39,810 --> 00:03:43,360
Ara s'aplica aquest patró
a 4 factorial, així?

67
00:03:43,360 --> 00:03:44,280
Sí

68
00:03:44,280 --> 00:03:49,120
Veiem que 4 factorial conté la
multiplicar 3 vegades 2 cops 1, el

69
00:03:49,120 --> 00:03:51,590
pròpia definició com 3 factorial.

70
00:03:51,590 --> 00:03:56,950
Així factorial 4 és igual a 4 vegades 3
factorial, i així successivament i així successivament nostra

71
00:03:56,950 --> 00:04:02,170
patró de pals fins a 1 factorial, la qual
per definició és igual a 1.

72
00:04:02,170 --> 00:04:04,950
>> No hi ha altra positiva
sencers van ser.

73
00:04:04,950 --> 00:04:07,870
Així que tenim el model per
nostra crida recursiva.

74
00:04:07,870 --> 00:04:13,260
n factorial és igual a n vegades
el factorial de n almenys 1.

75
00:04:13,260 --> 00:04:14,370
I el nostre cas base?

76
00:04:14,370 --> 00:04:17,370
Això acaba de ser la nostra definició
d'1 factorial.

77
00:04:17,370 --> 00:04:19,995
>> Així que ara podem passar a l'escriptura
codi de la funció.

78
00:04:19,995 --> 00:04:24,110
Per al cas base, que tindrem la
condició n és igual a és igual a 1, en els quals

79
00:04:24,110 --> 00:04:25,780
li retornarem 1.

80
00:04:25,780 --> 00:04:29,280
Després de passar a la crida recursiva,
tornarem n vegades el

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

82
00:04:32,180 --> 00:04:33,590
>> Ara anem a provar aquesta nostra.

83
00:04:33,590 --> 00:04:35,900
Provem factorial 4.

84
00:04:35,900 --> 00:04:39,420
Per la nostra funció és igual
a 4 vegades factorial (3).

85
00:04:39,420 --> 00:04:43,040
Factorial (3) és igual a
3 vegades factorials (2).

86
00:04:43,040 --> 00:04:48,700
Factorial (2) és igual a 2 vegades
factorial (1), que retorna 1.

87
00:04:48,700 --> 00:04:52,490
Factorial (2) ara retorna 2 temps 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorial (3) ara pot tornar
3 vegades 2, 6.

89
00:04:55,960 --> 00:05:02,490
I, finalment, factorial (4)
retorna 4 temps 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Si vostè està trobant alguna dificultat
amb la crida recursiva, pretendre que

91
00:05:06,780 --> 00:05:09,660
la funció ja funciona.

92
00:05:09,660 --> 00:05:13,450
El que vull dir amb això és que vostè ha
confiar en les seves trucades recursives per tornar

93
00:05:13,450 --> 00:05:15,100
els valors correctes.

94
00:05:15,100 --> 00:05:18,960
Per exemple, si jo sé que
factorial (5) és igual a 5 vegades

95
00:05:18,960 --> 00:05:24,870
factorial (4), vaig a confiar que
factorial (4) em donarà 24.

96
00:05:24,870 --> 00:05:28,510
Penseu en això com una variable, si
voluntat, com si ja ha definit

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

98
00:05:30,070 --> 00:05:33,850
Així que per a qualsevol factorial (N), que és
el producte de n i

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

100
00:05:35,360 --> 00:05:38,130
I això factorial anterior
s'obté trucant al

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

102
00:05:41,330 --> 00:05:45,130
>> Ara, a veure si es pot implementar un
recursiva funcionar a tu mateix.

103
00:05:45,130 --> 00:05:50,490
Càrrega teu terminal, o run.cs50.net,
i escriure una funció sum

104
00:05:50,490 --> 00:05:54,770
que pren un sencer n i retorna el
suma de totes positiva consecutiva

105
00:05:54,770 --> 00:05:57,490
nombres enters de n és 1.

106
00:05:57,490 --> 00:06:01,000
He escrit una ullada a les sumes d'alguns
valors que l'ajudaran a la nostra.

107
00:06:01,000 --> 00:06:04,030
En primer lloc, esbrinar el
condicions del cas base.

108
00:06:04,030 --> 00:06:06,170
Llavors, mira suma (5).

109
00:06:06,170 --> 00:06:09,270
Es pot expressar en termes
d'una altra suma?

110
00:06:09,270 --> 00:06:11,290
Ara, què passa amb summa (4)?

111
00:06:11,290 --> 00:06:15,630
Com es pot expressar suma (4)
en termes d'una altra suma?

112
00:06:15,630 --> 00:06:19,655
>> Un cop tingueu suma (5) i suma (4)
expressat en termes d'altres quantitats, consulteu

113
00:06:19,655 --> 00:06:22,970
si es pot identificar una
patró per la suma (n).

114
00:06:22,970 --> 00:06:26,190
Si no, proveu alguns altres números
i expressar les seves sumes en

115
00:06:26,190 --> 00:06:28,410
termes d'altres números.

116
00:06:28,410 --> 00:06:31,930
Mitjançant la identificació dels patrons de discreta
números, vostè està bé en la seva manera de

117
00:06:31,930 --> 00:06:34,320
identificar el patró per a qualsevol n.

118
00:06:34,320 --> 00:06:38,040
>> La recursivitat és una eina molt poderosa,
així que per descomptat no es limita a

119
00:06:38,040 --> 00:06:39,820
funcions matemàtiques.

120
00:06:39,820 --> 00:06:44,040
La recursivitat pot ser utilitzat de manera molt eficaç
quan es tracta d'arbres, per exemple.

121
00:06:44,040 --> 00:06:47,210
Fes una ullada a la tallada dels arbres durant un
opinió més a fons, però per ara

122
00:06:47,210 --> 00:06:51,140
recordar que els arbres de cerca binaris, en
en particular, es componen de nodes, cadascun

123
00:06:51,140 --> 00:06:53,820
amb un valor i dos punters de node.

124
00:06:53,820 --> 00:06:57,270
En general, això està representat pel
node pare té una apuntant línia

125
00:06:57,270 --> 00:07:01,870
al node fill esquerre i un
al node fill dret.

126
00:07:01,870 --> 00:07:04,510
L'estructura d'una recerca binària
arbre es presta bé

127
00:07:04,510 --> 00:07:05,940
a una recerca recursiva.

128
00:07:05,940 --> 00:07:09,730
L'anomenada recursiva sigui passa al
esquerra o dreta en el node, però més

129
00:07:09,730 --> 00:07:10,950
que en el curt arbre.

130
00:07:10,950 --> 00:07:15,690
>> Diguem que vostè vol fer una operació en
cada node individual en un arbre binari.

131
00:07:15,690 --> 00:07:17,410
Com podria vostè anar sobre això?

132
00:07:17,410 --> 00:07:20,600
Bé, es podria escriure un recursiu
la funció que realitza l'operació

133
00:07:20,600 --> 00:07:24,450
en el node pare i fa una recursiva
cridar a la mateixa funció,

134
00:07:24,450 --> 00:07:27,630
que passa a l'esquerra i
nodes secundaris adequats.

135
00:07:27,630 --> 00:07:31,650
Per exemple, aquesta funció, foo, que
canvia el valor d'un node donat i

136
00:07:31,650 --> 00:07:33,830
tots els seus fills a la 1.

137
00:07:33,830 --> 00:07:37,400
El cas base d'un node causes nuls
la funció per tornar, el que indica

138
00:07:37,400 --> 00:07:41,290
que no hi ha nodes
deixat en aquest sub-arbre.

139
00:07:41,290 --> 00:07:42,620
>> Anem a caminar a través d'ell.

140
00:07:42,620 --> 00:07:44,340
El primer dels pares és de 13.

141
00:07:44,340 --> 00:07:47,930
Canviem el valor a 1, i després diem
la nostra funció a la banda esquerra, així

142
00:07:47,930 --> 00:07:49,600
com el dret.

143
00:07:49,600 --> 00:07:53,910
La funció, foo, es diu a l'esquerra
sub-arbre en primer lloc, de manera que el node esquerre

144
00:07:53,910 --> 00:07:57,730
serà reassignat a 1 i Foo
es va demanar als nens d'aquest node,

145
00:07:57,730 --> 00:08:01,900
primer l'esquerra i després la dreta,
i així successivament i així successivament.

146
00:08:01,900 --> 00:08:05,630
I els dic que les branques no tenen
tenir més fills de manera que el mateix procés

147
00:08:05,630 --> 00:08:09,700
continuarà pels fills dreta
fins als nodes de la totalitat dels arbres són

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

149
00:08:11,430 --> 00:08:15,390
>> Com podeu veure, vostè no està limitat
a només una crida recursiva.

150
00:08:15,390 --> 00:08:17,930
Igual que tots els que aconseguirà la feina feta.

151
00:08:17,930 --> 00:08:21,200
Què passa si vostè tenia un arbre on cada
node va tenir tres fills,

152
00:08:21,200 --> 00:08:23,100
Esquerra, Centre i Dreta?

153
00:08:23,100 --> 00:08:24,886
Com editar foo?

154
00:08:24,886 --> 00:08:25,860
Bé, simple.

155
00:08:25,860 --> 00:08:30,250
Només ha d'afegir una altra crida recursiva i
passi el punter del node intermedi.

156
00:08:30,250 --> 00:08:34,549
>> La recursivitat és molt potent i no
esmenta elegant, però pot ser un

157
00:08:34,549 --> 00:08:38,010
difícil concepte al principi, així que
pacient i prengui el seu temps.

158
00:08:38,010 --> 00:08:39,370
Comenceu amb el cas base.

159
00:08:39,370 --> 00:08:42,650
En general és la més fàcil d'identificar,
i llavors vostè pot treballar

160
00:08:42,650 --> 00:08:43,830
cap enrere des d'allà.

161
00:08:43,830 --> 00:08:46,190
Vostè sap que necessita per arribar al seu
cas base, de manera que el poder

162
00:08:46,190 --> 00:08:47,760
donar-li alguns consells.

163
00:08:47,760 --> 00:08:53,120
Intenta expressar un cas específic en
termes d'altres causes o en sub-conjunts.

164
00:08:53,120 --> 00:08:54,700
>> Gràcies per veure aquest curt.

165
00:08:54,700 --> 00:08:58,920
Si més no, ara pot fer-ho
entendre acudits com aquest.

166
00:08:58,920 --> 00:09:01,250
El meu nom és Zamyla, i això és CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Prengui aquesta funció, hi un
void funció que pren

169
00:09:07,170 --> 00:09:09,212
01:00 int, n, com a entrada.

170
00:09:09,212 --> 00:09:11,020
El cas base és el primer.

171
00:09:11,020 --> 00:09:14,240
Si n és menor que 0, imprimir
"Bye" i el retorn.

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