Formation gratuite Python
Avec les piles, vous verrez efficacement comment chaque appel dans une fonction récursive est géré. La façon dont chaque appel est poussé sur la pile et sorti correspond exactement à la façon dont le programme est exécuté, et cela montrera clairement à quel point le calcul de grands nombres prendra beaucoup de temps, s'il n'est pas optimisé.
Illustrer la visualisation à l'aide d'une pile d'appels
Dans une pile d'appels, chaque fois qu'un appel de fonction renvoie un résultat, un cadre de pile représentant l'appel de fonction est extrait de la pile. Chaque fois que vous appelez une fonction, vous ajoutez un nouveau cadre de pile en haut de la pile.
Parcourir la pile d'appels
Les étapes sont décrites par les étiquettes bleues sous chaque pile d'appels. Vous verrez ce qui se passe étape par étape, vous aidant à comprendre les principes sous-jacents de la récursivité.
Vous voulez calculer F(5). Pour ce faire, vous allouez un bloc de mémoire sur le frame de pile pour stocker tous les calculs de la pile d'appels en un seul instant :
Notez que cela est appelé complexité spatiale, et c'est O(m) car il n'y a pas plus de m empiler les éléments sur le cadre en une seule fois.
Afin de calculer F(5), vous devez calculer F(4) comme indiqué par l'algorithme de Fibonacci, vous ajoutez donc cela à la pile :
Afin de calculer F(4), vous devez calculer F(3), vous ajoutez donc cela à la pile :
Afin de calculer F(3), vous devez calculer F(2), vous ajoutez donc cela à la pile :
Afin de calculer F(2), vous devez calculer F(1), qui est F(m – 1), donc vous l'ajoutez à la pile. Comme F(1) est un cas de base, il peut renvoyer un résultat immédiatement, vous donnant 1, et vous le retirez de la pile :
Maintenant, vous commencez à dérouler les résultats de manière récursive. F(1) renvoie le résultat à sa fonction appelante, F(2). Afin de calculer F(2) vous devez également calculer F(0), qui est F(m – 2) :
Vous ajoutez F(0) à la pile. Comme F(0) est un cas de base, il peut renvoyer un résultat immédiatement, vous donnant 0, et vous le retirez de la pile :
Ce résultat est renvoyé à F(2), et maintenant vous avez les deux F(m – 1) et F(m – 2) pour calculer F(2). tu calcules F(2) comme 1 et retirez-le de la pile :
Le résultat de F(2) est renvoyé à son appelant F(3). F(3) a également besoin du résultat de F(m – 2), F(1), pour compléter son calcul :
Après avoir ajouté l'appel de F(1) sur la pile, car il s'agit d'un cas de base et également dans le cache, vous pouvez renvoyer le résultat immédiatement et supprimer F(1) de la pile :
Vous pouvez compléter le calcul de F(3), qui est 2 :
vous supprimez F(3) de la pile après avoir terminé son calcul et renvoyer le résultat à son appelant, F(4). F(4) a également besoin du résultat de F(m – 2), F(2), pour compléter son calcul :
Vous ajoutez l'appel de F(2) à la pile. C'est là qu'intervient le cache astucieux. Vous l'avez déjà calculé, vous pouvez donc simplement récupérer la valeur du cache en appelant cache[2], évitant d'avoir à calculer récursivement le résultat pour F(2) à nouveau. Il renvoie 1, et vous supprimez F(2) de la pile :
F(2) est renvoyé à son appelant, et maintenant F(4) a tous les résultats dont il a besoin pour terminer son calcul, soit 3 :
vous supprimez F(4) de la pile et renvoyer son résultat à l'appelant final et d'origine, F(5) :
F(5) a maintenant le résultat de F(4) et a également besoin du résultat de F(m – 2), ce qui équivaut à F(3).
Vous ajoutez l'appel de fonction de F(3) à la pile, et le cache astucieux entre à nouveau en jeu. Vous avez précédemment calculé F(3), il vous suffit donc de le récupérer dans le cache en appelant cache[3], et vous obtenez le résultat. Il n'y a pas de processus récursif à calculer F(3). Il renvoie 2, et vous supprimez F(3) de la pile :
Maintenant F(5) a tous les prérequis pour calculer le résultat. En ajoutant 3 et 2, vous obtenez 5, et c'est la dernière étape avant de sauter F(5) hors de la pile, mettant fin à votre appel de fonction :
La pile est vide maintenant qu'elle a terminé le calcul F(5) :
Représenter les appels de fonction récursifs sous forme de piles vous permet d'avoir une compréhension plus concrète de tout le travail qui se déroule dans les coulisses. Il vous permet également de voir combien de ressources un appel de fonction récursive utilise lorsqu'elles sont affichées sous forme de blocs individuels.
En rassemblant toutes ces images, voici à quoi ressemble la séquence récursive de Fibonacci dans une pile en tant que visualisation complète :
Vous pouvez cliquer sur l'image ci-dessus pour zoomer sur les piles individuelles. À partir de l'image, vous pouvez voir combien de temps de calcul le cache économise. Si vous n'avez pas stocké les résultats calculés précédemment, certaines piles devraient être plus hautes et il faudrait plus de temps pour renvoyer les résultats à leurs appelants respectifs.
[ad_2]