Récursivité

Définitions récursives

La factorielle

La factorielle d’un entier naturel $n$ est le produit des entiers naturels de 1 à $n$ : $n! = 1 \cdot 2 \cdots n$, avec la convention $0! = 1$. Les points de suspension de cette formule cachent une boucle, et la leçon Boucles a appris à l’écrire. Or la même définition admet une autre forme, qui ne mentionne aucune boucle : la factorielle de $n$ est $n$ fois la factorielle de $n - 1$, et celle de 0 vaut 1.

C’est une définition récursive : elle définit la factorielle de $n$ au moyen de la factorielle d’un nombre plus petit. Elle n’est pas circulaire, car chaque application de la seconde règle descend d’une marche et l’escalier se termine sur la première : $3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 \cdot 0! = 6$. Les deux règles ont un nom. La première est le cas de base, qui donne le résultat sans renvoyer à rien d’autre ; la seconde est le cas récursif, qui ramène le problème à une instance plus petite du même problème.

C++ permet à une fonction de s’appeler elle-même, et la définition se traduit alors presque mot pour mot.

#include <print>​// Factorielle de n.// Précondition : 0 <= n <= 12 (la borne est justifiée plus loin).// Postcondition : renvoie n! = 1 · 2 · ... · n, avec 0! = 1.int factorial(int n){    if (n == 0) {        return 1;                   // cas de base    }    return n * factorial(n - 1);    // cas récursif}​int main(){    for (int n{0}; n <= 6; ++n) {        std::println("{}! = {}", n, factorial(n));    }}

0! = 11! = 12! = 23! = 64! = 245! = 1206! = 720

Le contrat n’est pas décoratif : avec $n = -1$, le cas récursif appellerait avec $-2$, puis avec $-3$, et n’atteindrait jamais 0 ; et $13!$ ne tient pas dans un int. Beaucoup de textes d’introduction écrivent cette factorielle avec le cas de base if (n == 0 || n == 1), redondant mais inoffensif, et sans rien dire des négatifs ni de la taille du résultat : leur code ne se termine pas avec $n < 0$ et donne un résultat dénué de sens à partir de $13!$. Ces deux défauts seront examinés dans leur section.

Cas de base et cas récursif

Toute fonction récursive a un ou plusieurs cas de base, qui se résolvent directement, et un ou plusieurs cas récursifs, qui appellent la même fonction avec un argument plus petit en un sens précis et combinent ce qu’elle renvoie.

La puissance $x^n$, avec $n$ naturel, se définit par $x^0 = 1$ et $x^n = x \cdot x^{n - 1}$ : la taille est l’exposant. La somme des chiffres d’un entier naturel $n$ (celle de 2026 est $2 + 0 + 2 + 6 = 10$) se définit ainsi : si $n < 10$, la somme est $n$, car il n’a qu’un chiffre ; sinon, c’est la somme des chiffres de $\lfloor n / 10 \rfloor$, qui est $n$ privé de son dernier chiffre, plus ce dernier chiffre, $n \bmod 10$. Ici, la taille est le nombre de chiffres.

#include <print>​// x élevé à la puissance n.// Précondition : n >= 0.// Postcondition : renvoie x^n, avec x^0 = 1.double power(double x, int n){    if (n == 0) {        return 1.0;    }    return x * power(x, n - 1);}​// Somme des chiffres décimaux de n.// Précondition : n >= 0.// Postcondition : renvoie la somme des chiffres de n.int digitSum(int n){    if (n < 10) {        return n;    }    return digitSum(n / 10) + n % 10;}​int main(){    std::println("2^10 = {}", power(2.0, 10));    std::println("1.5^3 = {}", power(1.5, 3));    std::println("somme des chiffres de 2026 : {}", digitSum(2026));}

2^10 = 10241.5^3 = 3.375somme des chiffres de 2026 : 10

Écrire une fonction récursive consiste donc à répondre à deux questions : quels cas se résolvent sans aide, et comment on obtient la solution d’un cas à partir de celle d’un cas plus petit. Si les deux réponses sont correctes, la fonction l’est aussi, et la section suivante le démontre.