Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

D'une file de personnes au code
factorial(6)🙋 La première personne : 6 × la réponse qu'elle attend
number * factorial(number - 1)➡️ Poser la même question à la suivante, avec un nombre plus petit
if number <= 1: return 1🛑 La dernière personne répond tout de suite : 1
720⬅️ Les réponses remontent la file : 720
Chaque appel attend un appel plus petit jusqu'à ce que le cas de base réponde.
En une phrase

Une 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

  1. if number <= 1: return 1 est le cas de base ; sans lui, les appels ne s'arrêteraient jamais.
  2. return number * factorial(number - 1) appelle la même fonction avec un nombre plus petit.
  3. factorial(6) attend factorial(5), qui attend factorial(4), jusqu'à factorial(1).
  4. 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.factorial est 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

Exécuter le code →
main.py
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))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Oublier le cas de base

La fonction s'appelle sans fin jusqu'à ce que Python lève une RecursionError.

Problème
def factorial(number):
    return number * factorial(number - 1)
Correction
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.

Tous les défis