Les exercices python à connaître

Il est possible de calculer la puissance \(x^n\) par récursivité en utilisant la définition : \[ x^n = \left\{ \begin{array}{2} 1 & \text{si} n=0, \\ x \times x^{n-1} &\text{sinon}.\\ \end{array} \right. \]

						def puissance_rec(x: float, n: int) -> float:
							if n == 0:
								return 1
							else:
								return x*puissance_rec(x, n-1)
					

Pour optimiser la vitesse de calcul, on remarque que : \[ x^n = \left\{ \begin{array}{2} 1 & \text{si} n=0, \\ (x \times x)^\frac{n}{2} &\text{si n est pair}.\\ x \times (x \times x)^\frac{n-1}{2} &\text{si n est impair}.\\ \end{array} \right. \] Cette définition permet de construire un algorithme de calcul en utilisant la méthode "diviser pour régner" :

• Diviser : Diviser n
  • si n est pair et non nul on divise n par 2
  • si n est impair on divise n-1 par 2
• Combiner :
  • si n est pair et non nul \( x^n = (x \times x)^\frac{n}{2} \)
  • si n est impair \(x^n = x \times (x \times x)^\frac{n-1}{2} \)
• Régner : si n vaut 0, \( x^n = 1 \)

Écrire une fonction récursive puissance_rapide qui prend en paramètres deux entiers x et n, qui calcule \(x^n\) en utilisant cette méthode.