1
00:00:00,000 --> 00:00:05,587

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Si vous avez vu
la vidéo sur la récursivité,

3
00:00:07,670 --> 00:00:10,170
l'ensemble du processus pourrait avoir
semblait un peu magique.

4
00:00:10,170 --> 00:00:10,930
Comment cela fonctionne t-il?

5
00:00:10,930 --> 00:00:15,010
Comment les fonctions savent qu'ils
besoin d'attendre et d'attendre une autre valeur

6
00:00:15,010 --> 00:00:19,150
pour revenir à partir d'une fonction différente
appeler afin d'obtenir le résultat que nous voulons?

7
00:00:19,150 --> 00:00:22,550
>> Eh bien, la raison est parce que cela fonctionne
de quelque chose de connu comme la pile d'appel.

8
00:00:22,550 --> 00:00:26,360
Lorsque vous appelez une fonction, la
système met de côté l'espace dans la mémoire

9
00:00:26,360 --> 00:00:28,120
pour cette fonction pour faire son travail.

10
00:00:28,120 --> 00:00:31,720
Et nous appelons ces morceaux de mémoire
sont mis de côté pour chaque fonction

11
00:00:31,720 --> 00:00:35,670
appeler un cadre de pile ou un cadre de la fonction.

12
00:00:35,670 --> 00:00:38,290
Et comme vous vous en doutez,
ces cadres de pile

13
00:00:38,290 --> 00:00:41,000
vivre sur la partie de la pile de la mémoire.

14
00:00:41,000 --> 00:00:43,960

15
00:00:43,960 --> 00:00:47,540
>> Cadre de pile plus d'une fonction
peuvent exister dans la mémoire à un instant donné.

16
00:00:47,540 --> 00:00:51,240
Si principale appelle une fonction déménagement,
et déplacer appelle direction,

17
00:00:51,240 --> 00:00:54,460
tous les trois fonctions ont des cadres ouverts.

18
00:00:54,460 --> 00:00:57,350
Mais ils ne sont pas tous des cadres actifs.

19
00:00:57,350 --> 00:00:59,410
Ces cadres sont disposés dans une pile.

20
00:00:59,410 --> 00:01:01,820
Et le cadre de la
plus récemment appelé

21
00:01:01,820 --> 00:01:04,390
fonction est toujours sur le dessus de la pile.

22
00:01:04,390 --> 00:01:07,150
Et cela est toujours le cadre actif.

23
00:01:07,150 --> 00:01:10,420
Il ya seulement jamais vraiment un
fonction qui est active à la fois.

24
00:01:10,420 --> 00:01:12,420
Il est l'un au-dessus de la pile.

25
00:01:12,420 --> 00:01:17,620
>> Quand une fonction appelle une autre
fonction, il sorte de presse pause.

26
00:01:17,620 --> 00:01:20,590
Ce genre de est en attente, en attendant.

27
00:01:20,590 --> 00:01:24,050
Et un autre cadre de pile est poussé
sur la pile au-dessus de celui-ci.

28
00:01:24,050 --> 00:01:26,150
Et que devient le cadre actif.

29
00:01:26,150 --> 00:01:28,600
Et la trame immédiatement
dessous doit attendre

30
00:01:28,600 --> 00:01:33,560
jusqu'à ce qu'il soit à nouveau le cadre actif
avant qu'il puisse reprendre ses travaux.

31
00:01:33,560 --> 00:01:35,870
Quand une fonction est
complète et il est fait,

32
00:01:35,870 --> 00:01:37,720
son cadre est sorti de la pile.

33
00:01:37,720 --> 00:01:38,950
Voilà la terminologie.

34
00:01:38,950 --> 00:01:41,110
Et la trame immédiatement
en dessous, comme je viens de le dire,

35
00:01:41,110 --> 00:01:42,880
devient le nouveau cadre actif.

36
00:01:42,880 --> 00:01:45,960
>> Et si elle appelle une autre fonction,
ça va faire une pause à nouveau.

37
00:01:45,960 --> 00:01:49,290
Le cadre de pile de cette nouvelle fonction
être poussé sur la partie supérieure de la pile.

38
00:01:49,290 --> 00:01:50,650
Il va faire son travail.

39
00:01:50,650 --> 00:01:52,100
Il pourrait pop reculer.

40
00:01:52,100 --> 00:01:55,630
L'autre fonction
ci-dessous, il peut reprendre.

41
00:01:55,630 --> 00:02:00,080
>> Donc, nous allons passer par ce nouveau, à la recherche
à l'idée de la fonction factorielle

42
00:02:00,080 --> 00:02:03,070
que nous avons défini dans le
récursivité vidéo à voir

43
00:02:03,070 --> 00:02:07,770
exactement comment la magie derrière ce
processus récursif se déroule.

44
00:02:07,770 --> 00:02:09,870
Donc, cela est l'ensemble de notre fichier, non?

45
00:02:09,870 --> 00:02:14,000
Nous avons défini deux
functions-- principale et de fait.

46
00:02:14,000 --> 00:02:15,980
Et comme on pouvait s'y attendre,
tout programme de C va

47
00:02:15,980 --> 00:02:18,470
commencer à la première ligne du principal.

48
00:02:18,470 --> 00:02:21,660
>> Donc, nous créons un nouveau cadre de pile pour principale.

49
00:02:21,660 --> 00:02:23,320
Et il va commencer à courir.

50
00:02:23,320 --> 00:02:25,270
Appels principales printf.

51
00:02:25,270 --> 00:02:29,390
Et printf va
imprimer factorielle de 5.

52
00:02:29,390 --> 00:02:31,440
Eh bien, il ne sait pas
ce factorielle 5 est,

53
00:02:31,440 --> 00:02:35,620
et ainsi de cet appel est déjà
fonction sur un autre appel de fonction.

54
00:02:35,620 --> 00:02:37,270
Donc principale va faire une pause juste là.

55
00:02:37,270 --> 00:02:39,103
Je vais laisser son
flèche à droite là, couleur

56
00:02:39,103 --> 00:02:41,360
elle la même couleur que le
empiler image sur la droite,

57
00:02:41,360 --> 00:02:47,720
pour indiquer que le principal va geler
ici tout factorielle 5 est appelé.

58
00:02:47,720 --> 00:02:49,300
>> Donc factorielle 5 est appelé.

59
00:02:49,300 --> 00:02:53,160
Et il va commencer à la très
à compter de la fonction factorielle.

60
00:02:53,160 --> 00:02:55,440
Il pose la question, je suis égal à 1?

61
00:02:55,440 --> 00:02:56,810
5 est égal à 1?

62
00:02:56,810 --> 00:02:57,410
Et bien non.

63
00:02:57,410 --> 00:03:01,110
Donc, il va descendre à
l'autre partie, le retour n fois

64
00:03:01,110 --> 00:03:02,990
factorielle de n moins 1.

65
00:03:02,990 --> 00:03:03,490
Ok, ça marche.

66
00:03:03,490 --> 00:03:07,070
>> Alors maintenant, factorielle 5 est
selon un autre appel

67
00:03:07,070 --> 00:03:09,740
à factorielle, en passant
à 4 en tant que paramètre.

68
00:03:09,740 --> 00:03:14,210
Et si la factorielle
5 cadre, ce cadre rouge,

69
00:03:14,210 --> 00:03:17,160
va geler là
à cette ligne je l'ai indiqué

70
00:03:17,160 --> 00:03:21,914
et attendre factorielle de 4 pour terminer
ce qu'il faut faire pour que alors il

71
00:03:21,914 --> 00:03:23,330
peut redevenir le cadre actif.

72
00:03:23,330 --> 00:03:26,890
>> Donc factorielle de 4 commence à
le début de factorielle.

73
00:03:26,890 --> 00:03:28,556
4 est égal à 1?

74
00:03:28,556 --> 00:03:30,180
Non, il va faire la même chose.

75
00:03:30,180 --> 00:03:31,590
Il va aller en bas de la branche d'autre.

76
00:03:31,590 --> 00:03:33,240
Il va se rendre à cette ligne de code.

77
00:03:33,240 --> 00:03:35,710
OK, je vais revenir à quatre reprises.

78
00:03:35,710 --> 00:03:41,270
Oh, factorielle de 3-- afin factorielle
4 dépend de factorielle de 3 finition.

79
00:03:41,270 --> 00:03:43,055
>> Et donc il a besoin d'appeler factorielle de 3.

80
00:03:43,055 --> 00:03:45,180
Et que ça va passer par
le même processus à nouveau.

81
00:03:45,180 --> 00:03:48,200
Il commence par, arrive ici.

82
00:03:48,200 --> 00:03:50,980
Factorielle de 3 dépend
sur factorielle de 1.

83
00:03:50,980 --> 00:03:53,750
Donc factorielle de 2 démarre, obtient ici.

84
00:03:53,750 --> 00:03:56,310
Il dépend de factorielle de 1.

85
00:03:56,310 --> 00:03:57,430
Factorielle de 1 commence.

86
00:03:57,430 --> 00:03:57,650
>> D'ACCORD.

87
00:03:57,650 --> 00:03:59,775
Alors maintenant, nous obtenons
un endroit intéressant, non?

88
00:03:59,775 --> 00:04:02,190
Alors maintenant, 1 est égal à 1.

89
00:04:02,190 --> 00:04:05,130
Et si nous revenons 1.

90
00:04:05,130 --> 00:04:06,770
À ce stade, nous sommes de retour.

91
00:04:06,770 --> 00:04:07,880
La fonction est fait.

92
00:04:07,880 --> 00:04:11,140
Il est un comportement est-- il ya
rien d'autre pour qu'il fasse,

93
00:04:11,140 --> 00:04:17,006
et donc le cadre de pile pour
factorielle de 1 pops off.

94
00:04:17,006 --> 00:04:17,589
C'est fini.

95
00:04:17,589 --> 00:04:19,480
Il est revenu 1.

96
00:04:19,480 --> 00:04:23,370
Et maintenant, factorielle de 2, qui
était immédiatement la trame dessous

97
00:04:23,370 --> 00:04:26,160
dans la pile, devient le cadre actif.

98
00:04:26,160 --> 00:04:29,030
>> Et il peut ramasser
exactement là où il l'avait laissé.

99
00:04:29,030 --> 00:04:32,240
Il a été en attente d'une factorielle
de 1 à terminer son travail.

100
00:04:32,240 --> 00:04:33,610
Il a maintenant terminé.

101
00:04:33,610 --> 00:04:35,510
Et si nous sommes ici.

102
00:04:35,510 --> 00:04:38,080
>> Factorielle de 1 a retourné une valeur de 1.

103
00:04:38,080 --> 00:04:42,430
Donc factorielle de 2 canette
disons retourner 2 fois 1.

104
00:04:42,430 --> 00:04:43,680
Son travail est maintenant fait.

105
00:04:43,680 --> 00:04:49,110
Elle est retournée à 2 factorielle
de 3, qui l'attendait.

106
00:04:49,110 --> 00:04:53,370
Factorielle de 3 est désormais le cadre supérieur,
le châssis actif dans la pile.

107
00:04:53,370 --> 00:04:58,617
Et il dit, OK, bien, je vais
retourner à 3 fois, ce qui est 2 6.

108
00:04:58,617 --> 00:05:00,700
Et je vais donner ce que
valeur à factoriel

109
00:05:00,700 --> 00:05:03,430
de 4, qui a été en attente pour moi.

110
00:05:03,430 --> 00:05:04,500
J'ai fini.

111
00:05:04,500 --> 00:05:09,410
Factorielle de 3 apparaît de la pile, et
factorielle de 4 est maintenant le cadre actif.

112
00:05:09,410 --> 00:05:13,510
>> 4 dit, OK, je vais revenir 4 fois
la factorielle de 3, qui avait six ans.

113
00:05:13,510 --> 00:05:15,980
Ce fut de valeur
factorielle de 3 retourné.

114
00:05:15,980 --> 00:05:19,010
Et donc 4 fois 6 est 24.

115
00:05:19,010 --> 00:05:20,990
Et je vais passer
ce retour à factoriel

116
00:05:20,990 --> 00:05:23,160
5, qui a été en attente pour moi.

117
00:05:23,160 --> 00:05:25,270
Factorielle 5 est désormais le cadre actif.

118
00:05:25,270 --> 00:05:30,700
Il va revenir 5 fois
factorielle de 4-- 5 fois 24 ou 120--

119
00:05:30,700 --> 00:05:32,722
et de donner cette valeur
Retour au menu principal, qui a

120
00:05:32,722 --> 00:05:35,680
été très patiemment attendre pour une
temps au bas de la pile.

121
00:05:35,680 --> 00:05:36,640
>> Il est où il a commencé.

122
00:05:36,640 --> 00:05:37,670
Il a lancé cet appel.

123
00:05:37,670 --> 00:05:39,400
Plusieurs cadres ont repris au sommet.

124
00:05:39,400 --> 00:05:41,890
Il est maintenant de retour au sommet de la pile.

125
00:05:41,890 --> 00:05:43,450
Il est le cadre actif.

126
00:05:43,450 --> 00:05:47,810
Donc principale obtenu la valeur 120
retour de factorielle de 5.

127
00:05:47,810 --> 00:05:50,750
Il a été en attente de
imprimer cette valeur.

128
00:05:50,750 --> 00:05:51,657
Et puis il est fait.

129
00:05:51,657 --> 00:05:53,240
Il n'y a pas plus de lignes de code en principal.

130
00:05:53,240 --> 00:05:56,800
Alors cadre de principale pops off
la pile, et nous allons faire.

131
00:05:56,800 --> 00:05:58,992
>> Et voilà comment fonctionne la récursivité.

132
00:05:58,992 --> 00:06:00,200
Voilà comment les cadres de pile travaillent.

133
00:06:00,200 --> 00:06:03,120
Ces appels de fonction
cela se produisait auparavant

134
00:06:03,120 --> 00:06:06,620
sont juste en pause, en attendant
pour les appels ultérieurs

135
00:06:06,620 --> 00:06:12,050
pour finir afin qu'ils puissent devenir actif
cadre et finir ce qu'ils doivent faire.

136
00:06:12,050 --> 00:06:13,060
>> Je suis Doug Lloyd.

137
00:06:13,060 --> 00:06:14,880
Ceci est CS50.

138
00:06:14,880 --> 00:06:16,580