La récursivité
165
Il faut bien voir qu’un appel de la méthode fac entraîne une allocation d’espace pour les
éventuelles variables locales (ici, il n’y en a aucune), le paramètre n et le résultat. Or chaque
nouvel appel de fac, à l’intérieur de fac, provoque une telle allocation, sans que les emplacements précédents n’aient été libérés.
Il y a donc une sorte d’empilement des espaces alloués aux informations gérées par la méthode, parallèlement à un empilement des appels de la méthode. Ce n’est que lors de l’exécution de la première instruction retourne que l’on commencera à « dépiler » les appels et les
emplacements, donc à libérer de l’espace mémoire sur la pile.
Voici comment vous pourriez modifier la méthode fac pour qu’elle vous permette de suivre
ses différents empilements et dépilements :
// programme utilisant la fonction fac
entier n
écrire «donnez un entier positif : »
lire n
écrire «Voici sa factorielle : », fac(n)
// la fonction fac
entier fonction fac (entier n)
{ entier res
écrire «** entree dans fac : n = », n
si n<=1 alors res := 1
sinon res := fac(n-1) * n
écrire «** sortie de fac :
res = », res
retourne res
}
donnez un entier positif : 5
** entree dans fac : n = 5
** entree dans fac : n = 4
** entree dans fac : n = 3
** entree dans fac : n = 2
** entree dans fac : n = 1
** sortie de fac :
res = 1
** sortie de fac :
res = 2
** sortie de fac :
res = 6
** sortie de fac :
res = 24
** sortie de fac :
res = 120
Voici sa factorielle : 120
Suivi des empilements et dépilements des appels d’une fonction récursive
Notez bien que nous n’avons programmé la fonction fac sous forme récursive que pour
l’exemple. Il est clair qu’elle pourrait être écrite de manière « itérative » classique, comme
nous l’avions fait au paragraphe 5 du chapitre 6, page 107 :