Programme officiel
| Contenus | Capacités attendues | Commentaires |
|---|---|---|
| Récursivité | Écrire un programme récursif.
Analyser le fonctionnement d’un programme récursif. |
Des exemples relevant de domaines variés sont à privilégier. |
Algorithme itératif
L’exponentiation est une opération mathématique que l’on peut traduire par plusieurs algorithmes. $$a^n=\underbrace{a ×….× a}_{n~fois}\qquad et\ a^0=1$$
def puissance_perso(x:int, n:int) -> int:
res = 1
while not n == 0:
res = res * x
n = n - 1
return res
Le coût temporel est linéaire en fonction de l’exposant n.
Algorithme récursif
Première formulation mathématique récursive: $$ puissance(x,n) = \left{ \begin{array}{ll} 1 & si~ n=0 \ x.puissance(x,n-1) & si~ n>0 \end{array} \right. $$
def puissance_recursif(x: int, n: int) -> int:
if n == 0: # cas limite
return 1
else: # appel récursif
return x*puissance_recursif(x, n-1)
Le coût temporel reste linéaire: la fonction effectue n appels récursifs. Seconde formulation récursive: $$ puissance(x,n) = \left{ \begin{array}{ll} 1 & si~ n=0 \ puissance(xx,n/2) & si~ n>0 ~ et~ n~pair\ x.puissance(xx,(n-1)/2) & si~ n>0 ~ et ~n~ impair \end{array} \right. $$
def puissance_recursif_rapide(x: int, n: int) -> int:
if n == 0: # cas limite
return 1
elif n % 2 == 0: # pair
return puissance_recursif_rapide(x*x, n//2)
else: # impair
return x*puissance_recursif_rapide(x*x, n//2)
L’exposant est divisé par 2 à chaque appel. Si $n=2^p$ alors il y a p appels récursifs. Le coût temporel est logarithmique.