DOUG LLOYD: Si vous avez vu la vidéo sur la récursivité,
l'ensemble du processus pourrait avoir semblait un peu magique.
Comment cela fonctionne t-il?
Comment les fonctions savent qu'ils besoin d'attendre et d'attendre une autre valeur
pour revenir à partir d'une fonction différente appeler afin d'obtenir le résultat que nous voulons?
>> Eh bien, la raison est parce que cela fonctionne de quelque chose de connu comme la pile d'appel.
Lorsque vous appelez une fonction, la système met de côté l'espace dans la mémoire
pour cette fonction pour faire son travail.
Et nous appelons ces morceaux de mémoire sont mis de côté pour chaque fonction
appeler un cadre de pile ou un cadre de la fonction.
Et comme vous vous en doutez, ces cadres de pile
vivre sur la partie de la pile de la mémoire.
>> Cadre de pile plus d'une fonction peuvent exister dans la mémoire à un instant donné.
Si principale appelle une fonction déménagement, et déplacer appelle direction,
tous les trois fonctions ont des cadres ouverts.
Mais ils ne sont pas tous des cadres actifs.
Ces cadres sont disposés dans une pile.
Et le cadre de la plus récemment appelé
fonction est toujours sur le dessus de la pile.
Et cela est toujours le cadre actif.
Il ya seulement jamais vraiment un fonction qui est active à la fois.
Il est l'un au-dessus de la pile.
>> Quand une fonction appelle une autre fonction, il sorte de presse pause.
Ce genre de est en attente, en attendant.
Et un autre cadre de pile est poussé sur la pile au-dessus de celui-ci.
Et que devient le cadre actif.
Et la trame immédiatement dessous doit attendre
jusqu'à ce qu'il soit à nouveau le cadre actif avant qu'il puisse reprendre ses travaux.
Quand une fonction est complète et il est fait,
son cadre est sorti de la pile.
Voilà la terminologie.
Et la trame immédiatement en dessous, comme je viens de le dire,
devient le nouveau cadre actif.
>> Et si elle appelle une autre fonction, ça va faire une pause à nouveau.
Le cadre de pile de cette nouvelle fonction être poussé sur la partie supérieure de la pile.
Il va faire son travail.
Il pourrait pop reculer.
L'autre fonction ci-dessous, il peut reprendre.
>> Donc, nous allons passer par ce nouveau, à la recherche à l'idée de la fonction factorielle
que nous avons défini dans le récursivité vidéo à voir
exactement comment la magie derrière ce processus récursif se déroule.
Donc, cela est l'ensemble de notre fichier, non?
Nous avons défini deux functions-- principale et de fait.
Et comme on pouvait s'y attendre, tout programme de C va
commencer à la première ligne du principal.
>> Donc, nous créons un nouveau cadre de pile pour principale.
Et il va commencer à courir.
Appels principales printf.
Et printf va imprimer factorielle de 5.
Eh bien, il ne sait pas ce factorielle 5 est,
et ainsi de cet appel est déjà fonction sur un autre appel de fonction.
Donc principale va faire une pause juste là.
Je vais laisser son flèche à droite là, couleur
elle la même couleur que le empiler image sur la droite,
pour indiquer que le principal va geler ici tout factorielle 5 est appelé.
>> Donc factorielle 5 est appelé.
Et il va commencer à la très à compter de la fonction factorielle.
Il pose la question, je suis égal à 1?
5 est égal à 1?
Et bien non.
Donc, il va descendre à l'autre partie, le retour n fois
factorielle de n moins 1.
Ok, ça marche.
>> Alors maintenant, factorielle 5 est selon un autre appel
à factorielle, en passant à 4 en tant que paramètre.
Et si la factorielle 5 cadre, ce cadre rouge,
va geler là à cette ligne je l'ai indiqué
et attendre factorielle de 4 pour terminer ce qu'il faut faire pour que alors il
peut redevenir le cadre actif.
>> Donc factorielle de 4 commence à le début de factorielle.
4 est égal à 1?
Non, il va faire la même chose.
Il va aller en bas de la branche d'autre.
Il va se rendre à cette ligne de code.
OK, je vais revenir à quatre reprises.
Oh, factorielle de 3-- afin factorielle 4 dépend de factorielle de 3 finition.
>> Et donc il a besoin d'appeler factorielle de 3.
Et que ça va passer par le même processus à nouveau.
Il commence par, arrive ici.
Factorielle de 3 dépend sur factorielle de 1.
Donc factorielle de 2 démarre, obtient ici.
Il dépend de factorielle de 1.
Factorielle de 1 commence.
>> D'ACCORD.
Alors maintenant, nous obtenons un endroit intéressant, non?
Alors maintenant, 1 est égal à 1.
Et si nous revenons 1.
À ce stade, nous sommes de retour.
La fonction est fait.
Il est un comportement est-- il ya rien d'autre pour qu'il fasse,
et donc le cadre de pile pour factorielle de 1 pops off.
C'est fini.
Il est revenu 1.
Et maintenant, factorielle de 2, qui était immédiatement la trame dessous
dans la pile, devient le cadre actif.
>> Et il peut ramasser exactement là où il l'avait laissé.
Il a été en attente d'une factorielle de 1 à terminer son travail.
Il a maintenant terminé.
Et si nous sommes ici.
>> Factorielle de 1 a retourné une valeur de 1.
Donc factorielle de 2 canette disons retourner 2 fois 1.
Son travail est maintenant fait.
Elle est retournée à 2 factorielle de 3, qui l'attendait.
Factorielle de 3 est désormais le cadre supérieur, le châssis actif dans la pile.
Et il dit, OK, bien, je vais retourner à 3 fois, ce qui est 2 6.
Et je vais donner ce que valeur à factoriel
de 4, qui a été en attente pour moi.
J'ai fini.
Factorielle de 3 apparaît de la pile, et factorielle de 4 est maintenant le cadre actif.
>> 4 dit, OK, je vais revenir 4 fois la factorielle de 3, qui avait six ans.
Ce fut de valeur factorielle de 3 retourné.
Et donc 4 fois 6 est 24.
Et je vais passer ce retour à factoriel
5, qui a été en attente pour moi.
Factorielle 5 est désormais le cadre actif.
Il va revenir 5 fois factorielle de 4-- 5 fois 24 ou 120--
et de donner cette valeur Retour au menu principal, qui a
été très patiemment attendre pour une temps au bas de la pile.
>> Il est où il a commencé.
Il a lancé cet appel.
Plusieurs cadres ont repris au sommet.
Il est maintenant de retour au sommet de la pile.
Il est le cadre actif.
Donc principale obtenu la valeur 120 retour de factorielle de 5.
Il a été en attente de imprimer cette valeur.
Et puis il est fait.
Il n'y a pas plus de lignes de code en principal.
Alors cadre de principale pops off la pile, et nous allons faire.
>> Et voilà comment fonctionne la récursivité.
Voilà comment les cadres de pile travaillent.
Ces appels de fonction cela se produisait auparavant
sont juste en pause, en attendant pour les appels ultérieurs
pour finir afin qu'ils puissent devenir actif cadre et finir ce qu'ils doivent faire.
>> Je suis Doug Lloyd.
Ceci est CS50.