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

2
00:00:05,587 --> 00:00:07,670
DOUG LLOYD: Se hai visto
il video su ricorsione,

3
00:00:07,670 --> 00:00:10,170
l'intero processo può avere
sembrava un po 'magico.

4
00:00:10,170 --> 00:00:10,930
Come funziona?

5
00:00:10,930 --> 00:00:15,010
Come fanno le funzioni sanno che
bisogno di aspettare e aspettare un altro valore

6
00:00:15,010 --> 00:00:19,150
di ritorno da una funzione diversa
chiamare al fine di ottenere il risultato che vogliamo?

7
00:00:19,150 --> 00:00:22,550
>> Beh, il motivo per cui funziona è perché
di qualcosa di noto come lo stack di chiamate.

8
00:00:22,550 --> 00:00:26,360
Quando si chiama una funzione, la
sistema mette da parte lo spazio in memoria

9
00:00:26,360 --> 00:00:28,120
per quella funzione di fare il suo lavoro.

10
00:00:28,120 --> 00:00:31,720
E noi chiamiamo questi blocchi di memoria che
sono messe a riposo per ogni funzione

11
00:00:31,720 --> 00:00:35,670
chiamare un frame dello stack o una cornice di funzione.

12
00:00:35,670 --> 00:00:38,290
E come ci si potrebbe aspettare,
questi stack frame

13
00:00:38,290 --> 00:00:41,000
vivere parte pila di memoria.

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

15
00:00:43,960 --> 00:00:47,540
>> Più di una funzione frame dello stack
può esistere nella memoria in un dato momento.

16
00:00:47,540 --> 00:00:51,240
Se principale chiama un movimento di funzione,
e spostare chiama la direzione,

17
00:00:51,240 --> 00:00:54,460
tutte e tre le funzioni hanno open frame.

18
00:00:54,460 --> 00:00:57,350
Ma non tutti hanno frame attivi.

19
00:00:57,350 --> 00:00:59,410
Questi telai sono disposti in una pila.

20
00:00:59,410 --> 00:01:01,820
E il telaio dal
più recentemente chiamato

21
00:01:01,820 --> 00:01:04,390
funzione è sempre in cima alla pila.

22
00:01:04,390 --> 00:01:07,150
Ed è sempre il telaio attivo.

23
00:01:07,150 --> 00:01:10,420
C'è solo davvero mai uno
funzione che è attiva alla volta.

24
00:01:10,420 --> 00:01:12,420
È quello in cima alla pila.

25
00:01:12,420 --> 00:01:17,620
>> Quando una funzione chiama un'altra
funzione, una sorta di preme pausa.

26
00:01:17,620 --> 00:01:20,590
E 'sorta di è in attesa, in attesa.

27
00:01:20,590 --> 00:01:24,050
E un altro stack frame viene spinto
nello stack su di esso.

28
00:01:24,050 --> 00:01:26,150
E che diventa la cornice attiva.

29
00:01:26,150 --> 00:01:28,600
E la cornice subito
sotto deve attendere

30
00:01:28,600 --> 00:01:33,560
finché non è di nuovo il frame attivo
prima che possa riprendere il suo lavoro.

31
00:01:33,560 --> 00:01:35,870
Quando una funzione è
completo e il gioco è fatto,

32
00:01:35,870 --> 00:01:37,720
la sua struttura è estratto dallo stack.

33
00:01:37,720 --> 00:01:38,950
Questa è la terminologia.

34
00:01:38,950 --> 00:01:41,110
E la cornice subito
sotto di essa, come ho appena detto,

35
00:01:41,110 --> 00:01:42,880
diventa il nuovo telaio attivo.

36
00:01:42,880 --> 00:01:45,960
>> E se chiama un'altra funzione,
sta andando a mettere in pausa di nuovo.

37
00:01:45,960 --> 00:01:49,290
Stack frame che nuova funzione
essere spinto sulla parte superiore della pila.

38
00:01:49,290 --> 00:01:50,650
Farà il suo lavoro.

39
00:01:50,650 --> 00:01:52,100
Potrebbe pop indietro.

40
00:01:52,100 --> 00:01:55,630
E l'altra funzione
seguito può riprendere di nuovo.

41
00:01:55,630 --> 00:02:00,080
>> Quindi cerchiamo di passare attraverso questo nuovo, guardando
all'idea della funzione fattoriale

42
00:02:00,080 --> 00:02:03,070
che abbiamo definito nel
Video ricorsione per vedere

43
00:02:03,070 --> 00:02:07,770
esattamente come la magia dietro questo
processo ricorsivo è in corso.

44
00:02:07,770 --> 00:02:09,870
Quindi questo è tutto il nostro file, giusto?

45
00:02:09,870 --> 00:02:14,000
Abbiamo definito due
functions-- principale e di fatto.

46
00:02:14,000 --> 00:02:15,980
E come ci si potrebbe aspettare,
qualsiasi programma C sta andando

47
00:02:15,980 --> 00:02:18,470
iniziare alla prima linea di principale.

48
00:02:18,470 --> 00:02:21,660
>> Quindi creiamo un nuovo stack frame per main.

49
00:02:21,660 --> 00:02:23,320
E sta andando a iniziare la corsa.

50
00:02:23,320 --> 00:02:25,270
Chiamate principali printf.

51
00:02:25,270 --> 00:02:29,390
E printf sta per
stampare fattoriale di 5.

52
00:02:29,390 --> 00:02:31,440
Beh, non lo sa
cosa fattoriale di 5 è,

53
00:02:31,440 --> 00:02:35,620
e quindi questa chiamata è già
a seconda di un'altra chiamata di funzione.

54
00:02:35,620 --> 00:02:37,270
Quindi principale sta per mettere in pausa proprio lì.

55
00:02:37,270 --> 00:02:39,103
Sto andando lasciare la sua
freccia proprio lì, colore

56
00:02:39,103 --> 00:02:41,360
lo stesso colore del
impilare cornice sulla destra,

57
00:02:41,360 --> 00:02:47,720
per indicare che principale sta per congelare
qui mentre fattoriale di 5 viene chiamato.

58
00:02:47,720 --> 00:02:49,300
>> Così fattoriale di 5 è chiamato.

59
00:02:49,300 --> 00:02:53,160
E sta andando per avviare al più
inizio della funzione fattoriale.

60
00:02:53,160 --> 00:02:55,440
Si fa la domanda sono io uguale a 1?

61
00:02:55,440 --> 00:02:56,810
È 5 uguale a 1?

62
00:02:56,810 --> 00:02:57,410
Beh no.

63
00:02:57,410 --> 00:03:01,110
Così sta andando a scendere a
l'altro parte, ritorno n volte

64
00:03:01,110 --> 00:03:02,990
fattoriale di n meno 1.

65
00:03:02,990 --> 00:03:03,490
Allora ok.

66
00:03:03,490 --> 00:03:07,070
>> Così ora, fattoriale di 5 è
a seconda di un'altra chiamata

67
00:03:07,070 --> 00:03:09,740
a fattoriale, passando
in 4 come parametro.

68
00:03:09,740 --> 00:03:14,210
E così il fattoriale di
5 telaio, che fanno da cornice rossa,

69
00:03:14,210 --> 00:03:17,160
sta per congelare proprio lì
a quella linea ho indicato

70
00:03:17,160 --> 00:03:21,914
e attendere fattoriale di 4 per finire
ciò che deve fare in modo che poi

71
00:03:21,914 --> 00:03:23,330
può diventare di nuovo il telaio attivo.

72
00:03:23,330 --> 00:03:26,890
>> Così fattoriale di 4 inizia a
All'inizio del fattoriale.

73
00:03:26,890 --> 00:03:28,556
E '4 uguale a 1?

74
00:03:28,556 --> 00:03:30,180
No, quindi sta andando a fare la stessa cosa.

75
00:03:30,180 --> 00:03:31,590
E 'intenzione di andare giù il ramo altro.

76
00:03:31,590 --> 00:03:33,240
E 'intenzione di arrivare a quella linea di codice.

77
00:03:33,240 --> 00:03:35,710
OK, ho intenzione di tornare per quattro volte.

78
00:03:35,710 --> 00:03:41,270
Oh, fattoriale di 3-- così fattoriale di
4 dipende fattoriale di 3 finiture.

79
00:03:41,270 --> 00:03:43,055
>> E quindi ha bisogno di chiamare fattoriale di 3.

80
00:03:43,055 --> 00:03:45,180
E questo è andando passare attraverso
lo stesso processo di nuovo.

81
00:03:45,180 --> 00:03:48,200
Si parte attraverso, arriva qui.

82
00:03:48,200 --> 00:03:50,980
Fattoriale di 3 dipende
il fattoriale di 1.

83
00:03:50,980 --> 00:03:53,750
Così fattoriale di 2 partenze, ottiene qui.

84
00:03:53,750 --> 00:03:56,310
Dipende fattoriale di 1.

85
00:03:56,310 --> 00:03:57,430
Fattoriale di 1 inizia.

86
00:03:57,430 --> 00:03:57,650
>> OK.

87
00:03:57,650 --> 00:03:59,775
Così ora, stiamo ottenendo
un luogo interessante, giusto?

88
00:03:59,775 --> 00:04:02,190
Così ora, 1 è uguale a 1.

89
00:04:02,190 --> 00:04:05,130
E così torniamo 1.

90
00:04:05,130 --> 00:04:06,770
A questo punto, ci torneremo.

91
00:04:06,770 --> 00:04:07,880
La funzione è fatto.

92
00:04:07,880 --> 00:04:11,140
E 'un comportamento è-- c'è
altro da fare per fare,

93
00:04:11,140 --> 00:04:17,006
e così lo stack frame per
fattoriale di 1 salta fuori.

94
00:04:17,006 --> 00:04:17,589
È finito.

95
00:04:17,589 --> 00:04:19,480
E 'tornato 1.

96
00:04:19,480 --> 00:04:23,370
Ed ora, fattoriale di 2, che
è stato subito il telaio sottostante

97
00:04:23,370 --> 00:04:26,160
nello stack, diventa la cornice attiva.

98
00:04:26,160 --> 00:04:29,030
>> E può ritirare
esattamente dove si era interrotto.

99
00:04:29,030 --> 00:04:32,240
E 'stato in attesa di un fattoriale
di 1 per terminare il suo lavoro.

100
00:04:32,240 --> 00:04:33,610
Ora è terminato.

101
00:04:33,610 --> 00:04:35,510
E così eccoci qui.

102
00:04:35,510 --> 00:04:38,080
>> Fattoriale di 1 ha restituito un valore di 1.

103
00:04:38,080 --> 00:04:42,430
Così fattoriale di 2 lattina
dire tornare 2 volte 1.

104
00:04:42,430 --> 00:04:43,680
Il suo lavoro ora è fatto.

105
00:04:43,680 --> 00:04:49,110
E 'tornato a 2 fattoriale
3, che è stato in attesa di esso.

106
00:04:49,110 --> 00:04:53,370
Fattoriale di 3 è ora il frame superiore,
il telaio attivo nella pila.

107
00:04:53,370 --> 00:04:58,617
E così si dice, OK, bene, io vado
per tornare 3 volte 2, che è 6.

108
00:04:58,617 --> 00:05:00,700
E ho intenzione di dare quel
valore al fattoriale

109
00:05:00,700 --> 00:05:03,430
di 4, che è stato in attesa di me.

110
00:05:03,430 --> 00:05:04,500
Ho finito.

111
00:05:04,500 --> 00:05:09,410
Fattoriale di 3 salta dallo stack, e
fattoriale di 4 è ora il telaio attivo.

112
00:05:09,410 --> 00:05:13,510
>> 4 dice, OK, ho intenzione di tornare 4 volte
il fattoriale di 3, che aveva sei anni.

113
00:05:13,510 --> 00:05:15,980
Questo è stato di valore che
fattoriale di 3 restituito.

114
00:05:15,980 --> 00:05:19,010
E così 4 volte 6 è 24.

115
00:05:19,010 --> 00:05:20,990
E ho intenzione di passare
che torna a fattoriale

116
00:05:20,990 --> 00:05:23,160
5, che è stato in attesa di me.

117
00:05:23,160 --> 00:05:25,270
Fattoriale di 5 è ora il telaio attivo.

118
00:05:25,270 --> 00:05:30,700
E 'intenzione di tornare 5 volte
fattoriale di 4-- 5 volte 24 o 120--

119
00:05:30,700 --> 00:05:32,722
e dare quel valore
torna alla pagina principale, che ha

120
00:05:32,722 --> 00:05:35,680
atteso con molta pazienza per un
lungo al fondo della pila.

121
00:05:35,680 --> 00:05:36,640
>> E 'dove ha cominciato.

122
00:05:36,640 --> 00:05:37,670
Ha fatto questa chiamata.

123
00:05:37,670 --> 00:05:39,400
Diversi telai ha assunto in alto.

124
00:05:39,400 --> 00:05:41,890
Ora è tornato in cima alla pila.

125
00:05:41,890 --> 00:05:43,450
E 'il telaio attivo.

126
00:05:43,450 --> 00:05:47,810
Così principale ha ottenuto il valore di 120
di ritorno da fattoriale di 5.

127
00:05:47,810 --> 00:05:50,750
E 'stato in attesa di
stampare tale valore.

128
00:05:50,750 --> 00:05:51,657
E poi è fatta.

129
00:05:51,657 --> 00:05:53,240
Non ci sono più righe di codice in principale.

130
00:05:53,240 --> 00:05:56,800
Così telaio del principale salta fuori
lo stack, e abbiamo finito.

131
00:05:56,800 --> 00:05:58,992
>> Ed è così che funziona la ricorsione.

132
00:05:58,992 --> 00:06:00,200
Ecco come funzionano stack frame.

133
00:06:00,200 --> 00:06:03,120
Quelle chiamate di funzione
quello che è successo in precedenza

134
00:06:03,120 --> 00:06:06,620
sono solo in pausa, in attesa
per le chiamate successive

135
00:06:06,620 --> 00:06:12,050
alla fine in modo che possano diventare attivo
cornice e finire quello che devono fare.

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

137
00:06:13,060 --> 00:06:14,880
Questo è CS50.

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