1
00:00:00,000 --> 00:00:05,860
>> [Música tocando]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Você provavelmente pensa que
código é apenas usado para realizar uma tarefa.

3
00:00:09,530 --> 00:00:10,450
Você escreve-o para fora.

4
00:00:10,450 --> 00:00:11,664
Ele faz alguma coisa.

5
00:00:11,664 --> 00:00:12,580
Isso é muito bonito isso.

6
00:00:12,580 --> 00:00:13,160
>> Você compilá-lo.

7
00:00:13,160 --> 00:00:13,993
Você executar o programa.

8
00:00:13,993 --> 00:00:15,370
Você está pronto para ir.

9
00:00:15,370 --> 00:00:17,520
>> Mas, acredite ou não, se
você codificar para um longo período de tempo,

10
00:00:17,520 --> 00:00:20,550
você realmente pode vir para ver
código como algo que é bonito.

11
00:00:20,550 --> 00:00:23,275
Resolve um problema em
uma maneira muito interessante,

12
00:00:23,275 --> 00:00:26,510
ou há algo realmente
puro sobre a maneira que parece.

13
00:00:26,510 --> 00:00:28,750
Você pode estar rindo
para mim, mas é verdade.

14
00:00:28,750 --> 00:00:31,530
E recursão é uma maneira
a sorte de obter essa idéia

15
00:00:31,530 --> 00:00:34,090
da bela código, de aparência elegante.

16
00:00:34,090 --> 00:00:37,740
Ele resolve os problemas de uma forma que
são interessantes, fácil de visualizar,

17
00:00:37,740 --> 00:00:39,810
e surpreendentemente curta.

18
00:00:39,810 --> 00:00:43,190
>> As obras maneira de recursão
é, uma função recursiva

19
00:00:43,190 --> 00:00:49,291
é definida como uma função que chama
-se como parte de sua execução.

20
00:00:49,291 --> 00:00:51,790
Isso pode parecer um pouco estranho,
e vamos ver um pouco

21
00:00:51,790 --> 00:00:53,750
sobre como isso funciona em um momento.

22
00:00:53,750 --> 00:00:55,560
Mas, novamente, estes
procedimentos recursiva são

23
00:00:55,560 --> 00:00:57,730
vai ser tão elegante
porque eles vão

24
00:00:57,730 --> 00:01:00,410
para resolver este problema, sem
Tendo em todas estas outras funções

25
00:01:00,410 --> 00:01:02,710
ou estes longos loops.

26
00:01:02,710 --> 00:01:06,310
Você vai ver que estes recursiva
procedimentos estão indo olhar tão curto.

27
00:01:06,310 --> 00:01:10,610
E eles realmente vão fazer
seu código olhar muito mais bonito.

28
00:01:10,610 --> 00:01:12,560
>> Vou te dar um exemplo
deste para ver como

29
00:01:12,560 --> 00:01:14,880
um procedimento recursiva pode ser definido.

30
00:01:14,880 --> 00:01:18,202
Então, se você estiver familiarizado com este
de aula de matemática há muitos anos,

31
00:01:18,202 --> 00:01:20,910
Há algo chamado de
função fatorial, que é normalmente

32
00:01:20,910 --> 00:01:25,340
denotado como um ponto de exclamação, que
é definida ao longo do todos os inteiros positivos.

33
00:01:25,340 --> 00:01:28,850
E a maneira que n
factorial é calculado

34
00:01:28,850 --> 00:01:31,050
é você multiplicar todos
os números de menos de

35
00:01:31,050 --> 00:01:33,750
ou igual a n together--
Todos os números inteiros inferiores a

36
00:01:33,750 --> 00:01:34,880
ou igual a n juntos.

37
00:01:34,880 --> 00:01:39,850
>> Então fatorial 5 é 5 vezes
4 vezes 3 vezes 2 vezes 1.

38
00:01:39,850 --> 00:01:43,020
E 4 fatorial é 4 vezes
3 vezes 2 vezes 1 e assim por diante.

39
00:01:43,020 --> 00:01:44,800
Você começa a idéia.

40
00:01:44,800 --> 00:01:47,060
>> Como programadores, nós não
usar n, ponto de exclamação.

41
00:01:47,060 --> 00:01:51,840
Então, vamos definir o fatorial
função como fato de n.

42
00:01:51,840 --> 00:01:56,897
E nós vamos usar para criar fatorial
uma solução para um problema recursiva.

43
00:01:56,897 --> 00:01:59,230
E eu acho que você pode encontrar
que é muito mais visualmente

44
00:01:59,230 --> 00:02:02,380
atraente do que o iterativo
versão deste, que

45
00:02:02,380 --> 00:02:05,010
nós também vamos dar uma olhada em um momento.

46
00:02:05,010 --> 00:02:08,310
>> Então, aqui estão um par de
trocadilho facts-- intended--

47
00:02:08,310 --> 00:02:10,169
sobre o factorial--
função fatorial.

48
00:02:10,169 --> 00:02:13,090
O fatorial de um, como eu disse, é uma.

49
00:02:13,090 --> 00:02:15,690
O fatorial de 2 é 2 vezes 1.

50
00:02:15,690 --> 00:02:18,470
O fatorial de 3 a 3
vezes 2 vezes 1, e assim por diante.

51
00:02:18,470 --> 00:02:20,810
Nós conversamos sobre 4 e 5 já.

52
00:02:20,810 --> 00:02:23,940
>> Mas olhando para isso, não é verdade?

53
00:02:23,940 --> 00:02:28,220
Não é apenas fatorial 2
2 vezes o fatorial de um?

54
00:02:28,220 --> 00:02:31,130
Quero dizer, o fatorial de um é um.

55
00:02:31,130 --> 00:02:34,940
Então, por que não podemos simplesmente dizer que,
desde fatorial 2 é 2 vezes 1,

56
00:02:34,940 --> 00:02:38,520
É realmente apenas 2 vezes
o fatorial de um?

57
00:02:38,520 --> 00:02:40,900
>> E então estender essa idéia,
não é o fatorial de 3

58
00:02:40,900 --> 00:02:44,080
apenas a 3 vezes o fatorial de 2?

59
00:02:44,080 --> 00:02:50,350
E o fatorial de 4 é 4 vezes
o fatorial de 3, e assim por diante?

60
00:02:50,350 --> 00:02:52,530
Na verdade, o fatorial
de qualquer número pode apenas

61
00:02:52,530 --> 00:02:54,660
ser expresso se nós tipo
de realizá-la para sempre.

62
00:02:54,660 --> 00:02:56,870
Podemos tipo de generalizar
o problema fatorial

63
00:02:56,870 --> 00:02:59,910
Como é n vezes os
fatorial de n menos 1.

64
00:02:59,910 --> 00:03:04,840
É n vezes o produto de
todos os números menos do que eu.

65
00:03:04,840 --> 00:03:08,890
>> Esta idéia, esta
generalização do problema,

66
00:03:08,890 --> 00:03:13,410
permite-nos de forma recursiva
definir a função fatorial.

67
00:03:13,410 --> 00:03:15,440
Quando você define uma função
de forma recursiva, não há

68
00:03:15,440 --> 00:03:17,470
duas coisas que precisam ser uma parte dela.

69
00:03:17,470 --> 00:03:20,990
Você precisa ter uma coisa chamada
caso base, o que, quando você acioná-lo,

70
00:03:20,990 --> 00:03:22,480
irá parar o processo recursivo.

71
00:03:22,480 --> 00:03:25,300
>> Caso contrário, uma função que chama
itself-- como você pode imagine--

72
00:03:25,300 --> 00:03:26,870
poderia ir para sempre.

73
00:03:26,870 --> 00:03:29,047
Função chama a função
chama as chamadas de função

74
00:03:29,047 --> 00:03:30,380
a função chama a função.

75
00:03:30,380 --> 00:03:32,380
Se você não tem uma maneira
pará-lo, o seu programa

76
00:03:32,380 --> 00:03:34,760
vai ser efetivamente preso
em um loop infinito.

77
00:03:34,760 --> 00:03:37,176
Ele irá falhar, eventualmente,
porque ele vai ficar sem memória.

78
00:03:37,176 --> 00:03:38,990
Mas isso não vem ao caso.

79
00:03:38,990 --> 00:03:42,210
>> Nós precisamos de ter alguma outra maneira de parar
coisas além do nosso programa que deixa de funcionar,

80
00:03:42,210 --> 00:03:46,010
porque um programa que falha é
provavelmente não bonito ou elegante.

81
00:03:46,010 --> 00:03:47,690
E assim nós chamamos este cenário de base.

82
00:03:47,690 --> 00:03:50,610
Esta é uma solução simples
para um problema que pára

83
00:03:50,610 --> 00:03:52,770
o processo recursivo ocorra.

84
00:03:52,770 --> 00:03:55,220
Então essa é uma parte da
uma função recursiva.

85
00:03:55,220 --> 00:03:56,820
>> A segunda parte é o caso recursiva.

86
00:03:56,820 --> 00:03:59,195
E é aqui que a recursão
vai realmente acontecer.

87
00:03:59,195 --> 00:04:02,200
Este é o lugar onde o
função irá chamar a si mesma.

88
00:04:02,200 --> 00:04:05,940
>> Não vai chamar-se exatamente
da mesma forma que foi chamado.

89
00:04:05,940 --> 00:04:08,880
Vai ser uma pequena variação
que faz com que o problema é

90
00:04:08,880 --> 00:04:11,497
tentando resolver um pouquinho menor.

91
00:04:11,497 --> 00:04:14,330
Mas geralmente passa o fanfarrão
de resolver a maior parte da solução de

92
00:04:14,330 --> 00:04:17,450
para uma chamada diferente para baixo da linha.

93
00:04:17,450 --> 00:04:20,290
>> Qual desses looks
como é o caso base aqui?

94
00:04:20,290 --> 00:04:25,384
Qual desses olhares como o
mais simples solução para um problema?

95
00:04:25,384 --> 00:04:27,550
Temos um monte de fatoriais,
e poderíamos continuar

96
00:04:27,550 --> 00:04:30,470
indo on-- 6, 7, 8, 9, 10, e assim por diante.

97
00:04:30,470 --> 00:04:34,130
>> Mas um desses olhares como um
bom caso para ser o caso base.

98
00:04:34,130 --> 00:04:35,310
É uma solução muito simples.

99
00:04:35,310 --> 00:04:37,810
Nós não temos que fazer nada especial.

100
00:04:37,810 --> 00:04:40,560
>> O fatorial de um é apenas um.

101
00:04:40,560 --> 00:04:42,790
Nós não temos que fazer qualquer
multiplicação de todo.

102
00:04:42,790 --> 00:04:45,248
Parece que se vamos
para tentar resolver este problema,

103
00:04:45,248 --> 00:04:47,600
e nós precisamos de parar o
recursão em algum lugar,

104
00:04:47,600 --> 00:04:50,610
nós provavelmente quer parar
quando chegarmos a 1.

105
00:04:50,610 --> 00:04:54,580
Nós não queremos parar antes disso.

106
00:04:54,580 --> 00:04:56,660
>> Então, se estamos definindo
nossa função fatorial,

107
00:04:56,660 --> 00:04:58,690
aqui está um esqueleto para
como podemos fazer isso.

108
00:04:58,690 --> 00:05:03,110
Precisamos de ligar esses dois coisas-
o caso base eo caso recursiva.

109
00:05:03,110 --> 00:05:04,990
O que é o caso base?

110
00:05:04,990 --> 00:05:10,150
Se n é igual a 1, de regresso que é 1--
um problema muito simples de resolver.

111
00:05:10,150 --> 00:05:11,890
>> O fatorial de um é um.

112
00:05:11,890 --> 00:05:13,860
Não são 1 vezes nada.

113
00:05:13,860 --> 00:05:15,020
É apenas um.

114
00:05:15,020 --> 00:05:17,170
É um fato muito fácil.

115
00:05:17,170 --> 00:05:19,620
E assim que pode ser o nosso caso base.

116
00:05:19,620 --> 00:05:24,730
Se conseguir passar 1 a este
função, vamos retornar 1.

117
00:05:24,730 --> 00:05:27,320
>> Qual é a recursiva
caso provavelmente se parece?

118
00:05:27,320 --> 00:05:32,445
Para cada outro número
além de um, que é o padrão?

119
00:05:32,445 --> 00:05:35,780
Bem, se nós estamos tomando
o fatorial de n,

120
00:05:35,780 --> 00:05:38,160
É n vezes o fatorial de n menos 1.

121
00:05:38,160 --> 00:05:42,130
>> Se nós estamos levando o fatorial de 3,
é 3 vezes o fatorial de 3 menos 1,

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

123
00:05:43,070 --> 00:05:47,330
E por isso, se nós não estamos
olhando para um, caso contrário,

124
00:05:47,330 --> 00:05:51,710
retorno n vezes os
fatorial de n menos 1.

125
00:05:51,710 --> 00:05:53,210
É bastante simples.

126
00:05:53,210 --> 00:05:57,360
>> E por uma questão de ter um pouco
mais limpo e mais elegante código,

127
00:05:57,360 --> 00:06:01,440
sabemos que se nós tem laços de linha única
ou single-line desvios condicionais,

128
00:06:01,440 --> 00:06:04,490
podemos nos livrar de todos os
chaves em torno deles.

129
00:06:04,490 --> 00:06:06,850
Assim, podemos consolidar essa a isso.

130
00:06:06,850 --> 00:06:09,640
Isto tem exactamente a mesma
como esta funcionalidade.

131
00:06:09,640 --> 00:06:13,850
>> Eu só estou tirando o encaracolado
cintas, porque há apenas uma linha

132
00:06:13,850 --> 00:06:18,500
dentro desses desvios condicionais.

133
00:06:18,500 --> 00:06:21,160
Assim, estes se comportam de forma idêntica.

134
00:06:21,160 --> 00:06:23,800
Se n é igual a 1, de regresso 1.

135
00:06:23,800 --> 00:06:28,351
Caso contrário, retornar n vezes
o fatorial de n menos 1.

136
00:06:28,351 --> 00:06:29,850
Então, nós estamos fazendo o problema menor.

137
00:06:29,850 --> 00:06:33,850
Se n começa como 5, vamos
voltar 5 vezes o fatorial de quatro.

138
00:06:33,850 --> 00:06:37,100
E vamos ver em um minuto quando falamos
sobre a stack-- chamada em outro vídeo

139
00:06:37,100 --> 00:06:39,390
onde falamos sobre o
chamar stack-- vamos aprender

140
00:06:39,390 --> 00:06:41,630
sobre por que exatamente esse processo funciona.

141
00:06:41,630 --> 00:06:46,970
>> Mas enquanto fatorial de 5 diz
voltar 5 vezes fatorial de 4, e 4

142
00:06:46,970 --> 00:06:49,710
vai dizer, OK, bem, retorno
4 vezes o fatorial de 3.

143
00:06:49,710 --> 00:06:51,737
E como você pode ver, estamos
tipo de aproximação 1.

144
00:06:51,737 --> 00:06:53,820
Estamos chegando mais perto e
mais perto desse caso base.

145
00:06:53,820 --> 00:06:58,180
>> E uma vez que nós batemos o caso base,
todas as funções anteriores

146
00:06:58,180 --> 00:07:00,540
tenho a resposta que eles estavam procurando.

147
00:07:00,540 --> 00:07:03,900
Fatorial de 2 estava dizendo retorno
2 vezes o fatorial de um.

148
00:07:03,900 --> 00:07:06,760
Bem, fatorial de 1 retorna 1.

149
00:07:06,760 --> 00:07:10,090
Assim, o convite à apresentação de fatorial
de 2 pode voltar 2 vezes 1,

150
00:07:10,090 --> 00:07:13,980
e dar isso de volta para fatorial
3, que está esperando por esse resultado.

151
00:07:13,980 --> 00:07:17,110
>> E, em seguida, ele pode calcular
Seu resultado, 3 vezes 2 é 6,

152
00:07:17,110 --> 00:07:18,907
e devolvê-lo ao fatorial de 4.

153
00:07:18,907 --> 00:07:20,740
E, novamente, temos um
vídeo na pilha de chamadas

154
00:07:20,740 --> 00:07:23,810
onde isso é ilustrado um pouco
mais do que o que estou dizendo agora.

155
00:07:23,810 --> 00:07:25,300
Mas é isso.

156
00:07:25,300 --> 00:07:29,300
Isto por si só, é a solução de
calcular o fatorial de um número.

157
00:07:29,300 --> 00:07:31,527
>> É apenas quatro linhas de código.

158
00:07:31,527 --> 00:07:32,610
Isso é muito legal, né?

159
00:07:32,610 --> 00:07:35,480
É uma espécie de sexy.

160
00:07:35,480 --> 00:07:38,580
>> Assim, em geral, mas não
sempre, uma função recursiva

161
00:07:38,580 --> 00:07:41,190
podem substituir um circuito numa
função não recursiva.

162
00:07:41,190 --> 00:07:46,100
Então, aqui, lado a lado, é o iterativo
versão da função fatorial.

163
00:07:46,100 --> 00:07:49,650
Ambos calcule
exatamente a mesma coisa.

164
00:07:49,650 --> 00:07:52,170
>> Ambos calcular o fatorial de n.

165
00:07:52,170 --> 00:07:54,990
A versão do lado esquerdo
usa recursão para fazê-lo.

166
00:07:54,990 --> 00:07:58,320
A versão à direita
usa iteração para fazê-lo.

167
00:07:58,320 --> 00:08:02,050
>> E observem, nós temos que declarar
uma variável de um produto inteiro.

168
00:08:02,050 --> 00:08:02,940
E então nós loop.

169
00:08:02,940 --> 00:08:06,790
Assim, desde que n é maior do que 0, nós
manter multiplicando esse produto por n

170
00:08:06,790 --> 00:08:09,890
e diminuindo n até
calculamos o produto.

171
00:08:09,890 --> 00:08:14,600
Assim, estas duas funções, de novo,
fazer exatamente a mesma coisa.

172
00:08:14,600 --> 00:08:19,980
Mas eles não fazê-lo em
exactamente da mesma forma.

173
00:08:19,980 --> 00:08:22,430
>> Agora, é possível
ter mais do que uma base

174
00:08:22,430 --> 00:08:25,770
caso de um ou mais
caso recursiva, dependendo

175
00:08:25,770 --> 00:08:27,670
em que a função está tentando fazer.

176
00:08:27,670 --> 00:08:31,650
Você não é necessariamente apenas limitado a
um caso base ou a uma única recursiva

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

178
00:08:32,370 --> 00:08:35,320
Então, um exemplo de algo
com vários casos base

179
00:08:35,320 --> 00:08:37,830
pode ser o o--
Seqüência de números de Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Você deve se lembrar de
dias de escola primária

181
00:08:41,549 --> 00:08:45,740
que a seqüência de Fibonacci é definido
isto-- como o primeiro elemento é 0.

182
00:08:45,740 --> 00:08:46,890
O segundo elemento é 1.

183
00:08:46,890 --> 00:08:49,230
Ambos esses são apenas por definição.

184
00:08:49,230 --> 00:08:55,920
>> Em seguida, todos os outros elementos é definida
como a soma de n menos 1 e n menos 2.

185
00:08:55,920 --> 00:09:00,330
Assim, o terceiro elemento
0 seria mais 1 é 1.

186
00:09:00,330 --> 00:09:03,280
E, em seguida, o quarto elemento
seria o segundo elemento, 1,

187
00:09:03,280 --> 00:09:06,550
mais o terceiro elemento, 1.

188
00:09:06,550 --> 00:09:08,507
E isso seria 2.

189
00:09:08,507 --> 00:09:09,340
E assim por diante e assim por diante.

190
00:09:09,340 --> 00:09:11,680
>> Portanto, neste caso, temos dois casos base.

191
00:09:11,680 --> 00:09:14,850
Se n é igual a 1, 0 regresso.

192
00:09:14,850 --> 00:09:18,560
Se n é igual a 2, o retorno 1.

193
00:09:18,560 --> 00:09:25,930
Caso contrário, o retorno de Fibonacci de n
menos 1 mais Fibonacci de n menos 2.

194
00:09:25,930 --> 00:09:27,180
>> Então é isso vários casos base.

195
00:09:27,180 --> 00:09:29,271
E sobre vários casos recursiva?

196
00:09:29,271 --> 00:09:31,520
Bem, há algo
chamado a conjectura de Collatz.

197
00:09:31,520 --> 00:09:34,630
Eu não vou dizer,
você sabe o que é,

198
00:09:34,630 --> 00:09:38,170
porque é realmente o nosso último
problema para este vídeo particular.

199
00:09:38,170 --> 00:09:43,220
E é o nosso exercício
para trabalhar em conjunto.

200
00:09:43,220 --> 00:09:46,760
>> Então aqui está o que o
Collatz conjectura é--

201
00:09:46,760 --> 00:09:48,820
que se aplica a cada inteiro positivo.

202
00:09:48,820 --> 00:09:51,500
E ele especula que ele é
sempre possível voltar

203
00:09:51,500 --> 00:09:55,060
1 se você seguir estes passos.

204
00:09:55,060 --> 00:09:57,560
Se n é 1, parar.

205
00:09:57,560 --> 00:10:00,070
Temos de volta para 1 se n for 1.

206
00:10:00,070 --> 00:10:05,670
>> Caso contrário, passar por isso
processo novamente em N dividida por 2.

207
00:10:05,670 --> 00:10:08,200
E veja se você pode obter de volta para 1.

208
00:10:08,200 --> 00:10:13,260
Caso contrário, se n for ímpar, passar por
este processo mais uma vez em 3n + 1,

209
00:10:13,260 --> 00:10:15,552
ou 3 vezes n mais 1.

210
00:10:15,552 --> 00:10:17,010
Então aqui nós temos um único caso base.

211
00:10:17,010 --> 00:10:18,430
Se n é igual a 1, pare.

212
00:10:18,430 --> 00:10:20,230
Nós não estamos fazendo mais recursão.

213
00:10:20,230 --> 00:10:23,730
>> Mas temos dois casos recursiva.

214
00:10:23,730 --> 00:10:28,750
Se n é par, nós fazemos uma recursiva
caso, chamando n dividido por dois.

215
00:10:28,750 --> 00:10:33,950
Se n é ímpar, fazemos uma diferente
caso recursiva em 3 vezes n mais 1.

216
00:10:33,950 --> 00:10:39,120
>> E assim, a meta para este vídeo é
para tomar uma segunda, pausar o vídeo,

217
00:10:39,120 --> 00:10:42,440
e tentar escrever este
função recursiva Collatz

218
00:10:42,440 --> 00:10:47,640
onde você passar um valor n, e
ele calcula quantos passos

219
00:10:47,640 --> 00:10:52,430
leva para chegar a 1 se você começar a partir de n
e você seguir os passos acima.

220
00:10:52,430 --> 00:10:56,660
Se n é 1, que leva 0 etapas.

221
00:10:56,660 --> 00:11:00,190
Caso contrário, ele vai
dar um passo além no entanto

222
00:11:00,190 --> 00:11:06,200
muitos passos que leva em ambos os n
dividido por 2, se n for par, ou 3n + 1

223
00:11:06,200 --> 00:11:08,100
se n é ímpar.

224
00:11:08,100 --> 00:11:11,190
>> Agora, eu coloquei na tela aqui
um par de coisas teste para você,

225
00:11:11,190 --> 00:11:15,690
um par de testes de casos para você, para ver
o que esses vários números de Collatz são,

226
00:11:15,690 --> 00:11:17,440
e também uma ilustração
de que as etapas

227
00:11:17,440 --> 00:11:20,390
precisam ser atravessado para que você possa
tipo de ver este processo em ação.

228
00:11:20,390 --> 00:11:24,222
Assim, se n for igual a
1, Collatz de n é 0.

229
00:11:24,222 --> 00:11:26,180
Você não tem que fazer
qualquer coisa para voltar para 1.

230
00:11:26,180 --> 00:11:27,600
Você já está lá.

231
00:11:27,600 --> 00:11:30,550
>> Se n for 2, que leva
um passo para chegar a 1.

232
00:11:30,550 --> 00:11:31,810
Você começa com dois.

233
00:11:31,810 --> 00:11:33,100
Bem, 2 não é igual a 1.

234
00:11:33,100 --> 00:11:36,580
Por isso, vai ser um passo
no entanto, mais muitos passos de TI

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

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

237
00:11:41,280 --> 00:11:42,910
>> 2 é dividido por 2 1.

238
00:11:42,910 --> 00:11:47,200
Por isso, dá um passo além no entanto
muitos passos que leva para 1.

239
00:11:47,200 --> 00:11:49,720
1 comporta de zero passos.

240
00:11:49,720 --> 00:11:52,370
>> Para 3, como você pode ver, há
muito poucos passos envolvidos.

241
00:11:52,370 --> 00:11:53,590
Você vai de 3.

242
00:11:53,590 --> 00:11:56,710
E então você vai para
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Leva sete passos para voltar a um.

244
00:11:58,804 --> 00:12:01,220
E como você pode ver, há uma
alguns outros casos de teste aqui

245
00:12:01,220 --> 00:12:02,470
para testar seu programa.

246
00:12:02,470 --> 00:12:03,970
Então, novamente, pausar o vídeo.

247
00:12:03,970 --> 00:12:09,210
E eu vou saltar para trás agora
o que o processo real é aqui,

248
00:12:09,210 --> 00:12:11,390
o que é essa conjectura.

249
00:12:11,390 --> 00:12:14,140
>> Veja se você pode descobrir
como definir Collatz de n

250
00:12:14,140 --> 00:12:19,967
de modo que ele calcula quantos
os passos que leva para chegar a 1.

251
00:12:19,967 --> 00:12:23,050
Portanto, esperamos que, você fez uma pausa o vídeo
e você não está apenas esperando por mim

252
00:12:23,050 --> 00:12:25,820
para dar-lhe a resposta aqui.

253
00:12:25,820 --> 00:12:29,120
Mas se você é, bem,
aqui está a resposta de qualquer maneira.

254
00:12:29,120 --> 00:12:33,070
>> Então aqui está uma possível definição
da função Collatz.

255
00:12:33,070 --> 00:12:35,610
Nossa base case-- se n for
igual a 1, voltamos 0.

256
00:12:35,610 --> 00:12:38,250
Não é preciso qualquer
passos para obter de volta a um.

257
00:12:38,250 --> 00:12:42,710
>> Caso contrário, temos dois cases-- recursiva
uma para números pares e outra para ímpar.

258
00:12:42,710 --> 00:12:47,164
A maneira que eu testar para números pares
é verificar se n mod 2 é igual a 0.

259
00:12:47,164 --> 00:12:49,080
Isto é, basicamente, mais uma vez,
fazer a pergunta,

260
00:12:49,080 --> 00:12:54,050
se você se lembra o que é-- mod se eu
divide n por 2 que não há restante?

261
00:12:54,050 --> 00:12:55,470
Isso seria um número par.

262
00:12:55,470 --> 00:13:01,370
>> E por isso, se n mod 2 é igual a 0 é
teste é este um número par.

263
00:13:01,370 --> 00:13:04,250
Se assim for, eu quero voltar 1,
porque este é definitivamente

264
00:13:04,250 --> 00:13:09,270
dando um passo além de Collatz
o que número é metade de mim.

265
00:13:09,270 --> 00:13:13,910
Caso contrário, eu quero voltar 1
além de Collatz de 3 vezes n mais 1.

266
00:13:13,910 --> 00:13:16,060
Essa foi a outra
passo que recursiva

267
00:13:16,060 --> 00:13:19,470
poderia tomar para calcular o
Collatz-- o número de passos

268
00:13:19,470 --> 00:13:22,610
é preciso para voltar
1 dado um número.

269
00:13:22,610 --> 00:13:24,610
Portanto, esperamos que, este exemplo
deu-lhe um pouco

270
00:13:24,610 --> 00:13:26,620
de um gosto de procedimentos recursiva.

271
00:13:26,620 --> 00:13:30,220
Com sorte, você acha que é um código
pouco mais bonito se implementado

272
00:13:30,220 --> 00:13:32,760
de uma forma elegante, recursiva.

273
00:13:32,760 --> 00:13:35,955
Mas mesmo se não, a recursividade é uma
realmente poderosa ferramenta, no entanto.

274
00:13:35,955 --> 00:13:38,330
E por isso é definitivamente algo
para obter a sua cabeça em torno,

275
00:13:38,330 --> 00:13:41,360
porque você vai ser capaz de criar
programas muito legal usando recursão

276
00:13:41,360 --> 00:13:45,930
que de outro modo poderiam ser complexo para escrever
se você estiver usando loops e iteração.

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

278
00:13:46,980 --> 00:13:48,780
Este é CS50.

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