Calculer une factorielle par récursivité en Python
Dans cette leçon, vous allez écrire une fonction récursive pour calculer une factorielle et comprendre le rôle du cas de base.
Introduction
Le problème
Certains problèmes se décrivent naturellement par une version plus petite d'eux-mêmes : un dossier contient des dossiers, un arbre généalogique contient des arbres plus petits, n! vaut n fois (n - 1)!. La récursion permet d'écrire un code qui suit directement de telles définitions.
Imaginez-le ainsi
La récursivité ressemble à une file de personnes qui se passent une question. Pour obtenir 6!, la première personne demande 5! à sa voisine et attend. Celle-ci demande 4!, et ainsi de suite, jusqu'à la personne à qui l'on demande 1! : elle peut répondre tout de suite. Les réponses remontent alors la file, et chacun multiplie par son propre nombre.
factorial(6)🙋 La première personne : 6 × la réponse qu'elle attendnumber * factorial(number - 1)➡️ Poser la même question à la suivante, avec un nombre plus petitif number <= 1: return 1🛑 La dernière personne répond tout de suite : 1720⬅️ Les réponses remontent la file : 720Une fonction récursive s'appelle elle-même avec une entrée plus petite jusqu'à un cas de base auquel elle répond directement ; ici factorial(n) = n × factorial(n - 1) et factorial(1) = 1.
Points clés
if number <= 1: return 1est le cas de base ; sans lui, les appels ne s'arrêteraient jamais.return number * factorial(number - 1)appelle la même fonction avec un nombre plus petit.factorial(6)attendfactorial(5), qui attendfactorial(4), jusqu'àfactorial(1).raise ValueError(...)refuse les nombres négatifs, qui n'atteindraient sinon jamais le cas de base.
Quand l’utiliser ?
- Les problèmes définis par des versions plus petites : arbres, dossiers, données imbriquées.
- Les algorithmes « diviser pour régner » comme le tri fusion.
- Apprendre comment fonctionne la pile d'appels.
Quand s'en passer
- La simple répétition comme la factorielle dans du vrai code : une boucle ou
math.factorialest plus rapide et sans limite de profondeur. - Les entrées très profondes : Python s'arrête vers 1 000 appels imbriqués avec une RecursionError.
Voir comment ça marche
Appuyez sur Étape pour suivre chaque appel. Les nouveaux appels vont sur la pile d'appels, et chacun renvoie sa valeur à l'appel qui l'a lancé.
Code d’exemple
def factorial(number):
if number < 0:
raise ValueError("Factorial is undefined for negative numbers")
if number <= 1:
return 1
return number * factorial(number - 1)
print(factorial(6))
Résultat de l’exécution
720
Explication du code
Quand number vaut 0 ou 1, la fonction renvoie aussitôt 1. C'est le cas de base qui empêche la récursivité de tourner indéfiniment. Pour les autres valeurs, la fonction renvoie number multiplié par factorial(number - 1). Chaque appel récursif est empilé sur la pile d'appels (call stack), la profondeur de récursion est donc O(n).
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Oublier le cas de base
La fonction s'appelle sans fin jusqu'à ce que Python lève une RecursionError.
def factorial(number):
return number * factorial(number - 1)
def factorial(number):
if number <= 1:
return 1
return number * factorial(number - 1)
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Factorielle Multiplier tous les entiers positifs jusqu'à n. Facile
- Recursive Power Compute a power recursively by halving the exponent. Moyen