Prépa Code Connexion Inscription

Écrire une fonction puissance(x, n) qui calcule x^n en utilisant l'algorithme d'exponentiation rapide (rapide car en O(log n) au lieu de O(n)).

Le principe est le suivant :

• Si n = 0, renvoyer 1
• Si n est pair : puissance(x, n) = puissance(x, n//2) ** 2
• Si n est impair : puissance(x, n) = x * puissance(x, n-1)