Récursivité et diviser pour régner

En clair. Cas de base, récurrence

Ce qu'on te demande au bac (Spé NSI) : maîtriser le vocabulaire de « Récursivité et diviser pour régner », savoir refaire les raisonnements du cours et les réutiliser sur un sujet ou un document nouveau.

Conseil de révision. Lis d'abord cet encadré, puis fais le quiz : si tu bloques, reprends la partie du cours correspondante.

Définition

Une fonction est récursive lorsqu'elle s'appelle elle-même sur une donnée plus petite, jusqu'à atteindre un cas de base qui arrête la descente. Toute fonction récursive correcte comporte deux éléments indissociables :

1. un ou plusieurs cas de base (terminaison) ;
2. un cas récursif qui se rapproche strictement du cas de base.

def factorielle(n):
    if n <= 1:          # cas de base
        return 1
    return n * factorielle(n - 1)   # cas récursif

Pile d'appels et coût

Chaque appel empile un contexte (paramètres, adresse de retour) dans la pile d'exécution. La profondeur maximale est limitée : en Python, sys.setrecursionlimit vaut 1000 par défaut, et un dépassement lève RecursionError.

Coût de factorielle(n) : $n$ appels, donc complexité temporelle $O(n)$ et spatiale $O(n)$ (à cause de la pile), là où une boucle serait en $O(1)$ d'espace.

Diviser pour régner

La stratégie diviser pour régner décompose un problème de taille $n$ en sous-problèmes indépendants de taille $n/2$, les résout récursivement, puis combine les résultats.

Recherche dichotomique dans un tableau trié :

def dicho(t, v, g, d):
    if g > d:
        return -1
    m = (g + d) // 2
    if t[m] == v:
        return m
    if t[m] < v:
        return dicho(t, v, m + 1, d)
    return dicho(t, v, g, m - 1)

À chaque étape la zone de recherche est divisée par 2 : complexité $O(\log_2 n)$. Pour $n = 1\,000\,000$, environ 20 comparaisons suffisent.

Tri fusion :

def tri_fusion(t):
    if len(t) <= 1:
        return t
    m = len(t) // 2
    return fusion(tri_fusion(t[:m]), tri_fusion(t[m:]))

Complexité $O(n\log n)$ dans tous les cas, contre $O(n^2)$ pour le tri par insertion dans le pire cas.

Piège : la récursivité multiple

def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

Cette version recalcule les mêmes valeurs : nombre d'appels exponentiel, $O(\varphi^n)$. fibo(40) demande déjà plus de 300 millions d'appels. Remède : la mémoïsation, qui mémorise les résultats déjà calculés et ramène le coût à $O(n)$.

def fibo(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo)
    return memo[n]

Méthode : écrire une fonction récursive

1. Identifier le cas le plus petit et sa valeur de retour.
2. Exprimer le résultat pour $n$ à l'aide du résultat pour une taille strictement inférieure.
3. Vérifier que chaque appel réduit bien la taille (sinon boucle infinie).
4. Tester sur le cas de base, puis sur deux ou trois petites valeurs à la main.

Erreurs fréquentes

• Oublier le cas de base ou ne jamais l'atteindre → RecursionError.
• Placer le return seulement dans le cas récursif : la fonction renvoie None.
• Croire que récursif = plus efficace : c'est souvent plus lisible, rarement plus rapide.
• Utiliser des tranches t[:m] sans compter leur coût : chaque copie est en $O(n)$.

Quiz corrigé

1. Quels sont les deux ingrédients obligatoires d'une fonction récursive ? → Un cas de base qui termine, et un cas récursif qui se rapproche de ce cas de base.

2. Quelle est la complexité de la recherche dichotomique et pourquoi ? → $O(\log_2 n)$ : l'intervalle de recherche est divisé par deux à chaque appel.

3. Pourquoi la version naïve de Fibonacci est-elle inutilisable pour n = 50 ? → Les sous-appels sont recalculés un nombre exponentiel de fois ; il faut mémoïser pour revenir à $O(n)$.