Le let qui change la complexité

(* A *) let rec puiss x n =
          if n = 0 then 1
          else let m = puiss x (n/2) in
               if n mod 2 = 0 then m * m else m * m * x

(* B *) let rec puiss x n =
          if n = 0 then 1
          else if n mod 2 = 0 then puiss x (n/2) * puiss x (n/2)
          else puiss x (n/2) * puiss x (n/2) * x

Mesuré, en instrumentant les deux fonctions d'un compteur :

n=10  A :  6 multiplications,  5 appels     B :  25 multiplications,  31 appels
n=20  A :  7 multiplications,  6 appels     B :  51 multiplications,  63 appels
n=40  A :  8 multiplications,  7 appels     B : 103 multiplications, 127 appels

Pourquoi. Dans A, le let m = ... calcule $x^{\lfloor n/2\rfloor }$ une fois et le nomme. La récurrence est $T(n)=T(n/2)+O(1)$, deuxième forme du cours avec $a=1$ : $T(n)=\Theta (\log n)$.

Dans B, l'expression puiss x (n/2) apparaît deux fois, donc elle est évaluée deux fois. La récurrence devient $T(n)=2T(n/2)+O(1)$, soit $a=2$ : le nombre d'appels double à chaque niveau, il y en a $2^{\lfloor {\log }_{2}n\rfloor +1}-1$, et $T(n)=\Theta (n)$. On mesure bien $127=2^7-1$ appels pour $n=40$, contre $7$ pour A.

Le piège nommé. Une variable n'est pas un raccourci d'écriture : en écrivant deux fois la même expression, on demande deux fois le même calcul. Tout le gain de l'exponentiation rapide — le gain qui fait passer de $\Theta (n)$ à $\Theta (\log n)$ — tient à ce let. Et la version B est même pire que la méthode naïve à $n$ multiplications, puisqu'elle en fait $103$ pour $n=40$.

À retenir comme réflexe : dès qu'un appel récursif figure deux fois dans une expression, comptez les nœuds de l'arbre des appels avant de conclure quoi que ce soit sur le coût.