factorielle — Programme de démonstration

Un programme C qui calcule n!, avec des tests qui vérifient qu'il ne raconte pas n'importe quoi.

1. C'est quoi la factorielle ?

La factorielle de n, notée n!, c'est le produit de tous les entiers de 1 à n. Par convention, 0! = 1 (parce que les mathématiciens aiment bien que leurs formules marchent même quand il n'y a rien à multiplier).

n! = 1 × 2 × 3 × … × n

n	n!
0	1
1	1
2	2
3	6
4	24
5	120
6	720
7	5 040
8	40 320
9	362 880
10	3 628 800
12	479 001 600
20	2 432 902 008 176 640 000

📈 La factorielle a une croissance exponentielle qui ferait pleurer un lapin dans un concours de reproduction : 10! c'est déjà 3,6 millions, 20! c'est 2,4 milliards de milliards. Et 100! dépasse le nombre d'atomes dans l'univers observable. (Oui, on a vérifié. Non, on ne l'a pas calculé avec notre programme — ça dépasse le long long.)

2. Le code pas à pas

Deux fonctions, pas une de plus. On n'est pas là pour faire du volume.

factorielle() — le moteur

long long factorielle(int n) {
    if (n < 0) return -1;      // cas d'erreur : pas de factorielle pour les négatifs
    long long res = 1;
    for (int i = 2; i <= n; i++) {
        res *= i;
    }
    return res;
}

Algorithme : itératif. On part de 1, on multiplie par tous les entiers de 2 à n. C'est simple, c'est lisible, et ça marche pour n jusqu'à 20 avant que long long (64 bits) ne dise « stop, je déborder ».

🧠 Pourquoi itératif et pas récursif ? Parce que la récursion c'est joli dans un cours, mais dans la vraie vie les gens compilent avec -O2 et le compilateur transforme votre belle récursion en boucle de toute façon. Autant l'écrire directement et économiser une pile d'appels. Et des nerfs.

main() — le banc de test

int main() {
    struct {
        int n;
        long long attendu;
    } tests[] = {
        {0,  1},
        {1,  1},
        {2,  2},
        {3,  6},
        {5,  120},
        {10, 3628800},
        {12, 479001600},
        {20, 2432902008176640000LL},
    };
    // ... parcourir, comparer, afficher OK/FAIL ...
}

8 cas de test qui couvrent :

Cas limites : 0! (convention mathématique) et 1!
Petites valeurs : 2, 3, 5 — on vérifie que la boucle tourne droit
Valeurs moyennes : 10, 12 — on vérifie que le long long tient la route
Maximum : 20 — la plus grande factorielle qui tient dans 64 bits

✅ Aucun test pour n négatif dans le tableau — c'est testé dans la fonction (qui retourne -1). Mais on pourrait ajouter un test qui vérifie que la fonction ne plante pas. On pourrait aussi ranger sa chambre. Les deux arriveront un jour.

3. Sortie du programme

Quand tout va bien :

OK   factorielle(0) = 1
OK   factorielle(1) = 1
OK   factorielle(2) = 2
OK   factorielle(3) = 6
OK   factorielle(5) = 120
OK   factorielle(10) = 3628800
OK   factorielle(12) = 479001600
OK   factorielle(20) = 2432902008176640000

8 passes, 0 echoues sur 8 tests

Si un test échoue (par exemple si on a cassé la fonction) :

OK   factorielle(0) = 1
FAIL factorielle(3) = 5 (attendu 6)
OK   factorielle(5) = 120
...

1 passes, 1 echoues sur 8 tests

Le code de retour est EXIT_SUCCESS (0) si tout passe, EXIT_FAILURE (1) sinon. Utile pour les scripts : on peut faire make run && echo "tout va bien".

🎯 Le code de retour, c'est le « tout roule » ou « j'explose » du programme. Les scripts shell l'utilisent pour décider de la suite des opérations. Un exit(1) bien placé, c'est l'assurance-vie de votre pipeline CI.

4. Limitations — le mur du long long

⚠️ 21! ne tient pas dans 64 bits

long long (signé, 64 bits) peut stocker au maximum
9 223 372 036 854 775 807 (2⁶³−1).

20! = 2 432 902 008 176 640 000 < 9,22×10¹⁸ → ✅ OK
21! = 51 090 942 171 709 440 000 > 9,22×10¹⁸ → ❌ Débordement

Quand ça déborde, le compilateur ne dit rien (pas de vérification à l'exécution en C). On obtient juste un résultat faux, modulo 2⁶⁴ — c'est-à-dire complètement à côté de la plaque.

5. Compilation et exécution

n	Résultat réel	`long long` retourné
20	2 432 902 008 176 640 000	✅ Correct
21	51 090 942 171 709 440 000	❌ 30 414 093 201 713 037 824 (modulo 2⁶⁴)
30	265 252 859 812 191 058 636 308 480 000 000	❌ Faux complet

Le projet utilise un Makefile conçu pour l'exploration pédagogique :

Commande	Ce qui se passe
`make run`	Compile et lance les tests
`make asm`	Génère le fichier assembleur
`make debug`	Compile en debug et ouvre gdb
`make perf`	Compare les niveaux d'optimisation
`make clean`	Nettoie tout (comme si on n'avait jamais rien fait)

🧹 make clean a le même effet psychologique que ranger son bureau le vendredi soir: on a l'impression que tout est possible lundi matin. (Spoiler : lundi matin, on relance make et ça repart.)

6. Variantes possibles

Variante	Description	Avantage	Inconvénient
Récursive	`if (n <= 1) return 1; return n * factorielle(n-1);`	Élégante, mathématique	Risque de stack overflow pour grand n, plus lent sans tail-call
Récursive terminale	`return fact_iter(n, 1)` avec accumulateur	Le compilateur peut optimiser en boucle	Syntaxe plus lourde, nécessite deux fonctions
Table précalculée	Un tableau `fact[21]` rempli à la compilation	Temps constant (O(1))	Fixe, pas de généralisation
Arbitrary Precision	Utilise `__int128` (GCC/clang) ou GMP	Plus de limite de taille	Moins portable, plus complexe
Template / générique	Macro ou fonction template pour choisir le type retour	Flexible	Horrible à débugger (surtout les macros)

🔁 La version récursive, c'est comme les poupées russes : tu ouvres une fonction, il y en a une autre, puis une autre… jusqu'à ce que la plus petite retourne 1. Ensuite tout se referme dans l'ordre inverse. Poétique, mais coûteux en pile. Et il n'y a pas de vodka à la fin.

7. Usage dans le monde réel

La factorielle sert (entre autres) à :

Probabilités et combinatoire : nombre de permutations de n éléments distincts = n!
Coefficients binomiaux : C(n, k) = n! / (k! × (n − k)!)
Développements de Taylor : sin, cos, exp sous forme de séries entières
Analyse algorithmique : tri par comparaison nécessite Ω(n log n) comparaisons (merci Stirling)
Gammes musicales : le nombre de façons de jouer n notes dans un ordre différent
Et… le calcul de votre patience quand vous attendez 40! pour rigoler

🎲 En combinatoire, la factorielle c'est la réponse à la question « de combien de façons peut-on organiser le désordre ? ». Spoiler : beaucoup. Pour 10 personnes autour d'une table : 3 628 800 façons. Plus que de raisons d'éviter les repas de famille.

8. Fiche récap

Propriété	Valeur
Langage	C99
Algorithme	Itératif, O(n) en temps, O(1) en mémoire
Type de retour	`long long` (64 bits signé)
Plage valide	0 ≤ n ≤ 20 (n < 0 → -1, n > 20 → overflow silencieux)
Tests	8 cas, couvrant n ∈ {0, 1, 2, 3, 5, 10, 12, 20}
Compilation	`gcc -Wall -Wextra -std=c99 -o factorielle factorielle.c`
Make	`make run`

🎓 Ce programme est probablement le premier qu'on écrit dans un nouveau langage, juste après hello world. C'est le « bonjour le monde » des mathématiques. Si votre factorielle ne marche pas, vous n'êtes pas prêt pour le tri fusion. (Allez, on rigole, mais rm -rf * c'est quand même pas une bonne idée.)

📐 factorielle

1. C'est quoi la factorielle ?

2. Le code pas à pas

factorielle() — le moteur

main() — le banc de test

3. Sortie du programme

4. Limitations — le mur du `long long`

5. Compilation et exécution

6. Variantes possibles

7. Usage dans le monde réel

8. Fiche récap

📐 factorielle

1. C'est quoi la factorielle ?

2. Le code pas à pas

factorielle() — le moteur

main() — le banc de test

3. Sortie du programme

4. Limitations — le mur du long long

5. Compilation et exécution

6. Variantes possibles

7. Usage dans le monde réel

8. Fiche récap

1. C'est quoi la factorielle ?

4. Limitations — le mur du `long long`