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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Al fine di comprendere
ricorsione, è necessario

3
00:00:10,190 --> 00:00:13,820
prima capire la ricorsione.

4
00:00:13,820 --> 00:00:17,280
Avendo ricorsione in programma mezzi di progettazione
che si deve auto-referenziale

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

6
00:00:18,570 --> 00:00:21,520
Strutture dati ricorsive, per esempio,
sono strutture di dati che

7
00:00:21,520 --> 00:00:23,990
si comprenderà in
loro definizioni.

8
00:00:23,990 --> 00:00:27,160
Ma oggi, stiamo andando a fuoco
sulle funzioni ricorsive.

9
00:00:27,160 --> 00:00:31,160
>> Ricordiamo che funzioni accettano ingressi,
argomenti e restituire un valore come loro

10
00:00:31,160 --> 00:00:34,480
uscita rappresentata dalla
questo diagramma qui.

11
00:00:34,480 --> 00:00:38,060
Penseremo della scatola come il corpo di
la funzione contenente il gruppo di

12
00:00:38,060 --> 00:00:42,340
istruzioni che interpretano il
input e fornire un'uscita.

13
00:00:42,340 --> 00:00:45,660
Dando un'occhiata più da vicino all'interno del corpo di
la funzione potrebbe rivelare chiamate

14
00:00:45,660 --> 00:00:47,430
altre funzioni.

15
00:00:47,430 --> 00:00:51,300
Prendete questa semplice funzione, foo, che
prende una singola stringa come input e

16
00:00:51,300 --> 00:00:54,630
Stampe quante lettere
che la stringa ha.

17
00:00:54,630 --> 00:00:58,490
La funzione strlen, per la lunghezza della stringa,
è chiamato, la cui uscita è

18
00:00:58,490 --> 00:01:01,890
richiesto per la chiamata a printf.

19
00:01:01,890 --> 00:01:05,770
>> Ora, ciò che rende una funzione ricorsiva
speciale è che si chiama.

20
00:01:05,770 --> 00:01:09,610
Possiamo rappresentare questa ricorsiva
chiamare con questo freccia arancione

21
00:01:09,610 --> 00:01:11,360
di tornare a se stesso.

22
00:01:11,360 --> 00:01:15,630
Ma l'esecuzione di sé ancora una volta solo sarà
effettuare un'altra chiamata ricorsiva, e

23
00:01:15,630 --> 00:01:17,150
altro e un altro.

24
00:01:17,150 --> 00:01:19,100
Ma le funzioni ricorsive
non può essere infinito.

25
00:01:19,100 --> 00:01:23,490
Devono finire in qualche modo, o il vostro
programma verrà eseguito sempre.

26
00:01:23,490 --> 00:01:27,680
>> Quindi abbiamo bisogno di trovare un modo per rompere
fuori delle chiamate ricorsive.

27
00:01:27,680 --> 00:01:29,900
Noi chiamiamo questo il caso base.

28
00:01:29,900 --> 00:01:33,570
Quando la condizione caso base è soddisfatta,
la funzione restituisce senza fare

29
00:01:33,570 --> 00:01:34,950
un'altra chiamata ricorsiva.

30
00:01:34,950 --> 00:01:39,610
Prendete questa funzione, hi, una funzione void
che prende un int n come input.

31
00:01:39,610 --> 00:01:41,260
Il caso base viene prima.

32
00:01:41,260 --> 00:01:46,220
Se n è minore di zero, bye stampa e
ritorno Per tutti gli altri casi, l'

33
00:01:46,220 --> 00:01:49,400
funzione di stampa hi ed eseguire
la chiamata ricorsiva.

34
00:01:49,400 --> 00:01:53,600
Un'altra chiamata alla funzione hi con
un valore di ingresso decrementato.

35
00:01:53,600 --> 00:01:56,790
>> Ora, anche se stampiamo ciao, l'
funzione non terminerà fino a quando

36
00:01:56,790 --> 00:02:00,370
ritorno il tipo restituito,
in questo caso vuoto.

37
00:02:00,370 --> 00:02:04,830
Quindi per ogni n diverso il caso base,
questa funzione hi tornerà hi

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

39
00:02:06,890 --> 00:02:10,050
Poiché questa funzione è nulla, però, siamo
non esplicitamente digitare ritorno qui.

40
00:02:10,050 --> 00:02:12,000
Ti basta eseguire la funzione.

41
00:02:12,000 --> 00:02:16,960
Così chiamata hi (3) stampa ciao e
eseguire hi (2) che esegue hi (1) una

42
00:02:16,960 --> 00:02:20,560
che esegue hi (0), in cui la
condizione di scenario di base è soddisfatta.

43
00:02:20,560 --> 00:02:24,100
Così hi (0) stampa bye e ritorna.

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

45
00:02:24,990 --> 00:02:28,690
Quindi, ora che abbiamo capito le basi del
funzioni ricorsive, che hanno bisogno

46
00:02:28,690 --> 00:02:32,730
almeno un caso base e un
chiamata ricorsiva, passiamo ad un

47
00:02:32,730 --> 00:02:34,120
esempio più significativo.

48
00:02:34,120 --> 00:02:37,830
Uno che non si limita a tornare
annullare qualunque cosa.

49
00:02:37,830 --> 00:02:41,340
>> Diamo uno sguardo al fattoriale
funzionamento più comunemente utilizzato in

50
00:02:41,340 --> 00:02:43,660
calcolo delle probabilità.

51
00:02:43,660 --> 00:02:48,120
Fattoriale di n è il prodotto di ogni
numero intero positivo inferiore

52
00:02:48,120 --> 00:02:49,400
e pari a n.

53
00:02:49,400 --> 00:02:56,731
Così cinque fattoriale è 5 volte 4 volte
3 volte 2 volte 1 per dare 120.

54
00:02:56,731 --> 00:03:01,400
Quattro fattoriale è 4 volte 3 volte
2 volte 1 per dare 24.

55
00:03:01,400 --> 00:03:04,910
E vale la stessa regola
qualsiasi numero intero positivo.

56
00:03:04,910 --> 00:03:08,670
>> Così come potremmo scrivere un ricorsiva
funzione che calcola il fattoriale

57
00:03:08,670 --> 00:03:09,960
di un numero?

58
00:03:09,960 --> 00:03:14,700
Bene, abbiamo bisogno di identificare sia l'
caso base e la chiamata ricorsiva.

59
00:03:14,700 --> 00:03:18,250
La chiamata ricorsiva sarà lo stesso
per tutti i casi, eccetto per la base

60
00:03:18,250 --> 00:03:21,420
caso, il che significa che dovremo
trovare un modello che ci darà il nostro

61
00:03:21,420 --> 00:03:23,350
risultato desiderato.

62
00:03:23,350 --> 00:03:30,270
>> Per questo esempio, vedere come 5 fattoriale
coinvolge moltiplicando 4 da 3 per 2 per 1

63
00:03:30,270 --> 00:03:33,010
E quella stessa moltiplicazione
si trova qui, l'

64
00:03:33,010 --> 00:03:35,430
definizione di 4 fattoriale.

65
00:03:35,430 --> 00:03:39,810
Così vediamo che 5 fattoriale è
a soli 5 volte 4 fattoriale.

66
00:03:39,810 --> 00:03:43,360
Ora si applica questo modello
4 fattoriale così?

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

68
00:03:44,280 --> 00:03:49,120
Vediamo che 4 fattoriale contiene il
moltiplicazione 3 volte 2 volte 1, la

69
00:03:49,120 --> 00:03:51,590
stessa definizione, 3 fattoriale.

70
00:03:51,590 --> 00:03:56,950
Quindi 4 fattoriale è pari a 4 volte 3
fattoriale, e così via e così via il nostro

71
00:03:56,950 --> 00:04:02,170
modello bastoni fino al 1 fattoriale, che
per definizione è uguale a 1.

72
00:04:02,170 --> 00:04:04,950
>> Non c'è nessun altro positivo
interi sinistra.

73
00:04:04,950 --> 00:04:07,870
Così abbiamo il modello per
la nostra chiamata ricorsiva.

74
00:04:07,870 --> 00:04:13,260
n fattoriale è pari a n volte
il fattoriale di n meno 1.

75
00:04:13,260 --> 00:04:14,370
E il nostro caso base?

76
00:04:14,370 --> 00:04:17,370
Questo sarà solo la nostra definizione
di 1 fattoriale.

77
00:04:17,370 --> 00:04:19,995
>> Così ora possiamo passare alla scrittura
codice per la funzione.

78
00:04:19,995 --> 00:04:24,110
Per il caso base, avremo l'
condizione n è uguale uguale a 1, dove

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

80
00:04:25,780 --> 00:04:29,280
Poi di passare la chiamata ricorsiva,
torneremo n volte l'

81
00:04:29,280 --> 00:04:32,180
fattoriale di n meno 1.

82
00:04:32,180 --> 00:04:33,590
>> Ora cerchiamo di testare questa nostra.

83
00:04:33,590 --> 00:04:35,900
Proviamo fattoriale 4.

84
00:04:35,900 --> 00:04:39,420
Per la nostra funzione è uguale
per 4 volte fattoriale (3).

85
00:04:39,420 --> 00:04:43,040
Fattoriale (3) è pari a
3 volte fattoriali (2).

86
00:04:43,040 --> 00:04:48,700
Fattoriale (2) è pari a 2 volte
fattoriale (1), che restituisce 1.

87
00:04:48,700 --> 00:04:52,490
Fattoriale (2) restituisce ora 2 volte 1, 2.

88
00:04:52,490 --> 00:04:55,960
Fattoriale (3) ora può tornare
3 volte 2, 6.

89
00:04:55,960 --> 00:05:02,490
E, infine, fattoriale (4)
restituisce 4 volte 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Se stai incontrando difficoltà
con la chiamata ricorsiva, fingere che

91
00:05:06,780 --> 00:05:09,660
la funzione funziona già.

92
00:05:09,660 --> 00:05:13,450
Quello che voglio dire è che si dovrebbe
fiducia le chiamate ricorsive di ritorno

93
00:05:13,450 --> 00:05:15,100
i giusti valori.

94
00:05:15,100 --> 00:05:18,960
Per esempio, se so che
fattoriale (5) è pari a 5 volte

95
00:05:18,960 --> 00:05:24,870
fattoriale (4), ho intenzione di fiducia che
fattoriale (4), mi darà 24.

96
00:05:24,870 --> 00:05:28,510
Pensate a come una variabile, se si
sarà, come se già definito

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

98
00:05:30,070 --> 00:05:33,850
Quindi per qualsiasi fattoriale (n), è
il prodotto di n e

99
00:05:33,850 --> 00:05:35,360
il fattoriale precedente.

100
00:05:35,360 --> 00:05:38,130
E questo precedente fattoriale
viene ottenuto chiamando

101
00:05:38,130 --> 00:05:41,330
fattoriale di n meno 1.

102
00:05:41,330 --> 00:05:45,130
>> Ora, vedere se è possibile implementare un
ricorsiva funzionare da soli.

103
00:05:45,130 --> 00:05:50,490
Caricare il terminale, o run.cs50.net,
e scrivere una somma funzione

104
00:05:50,490 --> 00:05:54,770
che prende un intero n e restituisce il
somma di tutti positivi consecutivi

105
00:05:54,770 --> 00:05:57,490
interi da n a 1.

106
00:05:57,490 --> 00:06:01,000
Ho scritto le somme di una certa
I valori per aiutarti nostra.

107
00:06:01,000 --> 00:06:04,030
In primo luogo, capire il
stato scenario di base.

108
00:06:04,030 --> 00:06:06,170
Poi, guarda sum (5).

109
00:06:06,170 --> 00:06:09,270
Si può esprimere in termini
di un'altra somma?

110
00:06:09,270 --> 00:06:11,290
Ora, che dire sum (4)?

111
00:06:11,290 --> 00:06:15,630
Come si può esprimere sum (4)
in termini di un'altra somma?

112
00:06:15,630 --> 00:06:19,655
>> Una volta che avete sum (5) e sum (4)
espressa in termini di altre somme, vedere

113
00:06:19,655 --> 00:06:22,970
se è possibile identificare un
modello per la somma (n).

114
00:06:22,970 --> 00:06:26,190
In caso contrario, provare alcuni altri numeri
ed esprimere le proprie somme in

115
00:06:26,190 --> 00:06:28,410
termini di un altro numero.

116
00:06:28,410 --> 00:06:31,930
Identificando modelli di discreta
numeri, siete sulla buona strada per

117
00:06:31,930 --> 00:06:34,320
identificare il modello per ogni n.

118
00:06:34,320 --> 00:06:38,040
>> La ricorsione è uno strumento davvero potente,
così naturalmente non è limitato a

119
00:06:38,040 --> 00:06:39,820
funzioni matematiche.

120
00:06:39,820 --> 00:06:44,040
La ricorsione può essere utilizzato in modo molto efficace
quando si tratta di alberi, per esempio.

121
00:06:44,040 --> 00:06:47,210
Scopri la breve sugli alberi per un
più approfondito esame, ma per ora

122
00:06:47,210 --> 00:06:51,140
ricordare che gli alberi binari di ricerca, in
particolare, sono costituiti da nodi, ciascuno

123
00:06:51,140 --> 00:06:53,820
con un valore e due puntatori nodo.

124
00:06:53,820 --> 00:06:57,270
Di solito, questo è rappresentato dal
nodo padre con una linea di puntamento

125
00:06:57,270 --> 00:07:01,870
al nodo figlio sinistro e uno
al nodo figlio destro.

126
00:07:01,870 --> 00:07:04,510
La struttura di una ricerca binaria
albero si presta bene

127
00:07:04,510 --> 00:07:05,940
ad una ricerca ricorsiva.

128
00:07:05,940 --> 00:07:09,730
La chiamata ricorsiva passa sia nella
sinistra o destra del nodo, ma più

129
00:07:09,730 --> 00:07:10,950
di che nel breve albero.

130
00:07:10,950 --> 00:07:15,690
>> Dire che si desidera eseguire un'operazione su
ogni singolo nodo in un albero binario.

131
00:07:15,690 --> 00:07:17,410
Come si potrebbe fare per questo?

132
00:07:17,410 --> 00:07:20,600
Beh, si potrebbe scrivere un ricorsiva
funzione che esegue l'operazione

133
00:07:20,600 --> 00:07:24,450
sul nodo padre e fa un ricorsiva
chiamare per la stessa funzione,

134
00:07:24,450 --> 00:07:27,630
passando sinistra e
nodi figlio destro.

135
00:07:27,630 --> 00:07:31,650
Ad esempio, questa funzione foo, che
modifica il valore di un dato nodo e

136
00:07:31,650 --> 00:07:33,830
tutti i suoi figli a 1.

137
00:07:33,830 --> 00:07:37,400
Il caso base di un valore NULL cause nodo
la funzione di tornare, indicando

138
00:07:37,400 --> 00:07:41,290
che non ci sono nodi
lasciato in quella sub-tree.

139
00:07:41,290 --> 00:07:42,620
>> Camminiamo attraverso di essa.

140
00:07:42,620 --> 00:07:44,340
Il primo genitore è 13.

141
00:07:44,340 --> 00:07:47,930
Cambiamo il valore di 1, e quindi chiamare
la nostra funzione sulla sinistra e

142
00:07:47,930 --> 00:07:49,600
come il diritto.

143
00:07:49,600 --> 00:07:53,910
La funzione foo, è chiamato a sinistra
sub-tree prima, in modo che il nodo di sinistra

144
00:07:53,910 --> 00:07:57,730
saranno riassegnate a 1 e foo sarà
essere chiamati figli di quel nodo,

145
00:07:57,730 --> 00:08:01,900
prima sinistra e poi destra,
e così via e così via.

146
00:08:01,900 --> 00:08:05,630
E dire loro che i rami non hanno
qualsiasi più bambini così lo stesso processo

147
00:08:05,630 --> 00:08:09,700
proseguirà per i bambini giuste
fino a quando i nodi dell'intero albero sono

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

149
00:08:11,430 --> 00:08:15,390
>> Come si può vedere, non si sono limitati
ad una sola chiamata ricorsiva.

150
00:08:15,390 --> 00:08:17,930
Proprio come molti come otterrà il lavoro fatto.

151
00:08:17,930 --> 00:08:21,200
E se aveste un albero dove ogni
nodo aveva tre figli,

152
00:08:21,200 --> 00:08:23,100
Sinistra, centro e destra?

153
00:08:23,100 --> 00:08:24,886
Come si potrebbe modificare foo?

154
00:08:24,886 --> 00:08:25,860
Beh, semplice.

155
00:08:25,860 --> 00:08:30,250
Basta aggiungere un'altra chiamata ricorsiva e
passare il puntatore nodo centrale.

156
00:08:30,250 --> 00:08:34,549
>> La ricorsione è molto potente e non
menziona elegante, ma può essere un

157
00:08:34,549 --> 00:08:38,010
concetto difficile in un primo momento, in modo da essere
paziente e prendere il vostro tempo.

158
00:08:38,010 --> 00:08:39,370
Inizia con il caso base.

159
00:08:39,370 --> 00:08:42,650
Di solito il più facile da identificare,
e poi si può lavorare

160
00:08:42,650 --> 00:08:43,830
indietro da lì.

161
00:08:43,830 --> 00:08:46,190
Sai che è necessario per raggiungere il tuo
scenario di base, in modo che la forza

162
00:08:46,190 --> 00:08:47,760
vi darò alcuni suggerimenti.

163
00:08:47,760 --> 00:08:53,120
Cercate di esprimere un caso specifico
termini di altri casi, o in sottoinsiemi.

164
00:08:53,120 --> 00:08:54,700
>> Grazie per guardare questo breve.

165
00:08:54,700 --> 00:08:58,920
Per lo meno, ora è possibile
capire gli scherzi come questo.

166
00:08:58,920 --> 00:09:01,250
Il mio nome è Zamyla, e questo è CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Prendete questa funzione, ciao, un
funzione di vuoto che prende

169
00:09:07,170 --> 00:09:09,212
un int, n, come input.

170
00:09:09,212 --> 00:09:11,020
Il caso base viene prima.

171
00:09:11,020 --> 00:09:14,240
Se n è minore di 0, stampa
"Bye" e ritorno.

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