Prépa Code Connexion Inscription

Écrire une fonction récursive puissance : int -> int -> int telle que puissance q p calcule $q^p$ en utilisant le principe de l'exponentiation rapide :

• $q^0 = 1$
• Si $p$ est pair : $q^p = (q^2)^{p/2}$
• Si $p$ est impair : $q^p = (q^2)^{(p-1)/2} \times q$

Cette méthode effectue $O(\log p)$ multiplications au lieu de $O(p)$.