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

2
00:00:07,800 --> 00:00:10,190
>> ZAMYLA: Afin de comprendre
récursivité, vous devez

3
00:00:10,190 --> 00:00:13,820
d'abord comprendre la récursivité.

4
00:00:13,820 --> 00:00:17,280
Avoir la récursivité dans les moyens de la conception du programme
que vous avez auto-référentielle

5
00:00:17,280 --> 00:00:18,570
définitions.

6
00:00:18,570 --> 00:00:21,520
Structures de données récursives, par exemple,
sont des structures de données qui

7
00:00:21,520 --> 00:00:23,990
se inclure dans
leurs définitions.

8
00:00:23,990 --> 00:00:27,160
Mais aujourd'hui, nous allons nous concentrer
sur les fonctions récursives.

9
00:00:27,160 --> 00:00:31,160
>> Rappelons que les fonctions prennent entrées,
arguments, et retourner une valeur comme

10
00:00:31,160 --> 00:00:34,480
sortie représentée par
ce schéma ici.

11
00:00:34,480 --> 00:00:38,060
Nous pensons de la boîte que le corps de
la fonction, qui contient l'ensemble d'

12
00:00:38,060 --> 00:00:42,340
instructions qui interprètent la
entrée et fournir un signal de sortie.

13
00:00:42,340 --> 00:00:45,660
Regardons de plus près l'intérieur du corps de
la fonction pourrait révéler des appels à

14
00:00:45,660 --> 00:00:47,430
d'autres fonctions ainsi.

15
00:00:47,430 --> 00:00:51,300
Prenez cette simple fonction, foo, que
prend une seule chaîne en entrée et

16
00:00:51,300 --> 00:00:54,630
gravures combien de lettres
cette chaîne a.

17
00:00:54,630 --> 00:00:58,490
La fonction strlen, pour la longueur de chaîne,
est appelée, dont la sortie est

18
00:00:58,490 --> 00:01:01,890
requis pour l'appel à printf.

19
00:01:01,890 --> 00:01:05,770
>> Maintenant, ce qui rend une fonction récursive
spécial, c'est qu'il appelle lui-même.

20
00:01:05,770 --> 00:01:09,610
Nous pouvons représenter cette récursive
appeler avec cette flèche orange

21
00:01:09,610 --> 00:01:11,360
boucle sur lui-même.

22
00:01:11,360 --> 00:01:15,630
Mais lui-même l'exécution de nouveau ne fera que
faire un autre appel récursif, et

23
00:01:15,630 --> 00:01:17,150
autre et un autre.

24
00:01:17,150 --> 00:01:19,100
Mais les fonctions récursives
ne peut pas être infinie.

25
00:01:19,100 --> 00:01:23,490
Ils doivent finir en quelque sorte, ou votre
programme fonctionnera toujours.

26
00:01:23,490 --> 00:01:27,680
>> Nous devons donc trouver un moyen de briser
sur les appels récursifs.

27
00:01:27,680 --> 00:01:29,900
Nous appelons cela le cas de base.

28
00:01:29,900 --> 00:01:33,570
Lorsque l'état de cas de base est atteint,
la fonction retourne sans faire

29
00:01:33,570 --> 00:01:34,950
un autre appel récursif.

30
00:01:34,950 --> 00:01:39,610
Prenez cette fonction, salut, une fonction de vide
qui prend un int n en entrée.

31
00:01:39,610 --> 00:01:41,260
Le cas de base vient en premier.

32
00:01:41,260 --> 00:01:46,220
Si n est inférieur à zéro, l'impression et au revoir
retourner tous les autres cas, la

33
00:01:46,220 --> 00:01:49,400
fonction imprimer salut et exécuter
l'appel récursif.

34
00:01:49,400 --> 00:01:53,600
Un autre appel à la fonction salut avec
une valeur d'entrée décrémenté.

35
00:01:53,600 --> 00:01:56,790
>> Maintenant, même si nous imprimons salut, l'
fonction ne mettra pas fin jusqu'à ce que nous

36
00:01:56,790 --> 00:02:00,370
retourner son type de retour,
dans ce cas, nul.

37
00:02:00,370 --> 00:02:04,830
Ainsi, pour chaque n autre que le cas de base,
cette fonction retournera salut salut

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

39
00:02:06,890 --> 00:02:10,050
Comme cette fonction est nulle si, nous
ne sera pas explicitement le type de retour ici.

40
00:02:10,050 --> 00:02:12,000
Nous allons exécuter la fonction.

41
00:02:12,000 --> 00:02:16,960
Donc, appeler salut (3) permet d'imprimer salut et
exécuter salut (2) qui exécute salut (1) un

42
00:02:16,960 --> 00:02:20,560
qui exécute salut (0), où l'
cas de base condition est remplie.

43
00:02:20,560 --> 00:02:24,100
Alors salut (0) imprime au revoir et retours.

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

45
00:02:24,990 --> 00:02:28,690
Alors, maintenant que nous comprenons les bases de
fonctions récursives, dont ils ont besoin

46
00:02:28,690 --> 00:02:32,730
au moins un cas de base, ainsi qu'un
appel récursif, passons à un

47
00:02:32,730 --> 00:02:34,120
exemple plus significatif.

48
00:02:34,120 --> 00:02:37,830
Un qui ne se retourne pas
annuler n'importe quoi.

49
00:02:37,830 --> 00:02:41,340
>> Jetons un coup d'oeil à la factorielle
fonctionnement utilisé le plus souvent dans

50
00:02:41,340 --> 00:02:43,660
calculs de probabilité.

51
00:02:43,660 --> 00:02:48,120
Factorielle de n est le produit de tous les
nombre entier positif inférieur à

52
00:02:48,120 --> 00:02:49,400
et égal à n.

53
00:02:49,400 --> 00:02:56,731
Donc cinq factorielle est 5 fois 4 fois
3 fois 2 fois 1 pour donner 120.

54
00:02:56,731 --> 00:03:01,400
Quatre factorielle est 4 fois 3 fois
2 fois 1 pour donner 24.

55
00:03:01,400 --> 00:03:04,910
Et la même règle s'applique
à n'importe quel nombre entier positif.

56
00:03:04,910 --> 00:03:08,670
>> Alors, comment pourrions-nous écrire un récursive
fonction qui calcule la factorielle

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

58
00:03:09,960 --> 00:03:14,700
Eh bien, nous avons besoin d'identifier le
cas de base et l'appel récursif.

59
00:03:14,700 --> 00:03:18,250
L'appel récursif sera la même
dans tous les cas à l'exception de la base

60
00:03:18,250 --> 00:03:21,420
cas, ce qui signifie que nous devrons
trouver un modèle qui nous donnera notre

61
00:03:21,420 --> 00:03:23,350
résultat souhaité.

62
00:03:23,350 --> 00:03:30,270
>> Pour cet exemple, voir comment 5 factorielle
consiste à multiplier 4 par 3 par 2 par 1

63
00:03:30,270 --> 00:03:33,010
Et cette même multiplication
se trouve ici, l'

64
00:03:33,010 --> 00:03:35,430
définition de quatre factorielle.

65
00:03:35,430 --> 00:03:39,810
Nous voyons donc que 5 factorielle est
seulement 5 fois 4 factorielle.

66
00:03:39,810 --> 00:03:43,360
Maintenant pas cette tendance
à 4 factorielle ainsi?

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

68
00:03:44,280 --> 00:03:49,120
Nous voyons que 4 factorielle contient le
multiplication 3 fois 2 fois 1, la

69
00:03:49,120 --> 00:03:51,590
même définition que 3 factorielle.

70
00:03:51,590 --> 00:03:56,950
Donc 4 factorielle est égale à 4 fois 3
factorielle, et ainsi de suite et ainsi de suite notre

71
00:03:56,950 --> 00:04:02,170
modèle colle jusqu'à une factorielle, qui
par définition, est égal à 1.

72
00:04:02,170 --> 00:04:04,950
>> Il n'y a pas d'autre positif
entiers laissés.

73
00:04:04,950 --> 00:04:07,870
Nous avons donc le modèle pour
notre appel récursif.

74
00:04:07,870 --> 00:04:13,260
n le facteur est égal à n fois
la factorielle de n moins 1.

75
00:04:13,260 --> 00:04:14,370
Et notre scénario de base?

76
00:04:14,370 --> 00:04:17,370
Ce sera juste notre définition
de 1 factorielle.

77
00:04:17,370 --> 00:04:19,995
>> Alors maintenant, nous pouvons passer à l'écriture
code de la fonction.

78
00:04:19,995 --> 00:04:24,110
Pour le cas de base, nous avons la
état n est égal à égal à 1, où

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

80
00:04:25,780 --> 00:04:29,280
Puis passer à l'appel récursif,
nous reviendrons n fois la

81
00:04:29,280 --> 00:04:32,180
factorielle de n moins 1.

82
00:04:32,180 --> 00:04:33,590
>> Testons maintenant ce notre.

83
00:04:33,590 --> 00:04:35,900
Essayons factorielle 4.

84
00:04:35,900 --> 00:04:39,420
Par notre fonction c'est égal
à 4 fois par factorielle (3).

85
00:04:39,420 --> 00:04:43,040
Factorielle (3) est égal à
3 fois factoriels (2).

86
00:04:43,040 --> 00:04:48,700
Factorielle (2) est égale à 2 fois
factorielle (1), qui renvoie 1.

87
00:04:48,700 --> 00:04:52,490
Factorielle (2) renvoie maintenant 2 fois 1, 2.

88
00:04:52,490 --> 00:04:55,960
Factorielle (3) peut maintenant revenir
3 fois 2, 6.

89
00:04:55,960 --> 00:05:02,490
Et enfin, factorielle (4)
retourne 4 fois 6, 24.

90
00:05:02,490 --> 00:05:06,780
>> Si vous rencontrez des difficultés
avec l'appel récursif, prétendre que

91
00:05:06,780 --> 00:05:09,660
la fonction fonctionne déjà.

92
00:05:09,660 --> 00:05:13,450
Ce que je veux dire par là que vous devriez
faites confiance à vos appels récursifs à revenir

93
00:05:13,450 --> 00:05:15,100
les bonnes valeurs.

94
00:05:15,100 --> 00:05:18,960
Par exemple, si je sais que
factorielle (5) est égale à 5 fois

95
00:05:18,960 --> 00:05:24,870
factorielle (4), je vais faire confiance à cette
factorielle (4) va me donner 24.

96
00:05:24,870 --> 00:05:28,510
Pensez-y comme une variable, si vous
volonté, comme si vous avez déjà défini

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

98
00:05:30,070 --> 00:05:33,850
Donc pour tout factorielle (n), c'est
le produit de n et

99
00:05:33,850 --> 00:05:35,360
la factorielle précédente.

100
00:05:35,360 --> 00:05:38,130
Et ce factorielle précédente
est obtenu en appelant

101
00:05:38,130 --> 00:05:41,330
factorielle de n moins 1.

102
00:05:41,330 --> 00:05:45,130
>> Maintenant, voyez si vous pouvez mettre en œuvre une
récursive fonctionner vous-même.

103
00:05:45,130 --> 00:05:50,490
Chargez votre terminal, ou run.cs50.net,
et écrire une fonction somme

104
00:05:50,490 --> 00:05:54,770
qui prend un entier n et renvoie le
somme de tous positifs consécutive

105
00:05:54,770 --> 00:05:57,490
entiers de n à 1.

106
00:05:57,490 --> 00:06:01,000
J'ai écrit les sommes d'une certaine
valeurs pour vous aider notre.

107
00:06:01,000 --> 00:06:04,030
Tout d'abord, comprendre la
cas de base état.

108
00:06:04,030 --> 00:06:06,170
Ensuite, regardez somme (5).

109
00:06:06,170 --> 00:06:09,270
Pouvez-vous exprimer en termes
d'une autre somme?

110
00:06:09,270 --> 00:06:11,290
Maintenant, qu'en est-il somme (4)?

111
00:06:11,290 --> 00:06:15,630
Comment pouvez-vous exprimer somme (4)
en termes d'une autre somme?

112
00:06:15,630 --> 00:06:19,655
>> Une fois que vous avez somme (5) et la somme (4)
exprimé en d'autres sommes, voir

113
00:06:19,655 --> 00:06:22,970
si vous pouvez identifier un
modèle pour la somme (n).

114
00:06:22,970 --> 00:06:26,190
Si non, essayez quelques autres numéros
et d'exprimer leurs sommes en

115
00:06:26,190 --> 00:06:28,410
termes d'un autre nombre.

116
00:06:28,410 --> 00:06:31,930
En identifiant les modèles de discret
numéros, vous êtes bien sur votre chemin à

117
00:06:31,930 --> 00:06:34,320
identifier le modèle pour tout n.

118
00:06:34,320 --> 00:06:38,040
>> La récursivité est un outil très puissant,
alors bien sûr il n'est pas limité à

119
00:06:38,040 --> 00:06:39,820
des fonctions mathématiques.

120
00:06:39,820 --> 00:06:44,040
Récursivité peut être utilisé très efficacement
lorsqu'il s'agit d'arbres par exemple.

121
00:06:44,040 --> 00:06:47,210
Découvrez le court sur les arbres pour une
plus approfondis, mais pour l'instant

122
00:06:47,210 --> 00:06:51,140
rappeler que les arbres binaires de recherche, en
particulier, sont constitués de nœuds, chaque

123
00:06:51,140 --> 00:06:53,820
avec une valeur et deux pointeurs de noeuds.

124
00:06:53,820 --> 00:06:57,270
Habituellement, ceci est représenté par l'
nœud parent ayant un pointage de ligne

125
00:06:57,270 --> 00:07:01,870
au noeud enfant gauche et une
au noeud de droit de l'enfant.

126
00:07:01,870 --> 00:07:04,510
La structure d'une recherche binaire
arbre se prête bien

127
00:07:04,510 --> 00:07:05,940
à une recherche récursive.

128
00:07:05,940 --> 00:07:09,730
L'appel récursif passe soit dans la
gauche ou la droite noeud, mais plus

129
00:07:09,730 --> 00:07:10,950
de celle de l'arbre court.

130
00:07:10,950 --> 00:07:15,690
>> Dites que vous voulez effectuer une opération sur
chaque nœud unique dans un arbre binaire.

131
00:07:15,690 --> 00:07:17,410
Comment pourriez-vous aller à ce sujet?

132
00:07:17,410 --> 00:07:20,600
Eh bien, vous pourriez écrire un récursive
fonction qui effectue l'opération

133
00:07:20,600 --> 00:07:24,450
sur le noeud parent et fait un récursive
appeler à la même fonction,

134
00:07:24,450 --> 00:07:27,630
passant à gauche et à
nœuds enfants droite.

135
00:07:27,630 --> 00:07:31,650
Par exemple, cette fonction, foo, que
modifie la valeur d'un noeud donné et

136
00:07:31,650 --> 00:07:33,830
tous ses enfants à 1.

137
00:07:33,830 --> 00:07:37,400
Le cas de base d'une valeur NULL causes nœud
la fonction de retour, indiquant

138
00:07:37,400 --> 00:07:41,290
qu'il n'y a pas de noeuds
laissé dans ce sous-arbre.

139
00:07:41,290 --> 00:07:42,620
>> Marchons à travers elle.

140
00:07:42,620 --> 00:07:44,340
Le premier parent est de 13.

141
00:07:44,340 --> 00:07:47,930
Nous changeons la valeur à 1, puis appelons
notre fonction sur la gauche ainsi

142
00:07:47,930 --> 00:07:49,600
que le droit.

143
00:07:49,600 --> 00:07:53,910
La fonction foo est appelée sur la gauche
sous-arbre d'abord, si le nœud gauche

144
00:07:53,910 --> 00:07:57,730
seront réaffectés à 1 et foo
être appelée sur les enfants de ce nœud,

145
00:07:57,730 --> 00:08:01,900
d'abord la gauche, puis le droit,
et ainsi de suite et ainsi de suite.

146
00:08:01,900 --> 00:08:05,630
Et leur dire que les branches n'ont pas
tout plus d'enfants si le même processus

147
00:08:05,630 --> 00:08:09,700
continuera pour les droit de l'enfant
jusqu'à ce que les noeuds de l'arbre entier sont

148
00:08:09,700 --> 00:08:11,430
réaffecté à 1.

149
00:08:11,430 --> 00:08:15,390
>> Comme vous pouvez le voir, vous n'êtes pas limité
juste un appel récursif.

150
00:08:15,390 --> 00:08:17,930
Tout autant que va faire le travail.

151
00:08:17,930 --> 00:08:21,200
Et si vous aviez un arbre où chaque
noeud a eu trois enfants,

152
00:08:21,200 --> 00:08:23,100
Gauche, au milieu, et à droite?

153
00:08:23,100 --> 00:08:24,886
Comment pourriez-vous modifier foo?

154
00:08:24,886 --> 00:08:25,860
Eh bien, simple.

155
00:08:25,860 --> 00:08:30,250
Il suffit d'ajouter un autre appel récursif et
passer le pointeur de la médiane.

156
00:08:30,250 --> 00:08:34,549
>> La récursivité est très puissant et ne pas
mentionne élégant, mais il peut être un

157
00:08:34,549 --> 00:08:38,010
concept difficile au premier abord, alors
patient et prenez votre temps.

158
00:08:38,010 --> 00:08:39,370
Commencez par le cas de base.

159
00:08:39,370 --> 00:08:42,650
Il est généralement plus facile à identifier,
et alors vous pouvez travailler

160
00:08:42,650 --> 00:08:43,830
arrière à partir de là.

161
00:08:43,830 --> 00:08:46,190
Vous savez que vous devez atteindre votre
cas de base, de sorte que la puissance

162
00:08:46,190 --> 00:08:47,760
vous donner quelques conseils.

163
00:08:47,760 --> 00:08:53,120
Essayez d'exprimer un cas spécifique,
Quant aux autres cas, ou dans des sous-ensembles.

164
00:08:53,120 --> 00:08:54,700
>> Merci pour regarder ce court.

165
00:08:54,700 --> 00:08:58,920
À tout le moins, maintenant vous pouvez
comprendre les blagues de ce genre.

166
00:08:58,920 --> 00:09:01,250
Mon nom est Zamyla, et c'est CS50.

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

168
00:09:04,306 --> 00:09:07,170
>> Prenez cette fonction, salut, un
fonction vide qui prend

169
00:09:07,170 --> 00:09:09,212
un int, n, comme entrée.

170
00:09:09,212 --> 00:09:11,020
Le cas de base vient en premier.

171
00:09:11,020 --> 00:09:14,240
Si n est inférieur à 0, imprimer
"Bye" et retour.

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