DOUG LLOYD: Se hai visto il video su ricorsione, l'intero processo può avere sembrava un po 'magico. Come funziona? Come fanno le funzioni sanno che bisogno di aspettare e aspettare un altro valore di ritorno da una funzione diversa chiamare al fine di ottenere il risultato che vogliamo? Beh, il motivo per cui funziona è perché di qualcosa di noto come lo stack di chiamate. Quando si chiama una funzione, la sistema mette da parte lo spazio in memoria per quella funzione di fare il suo lavoro. E noi chiamiamo questi blocchi di memoria che sono messe a riposo per ogni funzione chiamare un frame dello stack o una cornice di funzione. E come ci si potrebbe aspettare, questi stack frame vivere parte pila di memoria. 

Più di una funzione frame dello stack può esistere nella memoria in un dato momento. Se principale chiama un movimento di funzione, e spostare chiama la direzione, tutte e tre le funzioni hanno open frame. Ma non tutti hanno frame attivi. Questi telai sono disposti in una pila. E il telaio dal più recentemente chiamato funzione è sempre in cima alla pila. Ed è sempre il telaio attivo. C'è solo davvero mai uno funzione che è attiva alla volta. È quello in cima alla pila. 

Quando una funzione chiama un'altra funzione, una sorta di preme pausa. E 'sorta di è in attesa, in attesa. E un altro stack frame viene spinto nello stack su di esso. E che diventa la cornice attiva. E la cornice subito sotto deve attendere finché non è di nuovo il frame attivo prima che possa riprendere il suo lavoro. Quando una funzione è completo e il gioco è fatto, la sua struttura è estratto dallo stack. Questa è la terminologia. E la cornice subito sotto di essa, come ho appena detto, diventa il nuovo telaio attivo. 

E se chiama un'altra funzione, sta andando a mettere in pausa di nuovo. Stack frame che nuova funzione essere spinto sulla parte superiore della pila. Farà il suo lavoro. Potrebbe pop indietro. E l'altra funzione seguito può riprendere di nuovo. 

Quindi cerchiamo di passare attraverso questo nuovo, guardando all'idea della funzione fattoriale che abbiamo definito nel Video ricorsione per vedere esattamente come la magia dietro questo processo ricorsivo è in corso. Quindi questo è tutto il nostro file, giusto? Abbiamo definito due functions-- principale e di fatto. E come ci si potrebbe aspettare, qualsiasi programma C sta andando iniziare alla prima linea di principale. 

Quindi creiamo un nuovo stack frame per main. E sta andando a iniziare la corsa. Chiamate principali printf. E printf sta per stampare fattoriale di 5. Beh, non lo sa cosa fattoriale di 5 è, e quindi questa chiamata è già a seconda di un'altra chiamata di funzione. Quindi principale sta per mettere in pausa proprio lì. Sto andando lasciare la sua freccia proprio lì, colore lo stesso colore del impilare cornice sulla destra, per indicare che principale sta per congelare qui mentre fattoriale di 5 viene chiamato. 

Così fattoriale di 5 è chiamato. E sta andando per avviare al più inizio della funzione fattoriale. Si fa la domanda sono io uguale a 1? È 5 uguale a 1? Beh no. Così sta andando a scendere a l'altro parte, ritorno n volte fattoriale di n meno 1. Allora ok. 

Così ora, fattoriale di 5 è a seconda di un'altra chiamata a fattoriale, passando in 4 come parametro. E così il fattoriale di 5 telaio, che fanno da cornice rossa, sta per congelare proprio lì a quella linea ho indicato e attendere fattoriale di 4 per finire ciò che deve fare in modo che poi può diventare di nuovo il telaio attivo. 

Così fattoriale di 4 inizia a All'inizio del fattoriale. E '4 uguale a 1? No, quindi sta andando a fare la stessa cosa. E 'intenzione di andare giù il ramo altro. E 'intenzione di arrivare a quella linea di codice. OK, ho intenzione di tornare per quattro volte. Oh, fattoriale di 3-- così fattoriale di 4 dipende fattoriale di 3 finiture. 

E quindi ha bisogno di chiamare fattoriale di 3. E questo è andando passare attraverso lo stesso processo di nuovo. Si parte attraverso, arriva qui. Fattoriale di 3 dipende il fattoriale di 1. Così fattoriale di 2 partenze, ottiene qui. Dipende fattoriale di 1. Fattoriale di 1 inizia. 

OK. Così ora, stiamo ottenendo un luogo interessante, giusto? Così ora, 1 è uguale a 1. E così torniamo 1. A questo punto, ci torneremo. La funzione è fatto. E 'un comportamento è-- c'è altro da fare per fare, e così lo stack frame per fattoriale di 1 salta fuori. È finito. E 'tornato 1. Ed ora, fattoriale di 2, che è stato subito il telaio sottostante nello stack, diventa la cornice attiva. 

E può ritirare esattamente dove si era interrotto. E 'stato in attesa di un fattoriale di 1 per terminare il suo lavoro. Ora è terminato. E così eccoci qui. 

Fattoriale di 1 ha restituito un valore di 1. Così fattoriale di 2 lattina dire tornare 2 volte 1. Il suo lavoro ora è fatto. E 'tornato a 2 fattoriale 3, che è stato in attesa di esso. Fattoriale di 3 è ora il frame superiore, il telaio attivo nella pila. E così si dice, OK, bene, io vado per tornare 3 volte 2, che è 6. E ho intenzione di dare quel valore al fattoriale di 4, che è stato in attesa di me. Ho finito. Fattoriale di 3 salta dallo stack, e fattoriale di 4 è ora il telaio attivo. 

4 dice, OK, ho intenzione di tornare 4 volte il fattoriale di 3, che aveva sei anni. Questo è stato di valore che fattoriale di 3 restituito. E così 4 volte 6 è 24. E ho intenzione di passare che torna a fattoriale 5, che è stato in attesa di me. Fattoriale di 5 è ora il telaio attivo. E 'intenzione di tornare 5 volte fattoriale di 4-- 5 volte 24 o 120-- e dare quel valore torna alla pagina principale, che ha atteso con molta pazienza per un lungo al fondo della pila. 

E 'dove ha cominciato. Ha fatto questa chiamata. Diversi telai ha assunto in alto. Ora è tornato in cima alla pila. E 'il telaio attivo. Così principale ha ottenuto il valore di 120 di ritorno da fattoriale di 5. E 'stato in attesa di stampare tale valore. E poi è fatta. Non ci sono più righe di codice in principale. Così telaio del principale salta fuori lo stack, e abbiamo finito. 

Ed è così che funziona la ricorsione. Ecco come funzionano stack frame. Quelle chiamate di funzione quello che è successo in precedenza sono solo in pausa, in attesa per le chiamate successive alla fine in modo che possano diventare attivo cornice e finire quello che devono fare. 

Sono Doug Lloyd. Questo è CS50.