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

2 puissance n