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.