Exercice 41 / 100

Récursivité - factorielle

Calculez n! avec une fonction récursive

Une fonction récursive est une fonction qui s'appelle elle-même. Très naturel pour décomposer un problème en sous-problèmes plus petits.

Deux ingrédients obligatoires :

1. cas de base   →  arrêt de la récursion (sinon : récursion infinie → RecursionError)
2. cas récursif  →  réduction vers un cas plus petit

Exemple : factorielle

Définition mathématique :

n! = n × (n-1) × (n-2) × ... × 1
0! = 1   (cas de base)

Équivalent : n! = n × (n-1)!

En Python

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

Déroulement pour factorielle(3) :

factorielle(3) = 3 * factorielle(2)
               = 3 * (2 * factorielle(1))
               = 3 * (2 * (1 * factorielle(0)))
               = 3 * (2 * (1 * 1))
               = 6

Chaque appel de factorielle contient l'appel suivant, jusqu'au cas de base qui vaut 1 : c'est lui, et lui seul, qui arrête la descente

Pièges classiques

Oublier le cas de base → RecursionError (limite Python ~1000 appels).

Ne pas réduire le paramètre → même problème.

Pour de grands n, Python plafonne (sys.setrecursionlimit). Préfère une version itérative.

Récursif vs itératif

Version itérative (avec une boucle) :

def factorielle(n):
    r = 1
    for i in range(2, n + 1):
        r *= i
    return r

Même résultat, sans risque de débordement.

La récursion brille quand le problème est naturellement récursif : arbres, structures imbriquées, parcours de graphes, algorithmes de tri (mergesort, quicksort). Pour des calculs simples, l'itératif est souvent plus efficace.

exercise.py