Factorielle en C - L'approche fiable sans débordement

Calculer la factorielle en C est un excellent exercice pour comprendre à la fois les boucles, la récursion et les limites des types entiers. Je vais partir du cas concret: écrire un programme correct, lisible et capable de signaler quand le résultat ne tient plus dans une variable classique. Vous verrez aussi pourquoi je privilégie souvent une boucle dans un vrai projet, même si la version récursive reste très utile pour apprendre.

Ce que la factorielle demande vraiment

La règle mathématique est simple: pour un entier `n` positif, `n! = 1 × 2 × 3 × ... × n`. En pratique, le premier réflexe consiste à traiter correctement trois cas: `n = 0`, `n = 1` et `n < 0`. La première erreur que je vois souvent, c’est d’oublier que 0! = 1 et non `0`, ce qui casse très vite un programme censé être rigoureux.

Il faut aussi accepter une réalité moins confortable: la factorielle explose. Même avec des types entiers modernes, on atteint vite la limite. C’est pour cela que le sujet n’est pas seulement “comment écrire une formule”, mais aussi “comment protéger le programme contre les entrées qui dépassent la capacité du type choisi”. Une fois ce point clair, la bonne implémentation devient beaucoup plus évidente.

• `0! = 1`
• `1! = 1`
• Pour `n < 0`, le résultat n’est pas défini dans le cadre classique du programme entier
• La croissance est très rapide, donc le choix du type compte autant que l’algorithme

Avec cette base, on peut passer au code sans se tromper sur le sens du calcul, puis décider si une boucle ou une fonction récursive est la meilleure forme pour votre cas.

La version la plus simple avec une boucle

Pour un programme C propre et prévisible, je pars presque toujours d’une boucle. Elle est lisible, elle évite la pile d’appels, et elle permet de contrôler le débordement avant qu’il ne produise un résultat faux. C’est la version que je garderais pour un utilitaire, un petit outil interne ou un exercice à rendre sans artifices.

#include 
#include 

int main(void) {
    long long n;
    unsigned long long resultat = 1;

    printf("Entrez un entier positif : ");
    if (scanf("%lld", &n) != 1 || n < 0) {
        printf("Entrée invalide\n");
        return 1;
    }

    for (long long i = 2; i <= n; ++i) {
        if (resultat > ULLONG_MAX / (unsigned long long)i) {
            printf("Dépassement de capacité\n");
            return 1;
        }
        resultat *= (unsigned long long)i;
    }

    printf("%lld! = %llu\n", n, resultat);
    return 0;
}

Ce code fait trois choses importantes que je considère comme non négociables: il valide l’entrée, il calcule itérativement, et il bloque avant le débordement. Le test `resultat > ULLONG_MAX / i` est la partie la plus intéressante, parce qu’il vérifie le risque avant la multiplication. Autrement dit, on ne laisse pas le programme produire une valeur corrompue puis essayer de la corriger après coup.

Dans une logique de production, c’est souvent ce que je recommande. La prochaine question naturelle est alors de savoir si la récursion apporte quelque chose de plus élégant ou de plus pédagogique.

La version récursive et ce qu’elle implique

La version récursive est plus courte et plus proche de la définition mathématique. Elle convient très bien pour illustrer l’idée de base case et de recursive case, c’est-à-dire le cas d’arrêt et l’appel du sous-problème. En revanche, elle n’est pas la solution la plus robuste si vous comptez traiter des entrées élevées ou des contextes où la profondeur d’appel doit rester maîtrisée.

unsigned long long factorielle(unsigned int n) {
    if (n < 2) {
        return 1;
    }
    return n * factorielle(n - 1);
}

Ici, `n < 2` joue le rôle de cas d’arrêt. Sans lui, la fonction s’appellerait elle-même indéfiniment jusqu’à épuiser la pile. Chaque appel crée son propre cadre d’exécution, avec ses variables et son retour en attente. C’est pour cela que la récursion finit par consommer de la mémoire de pile, même si le code semble minuscule à l’écran.

Je précise aussi un point qui évite bien des malentendus: en C, il ne faut pas compter sur une optimisation terminale pour transformer automatiquement cette fonction en boucle. Même quand le compilateur sait parfois l’appliquer, ce n’est pas une garantie de conception. Si vous voulez une récursion terminale, il faut l’écrire explicitement avec un accumulateur, mais pour une factorielle je trouve souvent la boucle plus nette et plus sûre.

Cette version a donc surtout de la valeur pour apprendre et pour expliquer la mécanique de l’appel de fonction. Dès qu’on passe à l’exécution réelle, la vraie limite devient celle des entiers, pas celle de la syntaxe.

Le vrai piège est le débordement numérique

Sur une machine moderne, le problème n’est pas de savoir multiplier, mais de savoir jusqu’où les multiplications restent exactes. La factorielle grandit si vite qu’un type trop petit donne un résultat faux alors que le programme a l’air de fonctionner. C’est l’un des pièges les plus classiques en C, et franchement l’un des plus trompeurs pour un débutant.

Pour moi, la bonne règle est simple: si vous voulez rester en entier natif, posez une limite explicite. Si vous voulez aller plus loin, changez d’outil au lieu d’espérer qu’un type standard suffira. C’est aussi pour cela que je garde souvent une vérification du type `if (resultat > ULLONG_MAX / i)` avant chaque multiplication.

Un autre point utile: changer l’ordre des calculs ne résout pas le problème. La factorielle ne se “réorganise” pas magiquement pour éviter le débordement. Dès que la valeur cible dépasse la capacité du type, il faut soit arrêter proprement, soit passer à une représentation plus large. C’est cette contrainte qui détermine ensuite le choix de l’implémentation la plus adaptée.

Ce que je ferais dans un vrai projet C

Si je dois livrer un code propre, je choisis la méthode en fonction du but réel, pas en fonction de la beauté théorique de l’algorithme. Pour un exercice pédagogique, je montre la récursion. Pour un programme simple, je garde la boucle. Pour un calcul exact au-delà des limites natives, je change d’outillage. C’est la manière la plus honnête de traiter ce sujet.

Mon réflexe, dans la pratique, est de documenter la limite maximale acceptée par le programme et de la faire respecter explicitement. C’est plus utile qu’un code “général” qui affiche un nombre faux sans prévenir. Si vous retenez une seule idée, gardez celle-ci: en C, la difficulté n’est pas de calculer la factorielle, mais de la calculer sans mentir sur le résultat.