1
00:00:00,000 --> 00:00:05,860
>> [RIPRODUZIONE DI BRANI MUSICALI]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Probabilmente pensate che
codice è solo utilizzato per eseguire un compito.

3
00:00:09,530 --> 00:00:10,450
Si scrive fuori.

4
00:00:10,450 --> 00:00:11,664
Si fa qualcosa.

5
00:00:11,664 --> 00:00:12,580
Che è praticamente esso.

6
00:00:12,580 --> 00:00:13,160
>> Si compila.

7
00:00:13,160 --> 00:00:13,993
Si esegue il programma.

8
00:00:13,993 --> 00:00:15,370
Tu sei a posto.

9
00:00:15,370 --> 00:00:17,520
>> Ma che ci crediate o no, se
si codifica per un lungo periodo di tempo,

10
00:00:17,520 --> 00:00:20,550
in realtà si potrebbe venire a vedere
codice come qualcosa che è bello.

11
00:00:20,550 --> 00:00:23,275
Risolve un problema in
un modo molto interessante,

12
00:00:23,275 --> 00:00:26,510
o c'è solo qualcosa di veramente
accurata circa il suo aspetto.

13
00:00:26,510 --> 00:00:28,750
Si potrebbe ridere
a me, ma è vero.

14
00:00:28,750 --> 00:00:31,530
E ricorsione è un modo
per una sorta di ottenere questa idea

15
00:00:31,530 --> 00:00:34,090
di bello, codice elegante aspetto.

16
00:00:34,090 --> 00:00:37,740
Risolve i problemi in modi che
sono interessanti, facile da visualizzare,

17
00:00:37,740 --> 00:00:39,810
e sorprendentemente breve.

18
00:00:39,810 --> 00:00:43,190
>> Le opere modo ricorsione
è una funzione ricorsiva

19
00:00:43,190 --> 00:00:49,291
è definita come una funzione che chiama
sé come parte della sua esecuzione.

20
00:00:49,291 --> 00:00:51,790
Questo potrebbe sembrare un po 'strano,
e vedremo un po '

21
00:00:51,790 --> 00:00:53,750
su come funziona in un attimo.

22
00:00:53,750 --> 00:00:55,560
Ma ancora una volta, si tratta
procedure ricorsive sono

23
00:00:55,560 --> 00:00:57,730
sta per essere così elegante
perché stanno andando

24
00:00:57,730 --> 00:01:00,410
per risolvere questo problema senza
avendo tutte queste altre funzioni

25
00:01:00,410 --> 00:01:02,710
o questi lunghi cicli.

26
00:01:02,710 --> 00:01:06,310
Vedrai che questi ricorsiva
le procedure stanno andando a guardare così breve.

27
00:01:06,310 --> 00:01:10,610
E hanno davvero intenzione di fare
il codice aspetto molto più bello.

28
00:01:10,610 --> 00:01:12,560
>> Vi darò un esempio
di questo per vedere come

29
00:01:12,560 --> 00:01:14,880
una procedura ricorsiva potrebbe essere definito.

30
00:01:14,880 --> 00:01:18,202
Quindi, se si ha familiarità con questo
dalla classe di matematica molti anni fa,

31
00:01:18,202 --> 00:01:20,910
c'è qualcosa chiamato il
funzione fattoriale, che è di solito

32
00:01:20,910 --> 00:01:25,340
indicato come un punto esclamativo, che
è definito su tutti gli interi positivi.

33
00:01:25,340 --> 00:01:28,850
E il modo in cui n
fattoriale viene calcolato

34
00:01:28,850 --> 00:01:31,050
è si moltiplicano tutti
i numeri meno

35
00:01:31,050 --> 00:01:33,750
o uguale together-- n
tutti gli interi meno

36
00:01:33,750 --> 00:01:34,880
o uguale a n insieme.

37
00:01:34,880 --> 00:01:39,850
>> Quindi 5 fattoriale è 5 volte
4 volte 3 volte 2 volte 1.

38
00:01:39,850 --> 00:01:43,020
E 4 fattoriale è 4 volte
3 volte 2 volte 1 e così via.

39
00:01:43,020 --> 00:01:44,800
Si ottiene l'idea.

40
00:01:44,800 --> 00:01:47,060
>> Mentre i programmatori, non lo facciamo
utilizzare n, punto esclamativo.

41
00:01:47,060 --> 00:01:51,840
Quindi dovremo definire il fattoriale
funzione di realtà di n.

42
00:01:51,840 --> 00:01:56,897
E useremo fattoriale per creare
una soluzione ricorsiva di un problema.

43
00:01:56,897 --> 00:01:59,230
E penso che si potrebbe trovare
che è molto più visivamente

44
00:01:59,230 --> 00:02:02,380
appello che l'iterativo
versione di questo, che

45
00:02:02,380 --> 00:02:05,010
ci sarà anche uno sguardo a in un attimo.

46
00:02:05,010 --> 00:02:08,310
>> Quindi, ecco un paio di
gioco di parole facts-- intended--

47
00:02:08,310 --> 00:02:10,169
factorial-- sulla
funzione fattoriale.

48
00:02:10,169 --> 00:02:13,090
Il fattoriale di 1, come ho detto, è di 1.

49
00:02:13,090 --> 00:02:15,690
Il fattoriale di 2 è 2 volte 1.

50
00:02:15,690 --> 00:02:18,470
Il fattoriale di 3 è 3
per 2 per 1, e così via.

51
00:02:18,470 --> 00:02:20,810
Abbiamo parlato di 4 e 5 già.

52
00:02:20,810 --> 00:02:23,940
>> Ma guardando questo, non è vero?

53
00:02:23,940 --> 00:02:28,220
Non è fattoriale di 2 soli
2 volte il fattoriale di 1?

54
00:02:28,220 --> 00:02:31,130
Voglio dire, il fattoriale di 1 a 1.

55
00:02:31,130 --> 00:02:34,940
Allora, perché non possiamo solo dire che,
poiché fattoriale di 2 è 2 volte 1,

56
00:02:34,940 --> 00:02:38,520
E 'davvero solo 2 volte
il fattoriale di 1?

57
00:02:38,520 --> 00:02:40,900
>> E poi estendere tale idea,
Non è il fattoriale di 3

58
00:02:40,900 --> 00:02:44,080
solo 3 volte il fattoriale di 2?

59
00:02:44,080 --> 00:02:50,350
E il fattoriale di 4 è 4 volte
il fattoriale di 3, e così via?

60
00:02:50,350 --> 00:02:52,530
Infatti, il fattoriale
di un qualsiasi numero può solo

61
00:02:52,530 --> 00:02:54,660
essere espressa se noi genere
di portare questo fuori per sempre.

62
00:02:54,660 --> 00:02:56,870
Possiamo tipo di generalizzare
il problema fattoriale

63
00:02:56,870 --> 00:02:59,910
Come è N volte il
fattoriale di n meno 1.

64
00:02:59,910 --> 00:03:04,840
E 'n volte il prodotto
tutti i numeri meno di me.

65
00:03:04,840 --> 00:03:08,890
>> Questa idea, questo
generalizzazione del problema,

66
00:03:08,890 --> 00:03:13,410
ci permette in modo ricorsivo
definire la funzione fattoriale.

67
00:03:13,410 --> 00:03:15,440
Quando si definisce una funzione
ricorsivamente, c'è

68
00:03:15,440 --> 00:03:17,470
due cose che devono essere una parte di esso.

69
00:03:17,470 --> 00:03:20,990
È necessario disporre di qualcosa chiamato un
scenario di base, i quali, quando si attiva esso,

70
00:03:20,990 --> 00:03:22,480
si fermerà il processo ricorsivo.

71
00:03:22,480 --> 00:03:25,300
>> Altrimenti, una funzione che chiama
itself-- come si potrebbe imagine--

72
00:03:25,300 --> 00:03:26,870
potrebbe andare avanti per sempre.

73
00:03:26,870 --> 00:03:29,047
Funzione chiama la funzione
invita le chiamate di funzione

74
00:03:29,047 --> 00:03:30,380
la funzione chiama la funzione.

75
00:03:30,380 --> 00:03:32,380
Se non si dispone di un modo
per fermarlo, il programma

76
00:03:32,380 --> 00:03:34,760
saranno effettivamente bloccato
in un ciclo infinito.

77
00:03:34,760 --> 00:03:37,176
Si andrà in crash alla fine,
perché sarà a corto di memoria.

78
00:03:37,176 --> 00:03:38,990
Ma non è questo il punto.

79
00:03:38,990 --> 00:03:42,210
>> Abbiamo bisogno di avere qualche altro modo per fermare
cose oltre il nostro programma di crash,

80
00:03:42,210 --> 00:03:46,010
perché un programma che si blocca è
probabilmente non bello o elegante.

81
00:03:46,010 --> 00:03:47,690
E così noi chiamiamo questo il caso base.

82
00:03:47,690 --> 00:03:50,610
Questa è una soluzione semplice
ad un problema che ferma

83
00:03:50,610 --> 00:03:52,770
il processo ricorsivo di verificarsi.

84
00:03:52,770 --> 00:03:55,220
Ecco, questo è una parte del
una funzione ricorsiva.

85
00:03:55,220 --> 00:03:56,820
>> La seconda parte è il caso ricorsivo.

86
00:03:56,820 --> 00:03:59,195
Ed è qui che la ricorsione
avrà effettivamente luogo.

87
00:03:59,195 --> 00:04:02,200
Questo è dove il
Funzione chiamerà se stesso.

88
00:04:02,200 --> 00:04:05,940
>> Non si chiamerà esattamente
allo stesso modo è stato chiamato.

89
00:04:05,940 --> 00:04:08,880
Sarà una piccola variazione
che rende il problema è

90
00:04:08,880 --> 00:04:11,497
cercando di risolvere un pochino più piccolo.

91
00:04:11,497 --> 00:04:14,330
Ma generalmente passa il dollaro
di risolvere il grosso della soluzione

92
00:04:14,330 --> 00:04:17,450
ad una chiamata differente lungo la linea.

93
00:04:17,450 --> 00:04:20,290
>> Quale di questi sguardi
come il caso base qui?

94
00:04:20,290 --> 00:04:25,384
Quale di questi sguardi, come la
soluzione più semplice per un problema?

95
00:04:25,384 --> 00:04:27,550
Abbiamo un po 'di fattoriali,
e si potrebbe continuare

96
00:04:27,550 --> 00:04:30,470
andando on-- 6, 7, 8, 9, 10, e così via.

97
00:04:30,470 --> 00:04:34,130
>> Ma uno di questi sembra una
buon caso per essere il caso base.

98
00:04:34,130 --> 00:04:35,310
È una soluzione molto semplice.

99
00:04:35,310 --> 00:04:37,810
Noi non dobbiamo fare nulla di speciale.

100
00:04:37,810 --> 00:04:40,560
>> Il fattoriale di 1 si trova a 1.

101
00:04:40,560 --> 00:04:42,790
Non abbiamo a che fare ogni
moltiplicazione affatto.

102
00:04:42,790 --> 00:04:45,248
Sembra come se stiamo andando
per cercare di risolvere questo problema,

103
00:04:45,248 --> 00:04:47,600
e abbiamo bisogno di fermare il
ricorsione da qualche parte,

104
00:04:47,600 --> 00:04:50,610
probabilmente vogliamo fermare
quando si arriva a 1.

105
00:04:50,610 --> 00:04:54,580
Noi non vogliamo fermare prima.

106
00:04:54,580 --> 00:04:56,660
>> Quindi, se stiamo definendo
la nostra funzione fattoriale,

107
00:04:56,660 --> 00:04:58,690
qui è uno scheletro per
come potremmo farlo.

108
00:04:58,690 --> 00:05:03,110
Abbiamo bisogno di collegare quei due things--
il caso base e nel caso ricorsivo.

109
00:05:03,110 --> 00:05:04,990
Qual è il caso base?

110
00:05:04,990 --> 00:05:10,150
Se n è uguale a 1, questo è tornare 1--
davvero un problema semplice da risolvere.

111
00:05:10,150 --> 00:05:11,890
>> Il fattoriale di 1 a 1.

112
00:05:11,890 --> 00:05:13,860
Non è 1 volte nulla.

113
00:05:13,860 --> 00:05:15,020
E 'solo uno.

114
00:05:15,020 --> 00:05:17,170
E 'un fatto molto semplice.

115
00:05:17,170 --> 00:05:19,620
E così che può essere il nostro caso base.

116
00:05:19,620 --> 00:05:24,730
Se ci passati 1 in questo
la funzione, ci limiteremo a ritorniamo 1.

117
00:05:24,730 --> 00:05:27,320
>> Qual è il ricorsiva
caso probabilmente assomigliare?

118
00:05:27,320 --> 00:05:32,445
Per ogni altro numero
oltre 1, qual è il motivo?

119
00:05:32,445 --> 00:05:35,780
Beh, se ci stiamo prendendo
il fattoriale di n,

120
00:05:35,780 --> 00:05:38,160
E 'n volte il fattoriale di n meno 1.

121
00:05:38,160 --> 00:05:42,130
>> Se ci stiamo prendendo il fattoriale di 3,
è 3 volte il fattoriale di 3 meno 1,

122
00:05:42,130 --> 00:05:43,070
o 2.

123
00:05:43,070 --> 00:05:47,330
E così, se non siamo
guardando 1, altrimenti

124
00:05:47,330 --> 00:05:51,710
ritorno N volte il
fattoriale di n meno 1.

125
00:05:51,710 --> 00:05:53,210
E 'piuttosto semplice.

126
00:05:53,210 --> 00:05:57,360
>> E per il gusto di avere un po '
più pulito e più elegante codice,

127
00:05:57,360 --> 00:06:01,440
sapere che se abbiamo loop a linea singola
o riga singola rami condizionali,

128
00:06:01,440 --> 00:06:04,490
possiamo sbarazzarci di tutto quanto
parentesi graffe intorno a loro.

129
00:06:04,490 --> 00:06:06,850
Così possiamo consolidare questo a questo.

130
00:06:06,850 --> 00:06:09,640
Questo ha esattamente la stessa
funzionalità questo.

131
00:06:09,640 --> 00:06:13,850
>> Sto solo togliendo il riccio
bretelle, perché c'è solo una linea

132
00:06:13,850 --> 00:06:18,500
all'interno di quei rami condizionali.

133
00:06:18,500 --> 00:06:21,160
Quindi questi si comportano in modo identico.

134
00:06:21,160 --> 00:06:23,800
Se n è uguale a 1, 1 ritorno.

135
00:06:23,800 --> 00:06:28,351
In caso contrario, tornare n volte
il fattoriale di n meno 1.

136
00:06:28,351 --> 00:06:29,850
Quindi stiamo rendendo il problema più piccolo.

137
00:06:29,850 --> 00:06:33,850
Se n inizia come 5, stiamo andando a
ritorno 5 volte il fattoriale di 4.

138
00:06:33,850 --> 00:06:37,100
E vedremo tra un minuto quando si parla
sulla stack-- chiamata in un altro video

139
00:06:37,100 --> 00:06:39,390
dove si parla di
chiamare stack-- impareremo

140
00:06:39,390 --> 00:06:41,630
sul perché esattamente questo processo funziona.

141
00:06:41,630 --> 00:06:46,970
>> Ma mentre fattoriale di 5 dice
ritorno 5 volte fattoriale di 4, e 4

142
00:06:46,970 --> 00:06:49,710
sta per dire, OK, bene, il ritorno
4 volte il fattoriale di 3.

143
00:06:49,710 --> 00:06:51,737
E come potete vedere, siamo
sorta di avvicinamento 1.

144
00:06:51,737 --> 00:06:53,820
Ci stiamo avvicinando e
più simile a quella del caso base.

145
00:06:53,820 --> 00:06:58,180
>> E una volta ci ha colpito il caso base,
tutte le funzioni precedenti

146
00:06:58,180 --> 00:07:00,540
avere la risposta che cercavano.

147
00:07:00,540 --> 00:07:03,900
Fattoriale di 2 diceva ritorno
2 volte il fattoriale di 1.

148
00:07:03,900 --> 00:07:06,760
Beh, fattoriale di 1 restituisce 1.

149
00:07:06,760 --> 00:07:10,090
Quindi l'invito a fattoriale
di 2 può restituire 2 volte 1,

150
00:07:10,090 --> 00:07:13,980
e dare che torna a fattoriale di
3, che è attesa per quel risultato.

151
00:07:13,980 --> 00:07:17,110
>> E allora può calcolare
Il suo risultato, 3 volte 2 è 6,

152
00:07:17,110 --> 00:07:18,907
e dare di nuovo al fattoriale di 4.

153
00:07:18,907 --> 00:07:20,740
E ancora, abbiamo un
video sul stack di chiamate

154
00:07:20,740 --> 00:07:23,810
dove ciò è illustrato un po '
più di quello che sto dicendo adesso.

155
00:07:23,810 --> 00:07:25,300
Ma è proprio questo.

156
00:07:25,300 --> 00:07:29,300
Questo da solo è la soluzione ai
calcolare il fattoriale di un numero.

157
00:07:29,300 --> 00:07:31,527
>> È solo quattro righe di codice.

158
00:07:31,527 --> 00:07:32,610
Che è abbastanza freddo, giusto?

159
00:07:32,610 --> 00:07:35,480
È un po 'sexy.

160
00:07:35,480 --> 00:07:38,580
>> Quindi, in generale, ma non
sempre, una funzione ricorsiva

161
00:07:38,580 --> 00:07:41,190
può sostituire un loop in un
Funzione non ricorsiva.

162
00:07:41,190 --> 00:07:46,100
Così qui, fianco a fianco, è l'iterativo
versione della funzione fattoriale.

163
00:07:46,100 --> 00:07:49,650
Entrambi questi calculate
esattamente la stessa cosa.

164
00:07:49,650 --> 00:07:52,170
>> Entrambi calcolare il fattoriale di n.

165
00:07:52,170 --> 00:07:54,990
La versione a sinistra
utilizza la ricorsione per farlo.

166
00:07:54,990 --> 00:07:58,320
La versione a destra
utilizza l'iterazione di farlo.

167
00:07:58,320 --> 00:08:02,050
>> E notate, dobbiamo dichiarare
una variabile un prodotto intero.

168
00:08:02,050 --> 00:08:02,940
E poi abbiamo ciclo.

169
00:08:02,940 --> 00:08:06,790
Finché n è maggiore di 0, si
tenere moltiplicando tale prodotto n

170
00:08:06,790 --> 00:08:09,890
e decremento n fino a
calcoliamo il prodotto.

171
00:08:09,890 --> 00:08:14,600
Quindi queste due funzioni, di nuovo,
fare esattamente la stessa cosa.

172
00:08:14,600 --> 00:08:19,980
Ma non fanno in
esattamente nello stesso modo.

173
00:08:19,980 --> 00:08:22,430
>> Ora, è possibile
avere più di una base

174
00:08:22,430 --> 00:08:25,770
caso o più
caso ricorsivo, a seconda

175
00:08:25,770 --> 00:08:27,670
su ciò che la funzione sta cercando di fare.

176
00:08:27,670 --> 00:08:31,650
Lei non è necessariamente solo limitati a
un singolo caso di base o di un singolo ricorsivo

177
00:08:31,650 --> 00:08:32,370
caso.

178
00:08:32,370 --> 00:08:35,320
Così un esempio di qualcosa
con casi multipli di base

179
00:08:35,320 --> 00:08:37,830
potrebbe essere il questo--
Sequenza numerica di Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Si può ricordare da
giorni di scuola elementare

181
00:08:41,549 --> 00:08:45,740
che la sequenza di Fibonacci è definita
come questo-- il primo elemento è 0.

182
00:08:45,740 --> 00:08:46,890
Il secondo elemento è 1.

183
00:08:46,890 --> 00:08:49,230
Entrambi questi sono solo per definizione.

184
00:08:49,230 --> 00:08:55,920
>> Poi è definita ogni altro elemento
come somma di n meno 1 e n meno 2.

185
00:08:55,920 --> 00:09:00,330
Così il terzo elemento
Sarebbe 0 e 1 è 1.

186
00:09:00,330 --> 00:09:03,280
E poi il quarto elemento
sarebbe il secondo elemento, 1,

187
00:09:03,280 --> 00:09:06,550
più il terzo elemento, 1.

188
00:09:06,550 --> 00:09:08,507
E questo sarebbe 2.

189
00:09:08,507 --> 00:09:09,340
E così via e così via.

190
00:09:09,340 --> 00:09:11,680
>> Quindi, in questo caso, abbiamo due casi di base.

191
00:09:11,680 --> 00:09:14,850
Se n è uguale a 1, 0 ritorno.

192
00:09:14,850 --> 00:09:18,560
Se n è uguale a 2, ritorno 1.

193
00:09:18,560 --> 00:09:25,930
In caso contrario, tornare Fibonacci di n
meno 1 più di Fibonacci di n meno 2.

194
00:09:25,930 --> 00:09:27,180
>> Ecco, questo è i casi di base più.

195
00:09:27,180 --> 00:09:29,271
Che dire di più casi ricorsive?

196
00:09:29,271 --> 00:09:31,520
Beh, c'è qualcosa
chiamato la congettura di Collatz.

197
00:09:31,520 --> 00:09:34,630
Non ho intenzione di dire,
si sa di cosa si tratta,

198
00:09:34,630 --> 00:09:38,170
perché in realtà è il nostro ultimo
problema per questo particolare video.

199
00:09:38,170 --> 00:09:43,220
Ed è il nostro esercizio
a lavorare insieme.

200
00:09:43,220 --> 00:09:46,760
>> Quindi, ecco cosa il
Collatz congetture è--

201
00:09:46,760 --> 00:09:48,820
si applica ad ogni intero positivo.

202
00:09:48,820 --> 00:09:51,500
E specula che è
sempre possibile ottenere indietro

203
00:09:51,500 --> 00:09:55,060
a 1 se si segue questa procedura.

204
00:09:55,060 --> 00:09:57,560
Se n è 1, stop.

205
00:09:57,560 --> 00:10:00,070
Siamo tornati a 1 se n è 1.

206
00:10:00,070 --> 00:10:05,670
>> In caso contrario, passare attraverso questo
processo di nuovo il n diviso 2.

207
00:10:05,670 --> 00:10:08,200
E vedere se si può tornare a 1.

208
00:10:08,200 --> 00:10:13,260
In caso contrario, se n è dispari, passare attraverso
questo processo nuovamente 3n + 1,

209
00:10:13,260 --> 00:10:15,552
o 3 n volte più 1.

210
00:10:15,552 --> 00:10:17,010
Quindi qui abbiamo un caso base.

211
00:10:17,010 --> 00:10:18,430
Se n è uguale a 1, stop.

212
00:10:18,430 --> 00:10:20,230
Non stiamo facendo più ricorsione.

213
00:10:20,230 --> 00:10:23,730
>> Ma abbiamo due casi ricorsivi.

214
00:10:23,730 --> 00:10:28,750
Se n è pari, facciamo una ricorsiva
caso, chiamando n diviso per 2.

215
00:10:28,750 --> 00:10:33,950
Se n è dispari, facciamo un altro
caso ricorsivo su 3 n volte più 1.

216
00:10:33,950 --> 00:10:39,120
>> E così l'obiettivo per questo video è
di prendere un secondo, mettere in pausa il video,

217
00:10:39,120 --> 00:10:42,440
e cercare di scrivere questo
funzione ricorsiva Collatz

218
00:10:42,440 --> 00:10:47,640
dove si passa in un valore n, e
calcola quanti passi

219
00:10:47,640 --> 00:10:52,430
prende per arrivare a 1 se si inizia da n
e si seguono questi passaggi sopra.

220
00:10:52,430 --> 00:10:56,660
Se n è 1, esso prende 0 passi.

221
00:10:56,660 --> 00:11:00,190
In caso contrario, sta andando a
fare un passo in più per quanto

222
00:11:00,190 --> 00:11:06,200
molti passi che prende su entrambi n
diviso 2 se n è pari, o 3n + 1

223
00:11:06,200 --> 00:11:08,100
se n è dispari.

224
00:11:08,100 --> 00:11:11,190
>> Ora, io ho messo sullo schermo qui
un paio di cose di prova per voi,

225
00:11:11,190 --> 00:11:15,690
un paio di test case per voi, per vedere
ciò che questi vari numeri Collatz sono,

226
00:11:15,690 --> 00:11:17,440
ed anche un'illustrazione
dei passi che

227
00:11:17,440 --> 00:11:20,390
devono essere attraversato in modo da poter
sorta di vedere questo processo in azione.

228
00:11:20,390 --> 00:11:24,222
Quindi, se n è uguale a
1, Collatz di n è 0.

229
00:11:24,222 --> 00:11:26,180
Non dovete fare
qualsiasi cosa per tornare a 1.

230
00:11:26,180 --> 00:11:27,600
Sei già lì.

231
00:11:27,600 --> 00:11:30,550
>> Se n è 2, ci vuole
un passo per arrivare a 1.

232
00:11:30,550 --> 00:11:31,810
Si inizia con 2.

233
00:11:31,810 --> 00:11:33,100
Ebbene, 2 non è uguale a 1.

234
00:11:33,100 --> 00:11:36,580
Quindi sarà un passo
oltre tuttavia molti passi it

235
00:11:36,580 --> 00:11:38,015
assume n diviso 2.

236
00:11:38,015 --> 00:11:41,280

237
00:11:41,280 --> 00:11:42,910
>> 2 diviso 2 è 1.

238
00:11:42,910 --> 00:11:47,200
Quindi ci vuole un passo più comunque
molti passaggi impiegati per 1.

239
00:11:47,200 --> 00:11:49,720
1 prende a zero punti.

240
00:11:49,720 --> 00:11:52,370
>> Per 3, come potete vedere, non c'è
parecchi gradini coinvolti.

241
00:11:52,370 --> 00:11:53,590
Si passa da 3.

242
00:11:53,590 --> 00:11:56,710
E poi si va a
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Ci vogliono sette passi per tornare a 1.

244
00:11:58,804 --> 00:12:01,220
E come potete vedere, c'è una
paio di altri casi di test qui

245
00:12:01,220 --> 00:12:02,470
per testare il programma.

246
00:12:02,470 --> 00:12:03,970
Così ancora una volta, mettere in pausa il video.

247
00:12:03,970 --> 00:12:09,210
E io andrò ora a saltare indietro
ciò che il processo reale è qui,

248
00:12:09,210 --> 00:12:11,390
ciò che questa congettura è.

249
00:12:11,390 --> 00:12:14,140
>> Vedi se riesci a capire
come definire Collatz di n

250
00:12:14,140 --> 00:12:19,967
in modo che calcola quante
i passaggi che ci vuole per arrivare a 1.

251
00:12:19,967 --> 00:12:23,050
Così si spera, si è messo in pausa il video
e non sono solo in attesa di me

252
00:12:23,050 --> 00:12:25,820
per darvi la risposta qui.

253
00:12:25,820 --> 00:12:29,120
Ma se siete, beh,
ecco la risposta comunque.

254
00:12:29,120 --> 00:12:33,070
>> Quindi, ecco una possibile definizione
della funzione Collatz.

255
00:12:33,070 --> 00:12:35,610
La nostra base case-- se n è
uguale a 1, torniamo 0.

256
00:12:35,610 --> 00:12:38,250
Non ci vuole alcuna
passi per tornare a 1.

257
00:12:38,250 --> 00:12:42,710
>> In caso contrario, abbiamo due di casi, ricorsiva
uno per i numeri pari e dispari per uno.

258
00:12:42,710 --> 00:12:47,164
Il modo in cui provo per numeri pari
è quello di verificare se n mod 2 è uguale a 0.

259
00:12:47,164 --> 00:12:49,080
Questo è fondamentalmente, di nuovo,
porre la domanda,

260
00:12:49,080 --> 00:12:54,050
se vi ricordate cosa è-- mod se io
dividere n per 2 non c'è un resto?

261
00:12:54,050 --> 00:12:55,470
Questo sarebbe un numero pari.

262
00:12:55,470 --> 00:13:01,370
>> E così, se n mod 2 è uguale a 0 è
il test è presente un numero pari.

263
00:13:01,370 --> 00:13:04,250
Se è così, voglio tornare 1,
perché questo è sicuramente

264
00:13:04,250 --> 00:13:09,270
facendo un passo più Collatz di
qualunque sia il numero è la metà di me.

265
00:13:09,270 --> 00:13:13,910
In caso contrario, voglio tornare 1
più di 3 volte Collatz n più 1.

266
00:13:13,910 --> 00:13:16,060
Quello era l'altro
passo ricorsivo che ci

267
00:13:16,060 --> 00:13:19,470
potrebbe prendere per calcolare il
Collatz-- il numero di passi

268
00:13:19,470 --> 00:13:22,610
ci vuole per ottenere indietro
1 dato un numero.

269
00:13:22,610 --> 00:13:24,610
Così si spera, in questo esempio
ti ha dato un po '

270
00:13:24,610 --> 00:13:26,620
di un assaggio di procedure ricorsive.

271
00:13:26,620 --> 00:13:30,220
Si spera, si pensa codice è un
po 'di più bello se attuate

272
00:13:30,220 --> 00:13:32,760
in un modo ricorsivo elegante.

273
00:13:32,760 --> 00:13:35,955
Ma anche se non, la ricorsione è un
strumento davvero potente comunque.

274
00:13:35,955 --> 00:13:38,330
E quindi è sicuramente qualcosa
per ottenere la testa intorno,

275
00:13:38,330 --> 00:13:41,360
perché sarete in grado di creare
programmi piuttosto fresco utilizzando la ricorsione

276
00:13:41,360 --> 00:13:45,930
che potrebbero altrimenti essere complesso di scrivere
se si sta utilizzando loop e iterazione.

277
00:13:45,930 --> 00:13:46,980
Sono Doug Lloyd.

278
00:13:46,980 --> 00:13:48,780
Questo è CS50.

279
00:13:48,780 --> 00:13:50,228