Invariants et récursivité

• Précondition $1\le k\le n$ ; postcondition : la valeur retournée est $\max T[0:k]$.

static int maxRec(int[] T, int k) {   // 1 ≤ k ≤ n
    if (k == 1) return T[0];          // max T[0:1] = T[0]
    int m = maxRec(T, k - 1);         // m = max T[0:k-1]
    return Math.max(m, T[k - 1]);     // max T[0:k]
}

Base : pour $k=1$, $T[0:1]$ ne contient que $T[0]$. Hérédité : pour $k\ge 2$, l'appel maxRec(T, k - 1) est fait sous sa précondition ($1\le k-1\le n$) ; on suppose qu'il retourne $m=\max T[0:k-1]$, et alors $\max (m,T[k-1])=\max T[0:k]$. Terminaison : $k$ décroît strictement et reste $\ge 1$. Comme pour la boucle, la base ne peut pas être $k=0$ : le maximum d'un tableau vide n'existe pas.

maxRec(T, n) fait $n$ appels ($8$ pour l'exemple, qui retourne $9$), tous en attente les uns des autres : la pile d'appels a une profondeur $n$. Avec la pile par défaut de Java, maxRec passe pour $n=10000$ et provoque une StackOverflowError pour $n=100000$ ; la boucle, elle, n'a pas de limite.

• Si $k\ne n$, alors $k+1\le n$ et $\max (m,T[k])=\max T[0:k+1]$ : l'appel récursif est fait sous la précondition, c'est la progression $I(m,k)\wedge k\ne n\Rightarrow I(\max (m,T[k]),k+1)$ de la boucle. Le variant $n-k$ est un entier positif qui diminue de $1$ à chaque appel. L'appel maxAcc(T, T[0], 1) établit la précondition comme l'initialisation $m=T[0]$, $k=1$ ; le test k == T.length est l'arrêt, qui retourne $m=\max T[0:n]$ ; l'appel récursif est un tour de boucle. Sur l'exemple, $(m,k)$ prend les valeurs $(3,1)$, $(3,2)$, $(4,3)$, $(4,4)$, $(4,5)$, $(9,6)$, $(9,7)$, $(9,8)$, exactement les états de la boucle du cours.

L'appel récursif est la dernière action de la fonction (récursion terminale) : rien ne reste à faire au retour, et la fonction n'est qu'une boucle écrite autrement. Java ne transforme pas ces appels en boucle : la profondeur de pile reste $n$.

• Récurrence forte sur $b$. Base : $a^0=1$. Hérédité : pour $b\ge 1$, $\lfloor b/2\rfloor <b$, donc par hypothèse $y=a^{\lfloor b/2\rfloor }$. Si $b$ est pair, $y^2=a^b$ ; si $b$ est impair, $b=2\lfloor b/2\rfloor +1$ et $a\times y^2=a^b$. Terminaison : $b$ décroît strictement jusqu'à $0$. C'est l'invariant $a^b=p\times x^e$ du cours, lu de l'autre côté : la boucle consomme les bits de $b$ à partir de la droite, la récursion à partir de la gauche, au retour des appels.

Pour $b=13$, les appels portent sur $13,6,3,1,0$ : $5$ appels, et puiss(3, 13) retourne $1594323$. Pour $b\ge 1$, $b$ est divisé par $2$ jusqu'à $1$, puis vient $0$ : $\lfloor {\log }_{2}b\rfloor +2$ appels ($11$ pour $b=1000$, $22$ pour $b=2^{20}$), soit $\Theta (\log b)$.

• Elle reste juste : la démonstration précédente vaut mot pour mot, chacun des deux appels retournant $a^{\lfloor b/2\rfloor }$. Mais chaque appel en fait maintenant deux : $C(0)=1$ et $C(b)=1+2C(\lfloor b/2\rfloor )$, d'où $C(2^k)=2^{k+2}-1=4b-1$ :

puissDouble(1, 13) : 31 appels
puissDouble(1, 1000) : 2047 appels
puissDouble(1, 1024) : 4095 appels

En général $C(b)=2^{\lfloor {\log }_{2}b\rfloor +2}-1$, compris entre $2b$ et $4b-1$ : la complexité est $\Theta (b)$, celle de la boucle naïve. Calculer une fois $a^{\lfloor b/2\rfloor }$ et le garder dans $y$ est tout le gain de l'exponentiation rapide.