Récursivité et diviser pour régner
Fonctions récursives (cas de base, appels récursifs, pile d'appels), terminaison et correction, coût d'une récursivité naïve (Fibonacci), méthode « diviser pour régner » : recherche dichotomique récursive, tri fusion, exponentiation rapide.
1. Fonctions récursives
Définition
Une fonction est récursive si elle s'appelle elle-même. Elle comporte un ou plusieurs cas de base (résultat direct) et des appels récursifs sur des données « plus petites », qui doivent finir par atteindre un cas de base.
Exemple · Factorielle
def factorielle(n):
if n == 0:
return 1
return n * factorielle(n - 1)$\text{factorielle}(4) = 4 \times 3 \times 2 \times 1 \times 1 = 24$. Chaque appel attend le résultat du suivant : les appels sont empilés dans la pile d'appels.
Attention · Pile d'appels
Sans cas de base (ou si on ne s'en rapproche pas), la récursion ne s'arrête jamais : Python lève RecursionError (environ $1\,000$ appels par défaut).
Propriété · Coût d'une récursivité naïve
fib(n) = fib(n - 1) + fib(n - 2) recalcule les mêmes valeurs : le nombre d'appels croît de façon exponentielle. On l'évite en mémorisant les résultats (mémoïsation) ou par une boucle.
2. Diviser pour régner
Définition
La méthode diviser pour régner : diviser le problème en sous-problèmes plus petits, les résoudre (souvent récursivement), puis combiner les solutions.
Méthode · Tri fusion
def fusionner(a, b):
res, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]:
res.append(a[i]); i = i + 1
else:
res.append(b[j]); j = j + 1
return res + a[i:] + b[j:]
def tri_fusion(t):
if len(t) <= 1:
return t
m = len(t) // 2
return fusionner(tri_fusion(t[:m]), tri_fusion(t[m:]))Coût en $O(n \log n)$, bien meilleur que les tris quadratiques.
Exemple · Exponentiation rapide
$x^n = (x^{n/2})^2$ si $n$ est pair, $x \times x^{n-1}$ sinon : environ $\log_2 n$ multiplications au lieu de $n$.
Activité · Comparer fib naïve et mémoïsée
fib(25) naïve, puis écrire une version qui mémorise les valeurs dans un dictionnaire.S'entraîner
Exercices corrigés
🎓 20 exercices corrigés et un quiz vous attendent dans ce chapitre.
Créez votre compte gratuit pour voir les corrections, faire les quiz et suivre votre progression.
Cas de base
★☆☆Quel est le cas de base de la fonction factorielle ?
Dérouler factorielle
★☆☆Dérouler les appels de factorielle(3).
Somme récursive
★★☆Écrire une fonction récursive somme(n) qui calcule $1 + 2 + \dots + n$.
Puissance récursive
★★☆Écrire puissance(x, n) récursive (naïve).
Longueur d'une chaîne
★★☆Écrire une fonction récursive longueur(s) sans utiliser len (on pourra utiliser s[1:] et tester s == "").
Palindrome
★★★Écrire une fonction récursive palindrome(s).
Erreur de récursion
★★☆Pourquoi def f(n): return f(n - 1) provoque-t-il une erreur ?
Appels de fib
★★☆D'après la figure, combien d'appels pour fib(4) ? Combien de fois fib(1) ?
fib mémoïsée
★★★Écrire une version mémoïsée de fib avec un dictionnaire.
Fusion
★★☆Que renvoie fusionner([1, 4, 7], [2, 3, 9]) ?
Tri fusion à la main
★★☆Dérouler le tri fusion de [5, 2, 4, 1].
Coût du tri fusion
★★☆Combien de niveaux de division pour un tableau de $1\,024$ éléments ?
Comparer les tris
★★☆Pour $10^6$ éléments, comparer approximativement $n^2$ et $n\log_2 n$.
Dichotomie récursive
★★★Écrire une recherche dichotomique récursive dicho(t, x, g, d).
Exponentiation rapide
★★★Écrire puissance_rapide(x, n).
Nombre de multiplications
★★☆Combien de multiplications pour $x^{16}$ avec l'exponentiation rapide ? avec la méthode naïve ?
Terminaison
★★☆Pourquoi le tri fusion se termine-t-il ?
Tours de Hanoï
★★★Combien de déplacements pour résoudre les tours de Hanoï avec $n$ disques ? avec $10$ disques ?
Récursif ou itératif
★☆☆Toute fonction récursive peut-elle s'écrire avec une boucle ?
Vrai ou faux
★★☆a) Une fonction récursive doit avoir un cas de base. b) fib naïve a un coût linéaire. c) Le tri fusion est en $O(n \log n)$.
Vérifier
Avez-vous bien compris ?
Répondez au quiz : la correction s'affiche immédiatement.