Récursivité et diviser pour régner

Récursivité et diviser pour régner

Définition

Une fonction est récursive quand elle s'appelle elle-même. Toute fonction récursive doit comporter :

1. un ou plusieurs cas de base (sans appel récursif),
2. un cas récursif qui se ramène à un sous-problème plus petit,
3. une garantie de terminaison (un paramètre strictement décroissant vers le cas de base).

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

Pile d'exécution

Chaque appel empile une frame (variables locales, point de retour). La récursivité non terminale a un coût mémoire en $O(p)$ où $p$ est la profondeur des appels. Python limite la pile (≈ 1000 appels par défaut, modifiable via sys.setrecursionlimit).

Paradigme « diviser pour régner »

1. Diviser le problème en sous-problèmes indépendants.
2. Régner : résoudre récursivement les sous-problèmes.
3. Combiner les solutions partielles.

Exemples typiques :

Algorithme	Diviser	Combiner	Complexité
Tri fusion	en deux moitiés	fusion triée	$O(n \log n)$
Tri rapide	autour d'un pivot	concaténation	$O(n \log n)$ moyen
Recherche dichotomique	demi-tableau	–	$O(\log n)$
Exponentiation rapide	$a^n = (a^{n/2})^2$	carré	$O(\log n)$

Théorème maître (intuition)

Pour $T(n) = a \cdot T(n/b) + O(n^d)$ :

• si $d > \log_b a$ : $T(n) = O(n^d)$,
• si $d = \log_b a$ : $T(n) = O(n^d \log n)$,
• si $d < \log_b a$ : $T(n) = O(n^{\log_b a})$.

Le tri fusion vérifie $a=2, b=2, d=1$ donc $T(n) = O(n \log n)$.

Exponentiation rapide

def puissance(a, n):
    if n == 0: return 1
    demi = puissance(a, n // 2)
    return demi * demi * (a if n % 2 else 1)