Exercice 41 / 100

Récursivité - factorielle

ConsigneCalculez n! avec une fonction récursive

📖 Cours

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) × ... × 10! = 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 pour tout n entier positif ou nul, et sans risque de dépasser la limite de récursion.

Ni l'une ni l'autre ne gère un n négatif : l'itérative renvoie 1 (sa boucle ne tourne pas), la récursive ne rencontre jamais son cas de base et finit en RecursionError.

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.