Exécution d'une fonction récursive
Le principe⚓︎
Il est important de comprendre que chaque appel récursif met « en pause » l'exécution en cours, en attente d'obtenir le résultat qui est déterminé par l'appel suivant. Concrètement :
-
Les appels sont tour à tour mis « en pause » jusqu'au dernier appel qui fourni un résultat. On appelle cela le dépliage (ou la descente).
-
Ce résultat est ensuite transmis à l'appel précédent qui l'utilise pour calculer son propre résultat et le transmettre à l'appel précédent, et ainsi de suite jusqu'au premier appel qui peut alors calculer le résultat final. On appelle cela l'évaluation (ou la remontée).
Exemple
Nous allons étudier la fonction récursive (naïve) deux_puissance
qui prend en paramètre un entier positif n
et qui renvoie la valeur de \(2^n\)
Ecriture de la fonction récursive
- Le cas de base correspond à n = 0 et dans ce cas \(2^n=2^0=1\)
- Sinon, on peut calculer \(2^n\) en calculant \(2 \times 2^{n-1}\)
👉 on sait donc comment passer du calcul de \(2^n\) à celui de \(2^{n-1}\) pour notre appel récursif et on connaît le cas de base qui sera notre condition d'arrêt de la récursion
Tester
Tester
Des représentations⚓︎
Représentation 1
Représentation 2
Représentation 3
Visualisation avec Python tutor
Visualisation avec recursionvisualizer
Vos visualisations personnelles avec recursionvisualizer
# Tests
(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)