Exponentiation

Essayons de créer une fonction récursive terminale calculant $b^n$, comme cette valeur s'obtient par des multiplications successives, l'accumulateur $a$ est une valeur par lequel le résultat sera multiplié. Nous souhaitons donc mettre un point une fonction $puissanceT(a, b, n)$ qui retourne $a(b^n)$. On obtiendra $b^n$ en initialisant $a$ à $1$. On détermine une relation de récurrence entre $b^n$ et $b^{n-1}$ de la sorte : $b^n = b.b^{n-1}$, donc $ab^n = (ab)b^{n-1}$, à savoir $puissanceT(a\times b, b, n-1)$. Allons-y,

Prouvons par récurrence sur $n$ que $puissanceT(a, b, n) = ab^n$.

• On a bien $puissanceT(a, b, 0) = a = ab^0$
• Supposons que $puissanceT(a^\prime, b, n-1) = a^\prime b^{n-1}$, donc $puissanceT(ab, b, n-1) = (ab)b^{n-1} = ab^n$. D'où $puissanceT(a, b, n) = puissanceT(ab, b, n-1) = ab^n$.

On calcule donc $b^n$ en invoquant $puissanceT(1, b, n)$. On redéfinit $puissance(b, n)$ de la sorte :

Vous avez des doutes ? Traduisez donc ces sous-programmes en C en observez ce qui se passe...