1
00:00:00,000 --> 00:00:05,860
>> [Jouer de la musique]

2
00:00:05,860 --> 00:00:09,530
>> DOUG LLOYD: Vous pensez probablement que
code est juste utilisé pour accomplir une tâche.

3
00:00:09,530 --> 00:00:10,450
Vous écrivez-le.

4
00:00:10,450 --> 00:00:11,664
Il fait quelque chose.

5
00:00:11,664 --> 00:00:12,580
Voilà à peu près tout.

6
00:00:12,580 --> 00:00:13,160
>> Vous compilez.

7
00:00:13,160 --> 00:00:13,993
Vous exécutez le programme.

8
00:00:13,993 --> 00:00:15,370
Vous êtes bon pour aller.

9
00:00:15,370 --> 00:00:17,520
>> Mais croyez-le ou pas, si
vous codez pendant une longue période,

10
00:00:17,520 --> 00:00:20,550
vous pourriez effectivement venu pour voir
Code comme quelque chose qui est beau.

11
00:00:20,550 --> 00:00:23,275
Il résout un problème dans
une façon très intéressante,

12
00:00:23,275 --> 00:00:26,510
ou il ya juste quelque chose de vraiment
ordonnée au sujet de la façon dont elle regarde.

13
00:00:26,510 --> 00:00:28,750
Vous pourriez être riez
à moi, mais il est vrai.

14
00:00:28,750 --> 00:00:31,530
Et récursion est une façon
de sorte d'obtenir cette idée

15
00:00:31,530 --> 00:00:34,090
de la belle, le code élégant prospectifs.

16
00:00:34,090 --> 00:00:37,740
Il résout les problèmes d'une manière qui
sont intéressants, faciles à visualiser,

17
00:00:37,740 --> 00:00:39,810
et étonnamment court.

18
00:00:39,810 --> 00:00:43,190
>> Les travaux façon de récurrence
est une fonction récursive

19
00:00:43,190 --> 00:00:49,291
est défini comme étant une fonction qui appelle
lui-même dans le cadre de son exécution.

20
00:00:49,291 --> 00:00:51,790
Cela peut sembler un peu étrange,
et nous verrons un peu

21
00:00:51,790 --> 00:00:53,750
sur la façon dont cela fonctionne dans un moment.

22
00:00:53,750 --> 00:00:55,560
Mais encore une fois, ceux-ci
procédures récursives sont

23
00:00:55,560 --> 00:00:57,730
va être si élégant
parce qu'ils vont

24
00:00:57,730 --> 00:01:00,410
Pour résoudre ce problème sans
ayant toutes ces autres fonctions

25
00:01:00,410 --> 00:01:02,710
ou ces longues boucles.

26
00:01:02,710 --> 00:01:06,310
Vous verrez que ces récursive
procédures vont regarder si court.

27
00:01:06,310 --> 00:01:10,610
Et ils vont vraiment faire
votre code air beaucoup plus belle.

28
00:01:10,610 --> 00:01:12,560
>> Je vais vous donner un exemple
de cette façon de voir

29
00:01:12,560 --> 00:01:14,880
une procédure récursive peut être définie.

30
00:01:14,880 --> 00:01:18,202
Donc, si vous êtes familier avec ce
à partir de la classe de mathématiques il ya plusieurs années,

31
00:01:18,202 --> 00:01:20,910
Il ya quelque chose appelé le
fonction factorielle, qui est habituellement

32
00:01:20,910 --> 00:01:25,340
notée comme un point d'exclamation, qui
est définie sur tous les entiers positifs.

33
00:01:25,340 --> 00:01:28,850
Et la façon dont n
factorielle est calculée

34
00:01:28,850 --> 00:01:31,050
est vous multipliez tous
les nombres inférieurs à

35
00:01:31,050 --> 00:01:33,750
ou égal à n together--
tous les entiers de moins de

36
00:01:33,750 --> 00:01:34,880
ou égal à n ensemble.

37
00:01:34,880 --> 00:01:39,850
>> Donc 5 factorielle est 5 fois
4 fois 3 fois 2 fois 1.

38
00:01:39,850 --> 00:01:43,020
Et 4 factorielle est 4 fois
3 fois 2 fois 1 et ainsi de suite.

39
00:01:43,020 --> 00:01:44,800
Vous avez l'idée.

40
00:01:44,800 --> 00:01:47,060
>> Comme les programmeurs, nous ne faisons pas
utiliser n, point d'exclamation.

41
00:01:47,060 --> 00:01:51,840
Donc, nous allons définir la factorielle
fonction comme un fait de n.

42
00:01:51,840 --> 00:01:56,897
Et nous allons utiliser pour créer factorielle
une solution à un problème récurrent.

43
00:01:56,897 --> 00:01:59,230
Et je pense que vous pourriez trouver
qu'il est beaucoup plus visuelle

44
00:01:59,230 --> 00:02:02,380
appel que la itérative
version de ce qui

45
00:02:02,380 --> 00:02:05,010
nous allons aussi jeter un oeil à dans un moment.

46
00:02:05,010 --> 00:02:08,310
>> Donc, voici un couple de
calembour facts-- intended--

47
00:02:08,310 --> 00:02:10,169
factorial-- sur la
fonction factorielle.

48
00:02:10,169 --> 00:02:13,090
La factorielle de 1, comme je le disais, est 1.

49
00:02:13,090 --> 00:02:15,690
La factorielle de 2 est 2 fois 1.

50
00:02:15,690 --> 00:02:18,470
La factorielle de 3 est 3
1 fois et 2 fois, et ainsi de suite.

51
00:02:18,470 --> 00:02:20,810
Nous avons parlé de 4 et 5 déjà.

52
00:02:20,810 --> 00:02:23,940
>> Mais en regardant cela, est-ce pas vrai?

53
00:02:23,940 --> 00:02:28,220
Est pas factorielle de 2 seulement
2 fois la factorielle de 1?

54
00:02:28,220 --> 00:02:31,130
Je veux dire, la factorielle de 1 est 1.

55
00:02:31,130 --> 00:02:34,940
Alors pourquoi ne pouvons-nous pas tout simplement dire que,
depuis factorielle de 2 est 2 fois 1,

56
00:02:34,940 --> 00:02:38,520
il est vraiment juste 2 fois
la factorielle de 1?

57
00:02:38,520 --> 00:02:40,900
>> Et puis, étendant cette idée,
est pas la factorielle de 3

58
00:02:40,900 --> 00:02:44,080
seulement 3 fois la factorielle de 2?

59
00:02:44,080 --> 00:02:50,350
Et la factorielle de 4 est 4 fois
la factorielle de 3, et ainsi de suite?

60
00:02:50,350 --> 00:02:52,530
En fait, la factorielle
d'un nombre quelconque peut juste

61
00:02:52,530 --> 00:02:54,660
être exprimé si nous type
de porter ce pour toujours.

62
00:02:54,660 --> 00:02:56,870
Nous pouvons sorte de généraliser
le problème factorielle

63
00:02:56,870 --> 00:02:59,910
car il est n fois les
factorielle de n moins 1.

64
00:02:59,910 --> 00:03:04,840
Il est n fois le produit de
tous les nombres inférieurs à moi.

65
00:03:04,840 --> 00:03:08,890
>> Cette idée, cette
généralisation du problème,

66
00:03:08,890 --> 00:03:13,410
nous permet de façon récursive
définir la fonction factorielle.

67
00:03:13,410 --> 00:03:15,440
Lorsque vous définissez une fonction
récursive, il ya

68
00:03:15,440 --> 00:03:17,470
deux choses qui doivent être une partie de celui-ci.

69
00:03:17,470 --> 00:03:20,990
Vous avez besoin d'avoir quelque chose appelé un
scénario de base, qui, lorsque vous déclenchez ce,

70
00:03:20,990 --> 00:03:22,480
va arrêter le processus récursif.

71
00:03:22,480 --> 00:03:25,300
>> Sinon, une fonction qui appelle
itself-- que vous pourriez imagine--

72
00:03:25,300 --> 00:03:26,870
pourrait durer éternellement.

73
00:03:26,870 --> 00:03:29,047
Appelle la fonction
appelle les appels de fonction

74
00:03:29,047 --> 00:03:30,380
la fonction appelle la fonction.

75
00:03:30,380 --> 00:03:32,380
Si vous ne disposez pas d'une manière
pour l'arrêter, votre programme

76
00:03:32,380 --> 00:03:34,760
seront effectivement coincé
à une boucle infinie.

77
00:03:34,760 --> 00:03:37,176
Il va se planter finalement,
parce que ça va manquer de mémoire.

78
00:03:37,176 --> 00:03:38,990
Mais que ce côté de la question.

79
00:03:38,990 --> 00:03:42,210
>> Nous avons besoin d'un autre moyen d'arrêter
choses encore notre plantage du programme,

80
00:03:42,210 --> 00:03:46,010
car un programme qui plante est
probablement pas beau ou élégant.

81
00:03:46,010 --> 00:03:47,690
Et si nous appelons cela le cas de base.

82
00:03:47,690 --> 00:03:50,610
Ceci est une solution simple
à un problème qui stoppe

83
00:03:50,610 --> 00:03:52,770
le processus récursif de se produire.

84
00:03:52,770 --> 00:03:55,220
Voilà donc une partie de
une fonction récursive.

85
00:03:55,220 --> 00:03:56,820
>> La deuxième partie est le cas récursif.

86
00:03:56,820 --> 00:03:59,195
Et cela est l'endroit où la récursion
aura effectivement lieu.

87
00:03:59,195 --> 00:04:02,200
Ceci est où le
fonction appeler lui-même.

88
00:04:02,200 --> 00:04:05,940
>> Il ne sera pas appeler lui-même exactement
de la même manière qu'il a été appelé.

89
00:04:05,940 --> 00:04:08,880
Ça va être une légère variation
qui rend le problème il est

90
00:04:08,880 --> 00:04:11,497
essayer de résoudre un tout petit peu plus petit.

91
00:04:11,497 --> 00:04:14,330
Mais il passe généralement le mâle
la résolution de la masse de la solution

92
00:04:14,330 --> 00:04:17,450
à un autre appel sur la ligne.

93
00:04:17,450 --> 00:04:20,290
>> Lequel de ces regards
comme dans le cas de base ici?

94
00:04:20,290 --> 00:04:25,384
Lequel de ces regards comme le
solution la plus simple à un problème?

95
00:04:25,384 --> 00:04:27,550
Nous avons un tas de factorielles,
et nous pourrions continuer

96
00:04:27,550 --> 00:04:30,470
aller on-- 6, 7, 8, 9, 10, et ainsi de suite.

97
00:04:30,470 --> 00:04:34,130
>> Mais un de ces regards comme un
bon exemple est le cas de base.

98
00:04:34,130 --> 00:04:35,310
Il est une solution très simple.

99
00:04:35,310 --> 00:04:37,810
Nous ne disposons pas de faire quelque chose de spécial.

100
00:04:37,810 --> 00:04:40,560
>> La factorielle de 1 est juste 1.

101
00:04:40,560 --> 00:04:42,790
Nous ne devons pas faire de
la multiplication du tout.

102
00:04:42,790 --> 00:04:45,248
Il semble que si nous allons
pour essayer de résoudre ce problème,

103
00:04:45,248 --> 00:04:47,600
et nous devons arrêter la
récursivité quelque part,

104
00:04:47,600 --> 00:04:50,610
nous voulons probablement arrêter
quand nous arrivons à 1.

105
00:04:50,610 --> 00:04:54,580
Nous ne voulons pas arrêter avant que.

106
00:04:54,580 --> 00:04:56,660
>> Donc, si nous définissons
notre fonction factorielle,

107
00:04:56,660 --> 00:04:58,690
voici un squelette pour
comment nous pourrions le faire.

108
00:04:58,690 --> 00:05:03,110
Nous avons besoin de brancher ces deux things--
le cas de base et le cas récursif.

109
00:05:03,110 --> 00:05:04,990
Quel est le scénario de base?

110
00:05:04,990 --> 00:05:10,150
Si n est égal à 1, revenir 1-- qui est
un problème très simple à résoudre.

111
00:05:10,150 --> 00:05:11,890
>> La factorielle de 1 est 1.

112
00:05:11,890 --> 00:05:13,860
Ce ne sont pas 1 fois rien.

113
00:05:13,860 --> 00:05:15,020
Il est juste 1.

114
00:05:15,020 --> 00:05:17,170
Il est un fait très facile.

115
00:05:17,170 --> 00:05:19,620
Et si cela peut être notre scénario de base.

116
00:05:19,620 --> 00:05:24,730
Si nous sommes passés dans ce 1
fonction, nous allons simplement revenir 1.

117
00:05:24,730 --> 00:05:27,320
>> Quel est le récursif
cas probablement ressembler?

118
00:05:27,320 --> 00:05:32,445
Pour tout autre nombre
Outre 1, ce qui est le motif?

119
00:05:32,445 --> 00:05:35,780
Eh bien, si nous prenons
la factorielle de n,

120
00:05:35,780 --> 00:05:38,160
Il est n fois la factorielle de n moins 1.

121
00:05:38,160 --> 00:05:42,130
>> Si nous prenons la factorielle de 3,
il est 3 fois la factorielle de 3 moins 1,

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

123
00:05:43,070 --> 00:05:47,330
Et si nous ne sommes pas
regardant 1, sinon

124
00:05:47,330 --> 00:05:51,710
retour n fois les
factorielle de n moins 1.

125
00:05:51,710 --> 00:05:53,210
Il est assez simple.

126
00:05:53,210 --> 00:05:57,360
>> Et pour le plaisir d'avoir légèrement
plus propre et plus de code élégant,

127
00:05:57,360 --> 00:06:01,440
savoir que si nous avons des boucles seule ligne
ou une seule ligne de branches conditionnelles,

128
00:06:01,440 --> 00:06:04,490
nous pouvons nous débarrasser de tous les
accolades autour d'eux.

129
00:06:04,490 --> 00:06:06,850
Donc, nous pouvons consolider ce à cela.

130
00:06:06,850 --> 00:06:09,640
Ceci a exactement la même
fonctionnalité que cette.

131
00:06:09,640 --> 00:06:13,850
>> Je suis juste enlever l'bouclés
accolades, car il n'y a qu'une seule ligne

132
00:06:13,850 --> 00:06:18,500
à l'intérieur de ces branches conditionnelles.

133
00:06:18,500 --> 00:06:21,160
Donc, ce comportement identique.

134
00:06:21,160 --> 00:06:23,800
Si n est égal à 1, renvoie 1.

135
00:06:23,800 --> 00:06:28,351
Sinon retourner n fois
la factorielle de n moins 1.

136
00:06:28,351 --> 00:06:29,850
Nous allons donc faire le plus petit problème.

137
00:06:29,850 --> 00:06:33,850
Si n commence comme 5, nous allons
revenir 5 fois la factorielle de 4.

138
00:06:33,850 --> 00:06:37,100
Et nous verrons dans un instant lorsque nous parlons
sur le stack-- d'appel dans une autre vidéo

139
00:06:37,100 --> 00:06:39,390
où nous parlons de la
appeler stack-- nous apprendrons

140
00:06:39,390 --> 00:06:41,630
à propos de pourquoi exactement ce processus fonctionne.

141
00:06:41,630 --> 00:06:46,970
>> Mais tandis que factorielle de 5 dit
revenir 5 fois factorielle de 4, et 4

142
00:06:46,970 --> 00:06:49,710
va dire, OK, bien, le retour
4 fois la factorielle de 3.

143
00:06:49,710 --> 00:06:51,737
Et comme vous pouvez le voir, nous sommes
sorte d'approche 1.

144
00:06:51,737 --> 00:06:53,820
Nous nous rapprochons et
plus proche de celle cas de base.

145
00:06:53,820 --> 00:06:58,180
>> Et une fois que nous avons touché le cas de base,
l'ensemble des fonctions précédentes

146
00:06:58,180 --> 00:07:00,540
avoir la réponse qu'ils cherchaient.

147
00:07:00,540 --> 00:07:03,900
Factorielle de 2 disait retour
2 fois la factorielle de 1.

148
00:07:03,900 --> 00:07:06,760
Eh bien, factorielle de 1 renvoie 1.

149
00:07:06,760 --> 00:07:10,090
Donc, l'appel à factoriel
2 peut retourner 2 fois 1,

150
00:07:10,090 --> 00:07:13,980
et donner ce retour à factorielle
3, qui est en attente pour ce résultat.

151
00:07:13,980 --> 00:07:17,110
>> Et puis, il peut calculer
son résultat, 3 fois 2 est 6,

152
00:07:17,110 --> 00:07:18,907
et le remettre à factorielle de 4.

153
00:07:18,907 --> 00:07:20,740
Et encore une fois, nous avons une
vidéo sur la pile d'appel

154
00:07:20,740 --> 00:07:23,810
où cela est illustré un peu
plus que ce que je dis en ce moment.

155
00:07:23,810 --> 00:07:25,300
Mais ce qu'il est.

156
00:07:25,300 --> 00:07:29,300
Cela seul est la solution à
le calcul de la factorielle d'un nombre.

157
00:07:29,300 --> 00:07:31,527
>> Il est seulement quatre lignes de code.

158
00:07:31,527 --> 00:07:32,610
Cela est plutôt cool, non?

159
00:07:32,610 --> 00:07:35,480
Il est un peu sexy.

160
00:07:35,480 --> 00:07:38,580
>> Donc, en général, mais pas
toujours, une fonction récursive

161
00:07:38,580 --> 00:07:41,190
peut remplacer une boucle dans un
fonction non récursive.

162
00:07:41,190 --> 00:07:46,100
Donc, ici, côte à côte, est la itérative
version de la fonction factorielle.

163
00:07:46,100 --> 00:07:49,650
Ces deux Calculer
exactement la même chose.

164
00:07:49,650 --> 00:07:52,170
>> Ils ont tous deux calculer la factorielle de n.

165
00:07:52,170 --> 00:07:54,990
La version sur la gauche
utilise la récursivité pour le faire.

166
00:07:54,990 --> 00:07:58,320
La version sur la droite
utilise itération de le faire.

167
00:07:58,320 --> 00:08:02,050
>> Et remarquez, nous avons à déclarer
une variable d'un produit entier.

168
00:08:02,050 --> 00:08:02,940
Et puis on boucle.

169
00:08:02,940 --> 00:08:06,790
Tant que n est supérieur à 0, on
garder multipliant ce produit par n

170
00:08:06,790 --> 00:08:09,890
et la décrémentation de n jusqu'à ce que
nous calculons le produit.

171
00:08:09,890 --> 00:08:14,600
Donc, ces deux fonctions, à nouveau,
faire exactement la même chose.

172
00:08:14,600 --> 00:08:19,980
Mais ils ne le font pas dans
exactement de la même façon.

173
00:08:19,980 --> 00:08:22,430
>> Maintenant, il est possible de
avoir plus d'une base

174
00:08:22,430 --> 00:08:25,770
cas ou plus d'un
cas récursif, selon

175
00:08:25,770 --> 00:08:27,670
sur ce que votre fonction essaie de faire.

176
00:08:27,670 --> 00:08:31,650
Vous n'êtes pas nécessairement juste limité à
un cas de base ou un seul récursive

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

178
00:08:32,370 --> 00:08:35,320
Donc, un exemple de quelque chose
avec des cas de base multiples

179
00:08:35,320 --> 00:08:37,830
pourrait être l'this--
Séquence de nombres de Fibonacci.

180
00:08:37,830 --> 00:08:41,549
>> Vous vous souvenez peut partir
jours de l'école élémentaire

181
00:08:41,549 --> 00:08:45,740
que la suite de Fibonacci est définie
comme this-- le premier élément est 0.

182
00:08:45,740 --> 00:08:46,890
Le deuxième élément est une.

183
00:08:46,890 --> 00:08:49,230
Les deux sont tout simplement par définition.

184
00:08:49,230 --> 00:08:55,920
>> Puis tout autre élément est défini
que la somme de n et n moins 1 moins 2.

185
00:08:55,920 --> 00:09:00,330
Ainsi, le troisième élément
serait 0 + 1 est 1.

186
00:09:00,330 --> 00:09:03,280
Et puis le quatrième élément
serait le deuxième élément, 1,

187
00:09:03,280 --> 00:09:06,550
ainsi que le troisième élément, une.

188
00:09:06,550 --> 00:09:08,507
Et ce serait 2.

189
00:09:08,507 --> 00:09:09,340
Ainsi de suite.

190
00:09:09,340 --> 00:09:11,680
>> Donc dans ce cas, nous avons deux cas de base.

191
00:09:11,680 --> 00:09:14,850
Si n est égal à 1, retourner 0.

192
00:09:14,850 --> 00:09:18,560
Si n est égal à 2, retourner 1.

193
00:09:18,560 --> 00:09:25,930
Sinon, le retour de Fibonacci de n
moins 1 plus de Fibonacci de n moins 2.

194
00:09:25,930 --> 00:09:27,180
>> Voilà donc les cas de plusieurs bases.

195
00:09:27,180 --> 00:09:29,271
Qu'en est-il des cas multiples récursives?

196
00:09:29,271 --> 00:09:31,520
Eh bien, il ya quelque chose
appelé la conjecture de Syracuse.

197
00:09:31,520 --> 00:09:34,630
Je ne vais pas dire,
vous savez ce qui est,

198
00:09:34,630 --> 00:09:38,170
car il est en fait notre dernière
problème pour cette vidéo notamment.

199
00:09:38,170 --> 00:09:43,220
Et il est de notre exercice
de travailler ensemble.

200
00:09:43,220 --> 00:09:46,760
>> Alors, voici ce que le
Collatz Conjecture est--

201
00:09:46,760 --> 00:09:48,820
il applique à chaque nombre entier positif.

202
00:09:48,820 --> 00:09:51,500
Et il spécule qu'il est
toujours possible de revenir

203
00:09:51,500 --> 00:09:55,060
1 si vous suivez ces étapes.

204
00:09:55,060 --> 00:09:57,560
Si n est 1, arrêter.

205
00:09:57,560 --> 00:10:00,070
Nous avons de retour à 1 si n est 1.

206
00:10:00,070 --> 00:10:05,670
>> Sinon, passez à travers cette
processus nouveau sur n divisé par 2.

207
00:10:05,670 --> 00:10:08,200
Et voir si vous pouvez revenir à 1.

208
00:10:08,200 --> 00:10:13,260
Sinon, si n est impair, passer par
ce processus nouveau sur 3n + 1,

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

210
00:10:15,552 --> 00:10:17,010
Nous avons donc ici un cas de base unique.

211
00:10:17,010 --> 00:10:18,430
Si n est égal à 1, arrêter.

212
00:10:18,430 --> 00:10:20,230
Nous ne faisons plus la récursivité.

213
00:10:20,230 --> 00:10:23,730
>> Mais nous avons deux cas récursives.

214
00:10:23,730 --> 00:10:28,750
Si n est pair, nous faisons un récursif
cas, appelant n divisé par 2.

215
00:10:28,750 --> 00:10:33,950
Si n est impair, nous faisons un autre
récursif cas sur 3 fois n + 1.

216
00:10:33,950 --> 00:10:39,120
>> Et donc le but de cette vidéo est
de prendre une seconde, pause de la vidéo,

217
00:10:39,120 --> 00:10:42,440
et essayer d'écrire ce
fonction récursive Collatz

218
00:10:42,440 --> 00:10:47,640
où vous passez une valeur n, et
il calcule le nombre de mesures qu'il

219
00:10:47,640 --> 00:10:52,430
faut pour arriver à 1 si vous commencez à partir de n
et vous suivez ces étapes au-dessus.

220
00:10:52,430 --> 00:10:56,660
Si n est égal à 1, il faut 0 étapes.

221
00:10:56,660 --> 00:11:00,190
Sinon, ça va
faire un pas en plus mais

222
00:11:00,190 --> 00:11:06,200
de nombreuses mesures qu'il prend sur soit n
divisée par 2 si n est pair, ou 3n + 1

223
00:11:06,200 --> 00:11:08,100
si n est impair.

224
00:11:08,100 --> 00:11:11,190
>> Maintenant, je l'ai mis en place sur l'écran ici
un couple de tester des choses pour vous,

225
00:11:11,190 --> 00:11:15,690
un couple de cas de tests pour vous, pour voir
ce que ces divers nombres sont Collatz,

226
00:11:15,690 --> 00:11:17,440
et également une illustration
les étapes de

227
00:11:17,440 --> 00:11:20,390
besoin d'être traversé afin que vous puissiez
sorte de voir ce processus en action.

228
00:11:20,390 --> 00:11:24,222
Donc, si n est égal à
1, Collatz de n est 0.

229
00:11:24,222 --> 00:11:26,180
Vous ne devez pas faire
quoi que ce soit pour revenir à 1.

230
00:11:26,180 --> 00:11:27,600
Vous y êtes déjà.

231
00:11:27,600 --> 00:11:30,550
>> Si n est égal à 2, il faut
une étape pour arriver à 1.

232
00:11:30,550 --> 00:11:31,810
Vous commencez avec 2.

233
00:11:31,810 --> 00:11:33,100
Eh bien, pas 2 est égal à 1.

234
00:11:33,100 --> 00:11:36,580
Donc, ça va être une étape
Cependant, plus de nombreuses mesures qu'il

235
00:11:36,580 --> 00:11:38,015
prend n divisé par 2.

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

237
00:11:41,280 --> 00:11:42,910
>> 2 divisé par 2 est une.

238
00:11:42,910 --> 00:11:47,200
Il faut donc une étape en plus cependant
de nombreuses étapes qu'il faut pour 1.

239
00:11:47,200 --> 00:11:49,720
1 prend zéro étapes.

240
00:11:49,720 --> 00:11:52,370
>> Pour 3, comme vous pouvez le voir, il ya
tout à fait à quelques pas impliqués.

241
00:11:52,370 --> 00:11:53,590
Vous allez de 3.

242
00:11:53,590 --> 00:11:56,710
Et puis vous allez à
10, 5, 16, 8, 4, 2, 1.

243
00:11:56,710 --> 00:11:58,804
Il faut sept étapes pour revenir à 1.

244
00:11:58,804 --> 00:12:01,220
Et comme vous pouvez le voir, il ya une
quelques autres cas de test ici

245
00:12:01,220 --> 00:12:02,470
pour tester votre programme.

246
00:12:02,470 --> 00:12:03,970
Donc encore une fois, mettre en pause la vidéo.

247
00:12:03,970 --> 00:12:09,210
Et je vais revenir en arrière maintenant
ce que le processus réel est ici,

248
00:12:09,210 --> 00:12:11,390
ce que cette conjecture est.

249
00:12:11,390 --> 00:12:14,140
>> Voyez si vous pouvez comprendre
comment définir Collatz de n

250
00:12:14,140 --> 00:12:19,967
de sorte qu'il calcule combien
les étapes qu'il faut pour arriver à 1.

251
00:12:19,967 --> 00:12:23,050
Donc, je l'espère, vous avez suspendu la vidéo
et vous n'êtes pas simplement en attente pour moi

252
00:12:23,050 --> 00:12:25,820
pour vous donner la réponse ici.

253
00:12:25,820 --> 00:12:29,120
Mais si vous êtes, ainsi,
voici la réponse de toute façon.

254
00:12:29,120 --> 00:12:33,070
>> Alors, voici une définition possible
de la fonction Collatz.

255
00:12:33,070 --> 00:12:35,610
Notre base case-- si n est
égale à 1, nous revenons 0.

256
00:12:35,610 --> 00:12:38,250
Il ne prend pas
des mesures pour revenir à 1.

257
00:12:38,250 --> 00:12:42,710
>> Sinon, nous avons deux cases-- récursive
un pour les nombres pairs et un pour impair.

258
00:12:42,710 --> 00:12:47,164
La façon dont je test pour les nombres pairs
est de vérifier si n mod 2 est égal à 0.

259
00:12:47,164 --> 00:12:49,080
Ceci est essentiellement, à nouveau,
poser la question,

260
00:12:49,080 --> 00:12:54,050
si vous vous souvenez est-- ce mod si je
fracture n par 2 est-il pas de reste?

261
00:12:54,050 --> 00:12:55,470
Ce serait un nombre pair.

262
00:12:55,470 --> 00:13:01,370
>> Et donc, si n est égal à 0 mod 2 est
test est-ce un nombre pair.

263
00:13:01,370 --> 00:13:04,250
Si oui, je veux revenir 1,
parce que cela est certainement

264
00:13:04,250 --> 00:13:09,270
faire un pas en plus de Collatz
peu importe le nombre est la moitié de moi.

265
00:13:09,270 --> 00:13:13,910
Sinon, je veux revenir 1
ainsi Collatz de 3 fois n plus 1.

266
00:13:13,910 --> 00:13:16,060
Ce fut l'autre
étape récursive qui nous

267
00:13:16,060 --> 00:13:19,470
pourrait prendre pour calculer la
Collatz-- le nombre d'étapes

268
00:13:19,470 --> 00:13:22,610
il faut revenir
à 1 donné un numéro.

269
00:13:22,610 --> 00:13:24,610
Donc, je l'espère, cet exemple
vous a donné un peu

270
00:13:24,610 --> 00:13:26,620
d'un goût de procédures récursives.

271
00:13:26,620 --> 00:13:30,220
Heureusement, vous pensez que le code est un
peu plus belle si elle est appliquée

272
00:13:30,220 --> 00:13:32,760
dans un élégant, de manière récursive.

273
00:13:32,760 --> 00:13:35,955
Mais même si pas, la récursivité est un
vraiment puissant outil néanmoins.

274
00:13:35,955 --> 00:13:38,330
Et il est certainement quelque chose
pour obtenir votre tête autour,

275
00:13:38,330 --> 00:13:41,360
parce que vous serez en mesure de créer
programmes assez cool en utilisant la récursivité

276
00:13:41,360 --> 00:13:45,930
qui pourraient autrement être complexe à écrire
si vous utilisez des boucles et itération.

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

278
00:13:46,980 --> 00:13:48,780
Ceci est CS50.

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