Calcul de factorielle en C
Calculez instantanément n!, comparez les méthodes itérative et récursive, visualisez la croissance explosive des factorielles et identifiez les limites des types de données en langage C.
Calculatrice factorielle interactive
Choisissez une valeur de n, une méthode et un type de données, puis cliquez sur Calculer la factorielle.
Guide expert du calcul de factorielle en C
Le calcul de factorielle en C est un exercice fondamental en algorithmique, mais aussi un excellent révélateur des limites des types de données, des coûts liés à la récursivité et des choix de conception dans un programme performant. La factorielle d’un entier naturel n, notée n!, correspond au produit de tous les entiers de 1 à n. Ainsi, 5! = 5 × 4 × 3 × 2 × 1 = 120. Par convention, 0! = 1. Cette fonction apparaît dans les permutations, les combinaisons, les probabilités, les séries mathématiques, les méthodes numériques et certaines analyses de complexité.
En langage C, calculer une factorielle semble simple au premier regard. Pourtant, plusieurs questions importantes surgissent immédiatement : quel type utiliser ? La valeur tient-elle encore dans un int ou faut-il un long long ? La version récursive est-elle préférable à la version itérative ? Comment éviter un dépassement de capacité ? Peut-on afficher correctement des résultats très grands ? Et si la valeur dépasse la représentation entière native, faut-il passer à une bibliothèque d’entiers multiprécision ?
Définition mathématique de la factorielle
La définition classique est la suivante :
- 0! = 1
- n! = n × (n – 1)! pour tout n > 0
Cette définition récursive explique pourquoi la factorielle est souvent utilisée pour introduire la récursion en programmation. Cependant, en environnement de production, cette élégance théorique n’est pas toujours la plus pratique. En C, la boucle itérative est généralement plus simple à contrôler, consomme moins de pile et facilite la détection d’overflow avant la multiplication.
Pourquoi la factorielle croît-elle si vite ?
La croissance de n! est extrêmement rapide. Même pour des valeurs modestes de n, les résultats deviennent énormes. Par exemple, 10! vaut 3 628 800, ce qui reste facile à stocker dans un entier 32 bits signé. En revanche, 13! vaut déjà 6 227 020 800, ce qui dépasse la valeur maximale d’un entier signé 32 bits standard. À 21!, un entier signé 64 bits est généralement dépassé. Cette réalité rend le sujet très important pour tout développeur C qui veut écrire du code robuste.
| n | Valeur de n! | Ordre de grandeur | Observation pratique en C |
|---|---|---|---|
| 5 | 120 | 10² | Sans difficulté dans tous les types entiers usuels |
| 10 | 3 628 800 | 10⁶ | Stockage facile en int |
| 12 | 479 001 600 | 10⁸ | Encore compatible avec un int signé 32 bits |
| 13 | 6 227 020 800 | 10⁹ | Dépasse généralement int signé 32 bits |
| 20 | 2 432 902 008 176 640 000 | 10¹⁸ | Encore compatible avec signed long long 64 bits sur la plupart des plateformes modernes |
| 21 | 51 090 942 171 709 440 000 | 10¹⁹ | Dépasse généralement signed long long 64 bits |
Méthode itérative en C
La méthode itérative est la plus directe et la plus utilisée. Elle consiste à initialiser un accumulateur à 1, puis à multiplier successivement par chaque entier de 2 à n. Son intérêt principal est la simplicité d’exécution et la maîtrise des ressources mémoire. Il n’y a pas d’empilement d’appels, et il est plus facile d’ajouter une vérification avant chaque multiplication.
Cette approche est souvent préférée dans les cours d’initiation au C avancé, dans les exercices de programmation système et dans les environnements où la lisibilité opérationnelle importe plus que l’élégance mathématique. En pratique, si vous avez besoin d’un calcul sûr pour des valeurs modestes, l’itératif est presque toujours le meilleur premier choix.
Méthode récursive en C
La version récursive suit la définition mathématique naturelle de la factorielle. Elle est compacte et pédagogique, surtout pour illustrer l’idée qu’une fonction peut s’appeler elle-même jusqu’à atteindre un cas de base. Néanmoins, chaque appel ajoute un niveau à la pile d’exécution. Pour de petites valeurs de n, cela reste sans conséquence. Pour des profondeurs plus élevées, la récursion devient moins attractive qu’une simple boucle.
En C, l’optimisation des appels récursifs n’est pas garantie de manière universelle dans ce cas. Même si certaines chaînes d’outils peuvent optimiser certaines formes de récursion terminale, la factorielle classique telle qu’on l’écrit ci-dessus n’est pas une récursion terminale pure. Cela signifie qu’après l’appel récursif, il reste encore une multiplication à effectuer.
Comparaison itératif vs récursif
| Critère | Version itérative | Version récursive |
|---|---|---|
| Lisibilité mathématique | Bonne | Excellente |
| Performance générale | Très bonne | Souvent moins bonne à cause des appels de fonction |
| Consommation de pile | Très faible | Proportionnelle à n |
| Facilité de détection d’overflow | Élevée | Moyenne |
| Intérêt pédagogique | Excellent | Excellent |
| Usage en production | Le plus courant | Réservé à des cas simples ou éducatifs |
Limites des types de données en C
Le point critique du calcul de factorielle en C est la capacité des types numériques. Le standard C impose des tailles minimales, mais la taille exacte de int ou long dépend de la plateforme et du compilateur. Dans la pratique moderne, on rencontre très souvent :
- int signé 32 bits, maximum 2 147 483 647
- long long signé 64 bits, maximum 9 223 372 036 854 775 807
- double sur base IEEE 754, avec environ 15 à 17 chiffres décimaux significatifs
Conséquence directe : 12! tient généralement dans un int signé 32 bits, mais 13! ne tient plus. Pour un long long signé 64 bits, 20! est encore représentable, mais 21! dépasse typiquement la limite. Avec un double, on peut représenter des nombres bien plus grands en valeur absolue, mais pas avec une précision entière exacte au-delà d’un certain seuil. Cela veut dire qu’un double peut afficher une approximation de grandes factorielles, mais pas forcément chaque chiffre exact.
Détection d’overflow
Une bonne implémentation ne se contente pas de calculer. Elle doit aussi vérifier si le résultat reste valide. En C, une multiplication qui dépasse la capacité du type conduit à un comportement problématique ou à un résultat faux selon le contexte. L’approche classique consiste à tester avant la multiplication :
- Calculer la valeur maximale du type ciblé.
- Avant de faire resultat *= i, vérifier si resultat > max / i.
- Si oui, signaler un overflow avant qu’il ne se produise.
Cette stratégie est très importante si vous développez des outils de calcul, des programmes académiques fiables, des utilitaires embarqués ou des démonstrateurs pédagogiques où les dépassements silencieux doivent être évités.
Pourquoi utiliser parfois double plutôt qu’un entier
Si votre but n’est pas l’exactitude chiffre par chiffre mais plutôt l’ordre de grandeur, l’étude asymptotique ou le tracé d’une courbe, le type double devient intéressant. Il peut représenter des valeurs bien plus grandes qu’un entier 64 bits, même si la précision devient approximative. En analyse numérique, en statistiques ou pour afficher des résultats en notation scientifique, ce compromis peut être acceptable.
Pour des estimations de très grandes factorielles, on utilise souvent lgamma ou des approximations de Stirling plutôt qu’un produit direct. Cette approche est utile lorsque n est trop grand pour un calcul exact natif. Une approximation très connue est :
n! ≈ sqrt(2πn) × (n / e)^n
Cette formule donne d’excellentes estimations quand n devient grand. Elle n’est pas destinée à remplacer un calcul exact pour de petites valeurs, mais elle est très utile pour comprendre la vitesse de croissance de la fonction factorielle.
Cas d’usage concrets de la factorielle
- Calcul du nombre de permutations de n objets distincts.
- Calcul des combinaisons via n! / (k! × (n – k)!).
- Développement en série de fonctions mathématiques.
- Problèmes de probabilité discrète et de dénombrement.
- Analyse de complexité dans certains algorithmes exhaustifs.
- Exercices pédagogiques sur la récursion et les boucles en C.
Bonnes pratiques pour un programme C fiable
- Validez l’entrée utilisateur et refusez les nombres négatifs si vous travaillez sur les entiers naturels.
- Choisissez un type cohérent avec votre domaine de calcul.
- Ajoutez une détection d’overflow avant chaque multiplication.
- Préférez l’itératif si vous visez la robustesse et la performance.
- Utilisez la récursion surtout pour l’apprentissage ou quand la profondeur reste faible.
- Pour des valeurs immenses, passez à une bibliothèque multiprécision.
- Si l’objectif est analytique, utilisez des logarithmes ou l’approximation de Stirling.
Statistiques utiles à connaître
Quelques seuils numériques sont particulièrement utiles pour tout développeur C qui manipule des factorielles :
- 12! est la plus grande factorielle qui tient généralement dans un int signé 32 bits standard.
- 20! est la plus grande factorielle qui tient généralement dans un signed long long 64 bits standard.
- Au-delà d’environ 170!, même un double IEEE 754 dépasse typiquement sa plage finie et tend vers l’infini.
Ces chiffres sont très utiles dans une calculatrice comme celle de cette page, car ils permettent de prévenir immédiatement l’utilisateur lorsque le type sélectionné n’est plus adapté.
Liens d’autorité pour approfondir
- NIST Digital Library of Mathematical Functions
- Cornell University – ressources de programmation système et C
- Purdue University – cours de programmation en C
Conclusion
Le calcul de factorielle en C est bien plus qu’un exercice de base. C’est un sujet qui croise mathématiques, représentation machine, fiabilité logicielle et choix algorithmiques. Si vous devez calculer n! pour de petites valeurs exactes, une boucle itérative avec long long et détection d’overflow constitue souvent la meilleure solution. Si vous étudiez la notion de récursion, une fonction récursive reste très pédagogique. Enfin, si vous travaillez sur de très grandes valeurs, les types natifs du C ne suffisent plus : il faut soit passer à la multiprécision, soit utiliser des approximations et des logarithmes selon le besoin.