1. Calcul de la factorielle

La factorielle d’un entier naturel n (notée n!) est l’exemple canonique de la récursion directe : 0! = 1, et pour tout n > 0, n! = n * (n – 1)! :

def factorielle(n: int) -> int:
    if n == 0 or n == 1:
        return 1
    return n * factorielle(n - 1)

print(f"5! = {factorielle(5)}")  # 120

2. La suite de Fibonacci et les limites de la récursion naïve

L’implémentation récursive naïve de Fibonacci (F(n) = F(n-1) + F(n-2)) produit un arbre d’appels binaire entraînant une complexité exponentielle en O(2^n). Pour éviter les recalculs redondants de mêmes sous-branches, nous mettons en œuvre la mémoïsation (programmation dynamique) :

from functools import lru_cache

@lru_cache(maxsize=None)
def fibonacci_optimise(n: int) -> int:
    if n < 2:
        return n
    return fibonacci_optimise(n - 1) + fibonacci_optimise(n - 2)

print(f"Fibonacci(50) = {fibonacci_optimise(50)}")

3. La stratégie Diviser-pour-régner : le tri fusion (Merge Sort)

Le paradigme "Divide and Conquer" consiste à scinder récursivement une liste non triée en deux moitiés, à trier ces deux sous-listes, puis à les fusionner de manière ordonnée. Cet algorithme garantit un temps d'exécution optimal en O(n log n), surclassant nettement les tris naïfs en O(n²).

Synthèse pédagogique : La puissance de la récursion réside dans sa capacité à diviser des problèmes d'apparence insolubles en sous-structures indépendantes et immédiatement maîtrisables.

PreviousNext