Factorial

Q: Quelle est la complexité temporelle du calcul d’une factorielle ?

La boucle et la récursion effectuent toutes deux une multiplication pour chaque nombre jusqu’à n , donc leur complexité temporelle est de O(n) . La boucle nécessite un espace supplémentaire de O(1) . La récursion conserve un cadre de pile par appel jusqu’au retour du cas de base, elle utilise donc un espace de O(n) .

Q: Pourquoi 0! est-il égal à 1 ?

0! est le produit d’aucun nombre, et un produit sans facteur vaut 1 , tout comme une somme sans terme vaut 0 . Cela permet également de conserver la règle n! = n × (n-1)! à n = 1 : 1! = 1 × 0! = 1 . Le dénombrement confirme ce résultat : il existe exactement une façon d’organiser zéro élément.

Q: La récursion ou une boucle est-elle préférable pour calculer une factorielle ?

Elles effectuent les mêmes multiplications et renvoient le même résultat. La version récursive se lit comme la définition mathématique, c’est pourquoi c’est un exercice classique pour s’initier à la récursion. La boucle utilise une mémoire constante et ne peut pas provoquer de débordement de la pile d’appels, c’est donc le meilleur choix dans du code réel.

Q: Quel est la plus grande factorielle qui tient dans un entier ?

12! = 479001600 est la plus grande factorielle qui tient dans un entier signé de 32 bits. 20! = 2432902008176640000 est la plus grande pour un entier signé de 64 bits. Au-delà, il faut des nombres de taille illimitée, comme int de Python, BigInteger de Java ou BigInt de JavaScript.

DébutantMaths et simulation Récursivité

+10

La factorielle d’un nombre entier n, notée n!, est le produit de tous les nombres entiers de 1 à n. Par exemple, 4! = 1 × 2 × 3 × 4 = 24. Par définition, 0! = 1. Votre fonction reçoit n et renvoie n!.

Fonction

factorial(n: integer) → integer

ninteger: le nombre entier dont tu calcules la factorielle
Renvoieinteger: le produit de tous les entiers de 1 à n, qui vaut 1 lorsque n est égal à 0

Contraintes

0 ≤ n ≤ 12
La réponse tient dans un entier signé de 32 bits : le plus grand est 12! = 479001600.

Exemples

Entrée: n = 5
Sortie: 120
Explication: Multiplie 1 × 2 × 3 × 4 × 5. Le produit cumulé passe par 1, 2, 6, 24 et se termine à 120.

Entrée: n = 0
Sortie: 1
Explication: Il n’y a rien à multiplier, et un produit sans facteurs vaut 1. C’est pourquoi 0! = 1.

+11 tests cachés à la soumission

Pour aller plus loin

100! comporte 158 chiffres. Peux-tu compter le nombre de zéros à la fin sans le calculer ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La factorielle a deux descriptions équivalentes, et chacune se traduit en code. Sous forme de produit, n! = 1 × 2 × ... × n, c’est une boucle. Sous forme de définition récursive, 0! = 1 et n! = n × (n-1)!, c’est une fonction qui s’appelle elle-même. Les deux effectuent environ n multiplications. Il vaut mieux terminer par la boucle, car elle ne nécessite pas de pile d’appels.

La récursion à partir de la définition

Intuition

La factorielle se définit à partir d’une factorielle plus petite : n! = n × (n-1)!. Si tu sais déjà que 4! = 24, alors 5! = 5 × 24 = 120. Une fonction récursive exprime cette phrase sous forme de code. Pour obtenir factorial(n), elle demande factorial(n-1) et multiplie le résultat par n.

Les appels ont besoin d’un point d’arrêt, le cas de base : factorial(0) renvoie 1 sans rien appeler. Chaque appel diminue n de un, donc à partir de 5, les appels sont 5, 4, 3, 2, 1, 0. Puis les résultats remontent la chaîne : 1, 1, 2, 6, 24, 120.

Il y a n + 1 appels et n multiplications, donc le temps d’exécution est de O(n). Chaque appel attend sur la pile que l’appel en dessous renvoie son résultat, donc la pile contient n + 1 cadres, ce qui représente un espace de O(n). Avec n ≤ 12, c’est minime, mais le même schéma appliqué à une grande entrée provoque un débordement de pile.

Algorithme

Si n vaut 0, retourne 1. C’est le cas de base.
Sinon, appelle la fonction sur n-1.
Multiplie ce résultat par n et retourne-le.

def factorial(n):
    if n == 0:
        return 1  # base case: 0! = 1
    return n * factorial(n - 1)

Multiplier dans une boucle

Intuition

Déroulez la récursion et vous obtenez un produit cumulatif. Commencez par result = 1 et multipliez-le par 2, puis par 3, et ainsi de suite jusqu’à n. Pour n = 5, le résultat est 1, 2, 6, 24, 120.

Commencer à 1 couvre aussi les plus petites entrées. Pour n = 0 et n = 1, la boucle de 2 à n s’exécute zéro fois, et la fonction renvoie la valeur de départ 1, qui est la bonne réponse dans les deux cas.

La boucle effectue n-1 multiplications, prend un temps de O(n) et conserve un seul nombre, soit un espace de O(1). Il n’y a pas de pile d’appels susceptible de déborder, ce qui explique pourquoi les intervieweurs s’attendent à cette version une fois que vous avez présenté la version récursive.

Algorithme

Définis result = 1.
Parcours k de 2 à n, les deux inclus.
Multiplie result par k à chaque étape.
Retourne result.

def factorial(n):
    result = 1
    for k in range(2, n + 1):
        result *= k
    return result

Pièges et cas limites

Le code du factoriel est court, les bogues se cachent donc dans les cas limites.

Commencer le produit à 0. Chaque multiplication le maintient à 0. La valeur initiale d’un produit est 1.
Arrêter la récursion uniquement lorsque n == 1. Appelée avec 0, cette fonction n’atteint jamais son cas de base : elle continue avec -1, -2, et ainsi de suite, jusqu’au débordement de pile. Faites de n == 0 le cas de base.
Parcourir la boucle avec k < n au lieu de k ≤ n. Le dernier facteur est alors omis et le résultat est (n-1)!, donc 5 donne 24 au lieu de 120.
Ignorer le dépassement de capacité. 13! = 6227020800 ne tient pas dans un entier signé de 32 bits. En Java et en C#, le produit revient silencieusement à une valeur erronée ; en C, le dépassement d’un entier signé entraîne un comportement indéfini, et une compilation Rust en mode débogage provoque une panique. Un entier de 64 bits peut contenir jusqu’à 20! ; au-delà, il faut utiliser des entiers de précision arbitraire.
En Swift, écrire for k in 2...n. Une plage fermée dont la borne de fin est inférieure à la borne de début provoque un plantage à l’exécution lorsque n vaut 0 ou 1.

Questions fréquentes4

Quelle est la complexité temporelle du calcul d’une factorielle ?

La boucle et la récursion effectuent toutes deux une multiplication pour chaque nombre jusqu’à n, donc leur complexité temporelle est de O(n). La boucle nécessite un espace supplémentaire de O(1). La récursion conserve un cadre de pile par appel jusqu’au retour du cas de base, elle utilise donc un espace de O(n).

Pourquoi 0! est-il égal à 1 ?

0! est le produit d’aucun nombre, et un produit sans facteur vaut 1, tout comme une somme sans terme vaut 0. Cela permet également de conserver la règle n! = n × (n-1)! à n = 1 : 1! = 1 × 0! = 1. Le dénombrement confirme ce résultat : il existe exactement une façon d’organiser zéro élément.

La récursion ou une boucle est-elle préférable pour calculer une factorielle ?

Elles effectuent les mêmes multiplications et renvoient le même résultat. La version récursive se lit comme la définition mathématique, c’est pourquoi c’est un exercice classique pour s’initier à la récursion. La boucle utilise une mémoire constante et ne peut pas provoquer de débordement de la pile d’appels, c’est donc le meilleur choix dans du code réel.

Quel est la plus grande factorielle qui tient dans un entier ?

12! = 479001600 est la plus grande factorielle qui tient dans un entier signé de 32 bits. 20! = 2432902008176640000 est la plus grande pour un entier signé de 64 bits. Au-delà, il faut des nombres de taille illimitée, comme int de Python, BigInteger de Java ou BigInt de JavaScript.

Python

def factorial(n):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

n = 5

Attendu