Calcul du factoriel en C
Calculez n!, vérifiez les risques de dépassement de capacité selon le type C choisi, comparez une approche itérative et récursive, puis visualisez la croissance explosive du factoriel avec un graphique interactif.
Conseil pratique : au delà de 20!, les entiers 64 bits débordent en C. Pour des valeurs plus grandes, il faut passer par des bibliothèques de grands entiers ou une logique de multiplication sur chaînes.
Guide expert : comprendre le calcul du factoriel en C
Le factoriel est une opération fondamentale en mathématiques discrètes, en algorithmique, en probabilités et dans de nombreux programmes écrits en C. La notation est simple : pour un entier naturel n, le factoriel n! est le produit de tous les entiers positifs de 1 à n. Ainsi, 5! = 5 × 4 × 3 × 2 × 1 = 120. Par convention, 0! vaut 1. Cette définition paraît élémentaire, mais sa mise en oeuvre dans un langage comme le C ouvre immédiatement plusieurs questions importantes : quel type de données utiliser, comment éviter les débordements, quelle méthode choisir entre itératif et récursif, et comment gérer les valeurs très grandes ?
Quand on parle de calcul du factoriel en C, il ne suffit pas de savoir écrire une boucle. Il faut aussi connaître les limites numériques de la machine. Le C est rapide, proche du matériel, et laisse une grande liberté au développeur. En contrepartie, il n’intègre pas nativement de type entier arbitrairement grand. Cela signifie qu’un code correct sur le plan logique peut devenir faux dès que la valeur calculée dépasse la capacité du type utilisé. Pour un développeur, maîtriser le factoriel est donc un excellent exercice pour apprendre la robustesse numérique.
Définition mathématique et relation avec la fonction gamma
Le factoriel est défini pour les entiers naturels, mais en analyse mathématique il se prolonge à travers la fonction gamma. Cette relation est donnée par Γ(n + 1) = n! pour n entier naturel. Si vous voulez une source de référence sur ce point, la Digital Library of Mathematical Functions du NIST fournit une base théorique très solide. Pour un programmeur C, cette relation devient intéressante lorsque l’on travaille avec des approximations flottantes, des modèles probabilistes ou des extensions vers des valeurs non entières.
Pourquoi le factoriel grandit si vite
La difficulté principale vient de la croissance extrêmement rapide de n!. Quelques exemples suffisent à s’en rendre compte : 10! vaut 3 628 800, 20! vaut déjà 2 432 902 008 176 640 000, et 50! dépasse 3,04 × 10^64. Cette accélération signifie que les types entiers classiques en C deviennent insuffisants bien plus tôt que beaucoup de débutants ne l’imaginent. En pratique, un programme qui calcule correctement 12! avec un type 32 bits échouera à 13!, et un programme en 64 bits échouera à partir de 21!.
| Type numérique simulé | Valeur maximale typique | Plus grand factoriel exact | Premier factoriel en dépassement |
|---|---|---|---|
| int 32 bits signé | 2 147 483 647 | 12! = 479 001 600 | 13! = 6 227 020 800 |
| unsigned int 32 bits | 4 294 967 295 | 12! = 479 001 600 | 13! = 6 227 020 800 |
| long long 64 bits signé | 9 223 372 036 854 775 807 | 20! = 2 432 902 008 176 640 000 | 21! = 51 090 942 171 709 440 000 |
| unsigned long long 64 bits | 18 446 744 073 709 551 615 | 20! = 2 432 902 008 176 640 000 | 21! = 51 090 942 171 709 440 000 |
| double IEEE 754 | Environ 1,79 × 10^308 | 170! reste fini en virgule flottante | 171! tend vers l’infini |
Approche itérative : la meilleure base en C
La méthode la plus simple et la plus robuste pour calculer un factoriel en C consiste à utiliser une boucle for. On initialise une variable résultat à 1, puis on multiplie successivement par chaque entier de 2 à n. Cette approche a plusieurs avantages : elle est lisible, performante, prévisible, et n’ajoute pas de profondeur de pile. Pour les petites et moyennes valeurs, c’est presque toujours la meilleure solution. Si votre objectif est la production, la pédagogie ou l’optimisation, commencez par l’itératif.
En complexité, le calcul d’un factoriel simple par boucle est en O(n) multiplications. La mémoire supplémentaire utilisée est O(1), puisque le programme n’a besoin que d’un petit nombre de variables. C’est un point fort par rapport à la récursivité, qui utilise la pile d’appels. Dans un contexte embarqué ou système, cette différence compte énormément.
Approche récursive : élégante mais moins sûre
La version récursive suit directement la définition mathématique : n! = n × (n – 1)!, avec le cas de base 0! = 1 ou 1! = 1. C’est souvent la première solution présentée dans les cours d’algorithmique, car elle est compacte et intuitive. Cependant, en C, la récursivité a un coût. Chaque appel empile un nouveau cadre de fonction, ce qui consomme de la mémoire et augmente le risque d’erreur si n devient élevé. Même si le débordement numérique se produit bien avant sur les types entiers classiques, la récursivité reste moins appropriée pour un code robuste.
En résumé, utilisez la récursion pour comprendre le concept ou pour illustrer un cours, mais préférez l’itération dans la majorité des programmes réels. Si vous souhaitez revoir les bases du langage C dans un cadre académique, le cours CS50 de Harvard fournit une excellente introduction au raisonnement bas niveau, aux types et aux fonctions. Pour la notion de récursion plus spécifiquement, des notes universitaires comme celles de l’University of Tennessee sont aussi très utiles.
Validation des entrées : le point que beaucoup oublient
Un calcul de factoriel en C doit toujours vérifier les entrées. Le factoriel standard n’est défini que pour les entiers naturels. Si l’utilisateur saisit une valeur négative, un nombre trop grand pour le type choisi, ou une valeur non entière, votre programme doit réagir clairement. Dans une interface console C classique, cela signifie vérifier le retour de scanf, contrôler que n est supérieur ou égal à 0, puis afficher un message d’erreur compréhensible si la saisie est invalide.
- Refuser les valeurs négatives.
- Refuser les valeurs non entières si l’algorithme attend un entier.
- Signaler le dépassement de capacité avant la multiplication finale si possible.
- Documenter la limite pratique liée au type utilisé.
Détection du dépassement de capacité
Le dépassement de capacité, ou overflow, est le vrai enjeu quand on code un factoriel en C. Pour le prévenir, il ne suffit pas d’espérer que l’utilisateur restera dans des bornes raisonnables. Une bonne pratique consiste à tester, avant chaque multiplication, si resultat > MAX / i. Si cette condition est vraie, la prochaine multiplication dépasserait la capacité du type. On peut alors arrêter proprement le calcul et avertir l’utilisateur. Cette stratégie fonctionne très bien pour les types entiers classiques.
Pour les flottants comme double, le problème est différent. Les grandes valeurs finissent en infini selon la norme IEEE 754. On peut tester la finitude du résultat avec des fonctions comme isfinite(), mais il faut aussi rappeler qu’un double n’est pas conçu pour représenter exactement de très grands entiers. Il peut rester fini tout en perdant de la précision sur les derniers chiffres.
| n | Valeur de n! | Nombre de chiffres décimaux | Observation pratique |
|---|---|---|---|
| 10 | 3 628 800 | 7 | Facile à manipuler dans tous les types standards |
| 20 | 2 432 902 008 176 640 000 | 19 | Dernière valeur exacte en 64 bits entier |
| 50 | ≈ 3,0414 × 10^64 | 65 | Impossible en 64 bits entier, nécessite grand entier ou approximation |
| 100 | ≈ 9,3326 × 10^157 | 158 | Encore fini en double mais sans exactitude entière complète |
| 170 | ≈ 7,2574 × 10^306 | 307 | Limite haute pratique avant infini en double |
Exemple logique d’algorithme itératif en C
- Lire un entier n.
- Vérifier que n est supérieur ou égal à 0.
- Initialiser
resultat = 1. - Pour chaque i de 2 à n, vérifier si la multiplication provoquerait un overflow.
- Multiplier si c’est sûr.
- Afficher le résultat.
Cette séquence simple couvre déjà une grande partie des besoins réels. Si vous travaillez sur un projet de calcul combinatoire, ce même schéma servira aussi pour les permutations, les arrangements et certaines combinaisons, même si dans ces cas il est souvent préférable d’éviter de calculer les factoriels complets pour des raisons de stabilité et de performance.
Applications concrètes du factoriel
Le factoriel apparaît partout en informatique scientifique. En combinatoire, il permet de calculer le nombre de permutations de n objets distincts. En probabilités, on le retrouve dans la loi de Poisson, les coefficients binomiaux et certaines fonctions génératrices. En algorithmique, il sert souvent à décrire la complexité de certains problèmes d’énumération. Dans des systèmes C orientés calcul, traitement embarqué ou simulation, savoir manipuler n! proprement évite des erreurs graves de résultat.
- Calcul de permutations et de combinaisons.
- Évaluation de séries en analyse numérique.
- Étude de complexité de recherches exhaustives.
- Outils pédagogiques pour apprendre boucles, fonctions et récursion en C.
Que faire si vous avez besoin de valeurs énormes
Si votre programme doit calculer 100!, 500! ou davantage avec exactitude, les types standards du C ne suffisent plus. Il faut alors utiliser une bibliothèque de grands entiers, ou implémenter une représentation maison sous forme de tableau de chiffres ou de blocs numériques. L’idée est de simuler la multiplication manuellement, en stockant le résultat morceau par morceau. Cela augmente la complexité du code, mais c’est la seule façon d’obtenir une exactitude totale au delà des limites machine.
Une autre stratégie consiste à travailler non pas sur la valeur exacte de n!, mais sur son logarithme, souvent log(n!) ou log10(n!). C’est extrêmement utile lorsque vous avez seulement besoin de comparer des ordres de grandeur, de compter le nombre de chiffres, ou d’évaluer des expressions probabilistes sans déborder. Le graphique interactif du calculateur ci dessus utilise justement cette idée pour rester lisible même quand le factoriel devient gigantesque.
Bonnes pratiques pour un code C fiable
- Choisir un type adapté et documenter clairement sa limite.
- Tester l’overflow avant chaque multiplication.
- Préférer l’itération à la récursion pour la robustesse générale.
- Valider la saisie utilisateur sans supposer qu’elle est correcte.
- Utiliser des tests unitaires sur 0!, 1!, 5!, 10!, 12!, 20! et les premiers cas de dépassement.
Conclusion
Le calcul du factoriel en C est un sujet apparemment simple, mais il constitue un excellent révélateur du niveau de rigueur d’un développeur. Savoir écrire n! avec une boucle n’est que la première étape. Le vrai savoir faire consiste à comprendre la croissance de la fonction, les limites des types, la différence entre exactitude et approximation, et les méthodes pour prévenir les erreurs numériques. Si vous retenez une seule règle, retenez celle ci : en C, la bonne formule ne suffit pas, il faut aussi la bonne stratégie de représentation.