"Récursivité : Calcul de la factorielle"

Introduction

Dans la leçon précédente, nous avons disséqué l'anatomie d'une fonction récursive. Nous avons appris à identifier ses deux composantes cruciales : le cas de base, qui stoppe la récursivité, et le cas récursif, où la fonction s'appelle elle-même pour se rapprocher de la solution.

L'objectif d'aujourd'hui est de franchir une étape décisive : nous allons écrire notre première fonction récursive simple en pseudo-code. Nous allons assembler les briques que nous avons identifiées pour construire un algorithme fonctionnel. Pour ce faire, nous reprendrons l'exemple du calcul de la factorielle, un problème désormais familier qui se prête parfaitement à cet exercice. En fin de leçon, vous serez capable de traduire une définition mathématique récursive en un algorithme concret.

1. La méthode pour écrire une fonction récursive

Avant de nous lancer dans le code, rappelons la stratégie générale. Écrire une fonction récursive est une démarche très structurée.

Comme vous l'avez lu, la recette est presque toujours la même :

1. Traiter le cas de base : On commence par écrire la condition qui arrête la récursivité. C'est le cas le plus simple du problème, celui pour lequel on connaît la réponse directement. Cela se traduit souvent par une structure SI ... ALORS RETOURNER une_valeur_simple.
2. Traiter le cas récursif : Ensuite, on gère tous les autres cas. C'est ici que l'on formule la solution du problème en fonction de la solution d'un problème plus petit. C'est l'appel récursif. Il se trouve généralement dans la partie SINON de la structure conditionnelle.

Appliquons immédiatement cette méthode au calcul de la factorielle.

2. Écriture de la fonction factorielle

Rappelons la définition mathématique de la factorielle :

• Cas de base : $0!=1$
• Cas récursif : $n!=n\times (n-1)!$ pour $n>0$

Nous avons tout ce qu'il nous faut pour écrire notre fonction.

Voici le pseudo-code que vous venez de voir, que nous allons analyser ensemble :

Fonction FACTORIELLE(n : Entier) : Entier
DEBUT
    // Étape 1 : Gérer le cas de base
    SI (n = 0) ALORS
        RETOURNER 1
    
    // Étape 2 : Gérer le cas récursif
    SINON
        RETOURNER n * FACTORIELLE(n - 1)
    FIN SI
FIN

Décortiquons cet algorithme :

• Fonction FACTORIELLE(n : Entier) : Entier : C'est la signature de la fonction. Elle s'appelle FACTORIELLE, prend un paramètre n de type Entier, et retourne un résultat de type Entier.
• SI (n = 0) ALORS RETOURNER 1 : Voici notre cas de base. Si la fonction est appelée avec l'argument 0, elle retourne immédiatement 1 sans autre appel. La récursivité s'arrête ici.
• SINON RETOURNER n * FACTORIELLE(n - 1) : C'est le cas récursif. Si n n'est pas 0, la fonction retourne le résultat de n multiplié par le résultat de l'appel à elle-même (FACTORIELLE) avec un argument plus petit (n - 1). C'est ici que la "magie" opère.

3. Comment ça marche ? Le traçage des appels

Écrire la fonction est une chose, mais il est fondamental de comprendre comment l'ordinateur l'exécute. Ce processus peut sembler déroutant au début. Visualisons-le.

Imaginons que nous voulons calculer FACTORIELLE(4).

Le processus se déroule en deux temps :

1. La descente (ou l'empilement des appels) :

   • FACTORIELLE(4) est appelé. Puisque 4 ≠ 0, il doit calculer 4 * FACTORIELLE(3). Il se met en pause en attendant le résultat.
   • FACTORIELLE(3) est appelé. Puisque 3 ≠ 0, il doit calculer 3 * FACTORIELLE(2). Il se met en pause.
   • FACTORIELLE(2) est appelé. Puisque 2 ≠ 0, il doit calculer 2 * FACTORIELLE(1). Il se met en pause.
   • FACTORIELLE(1) est appelé. Puisque 1 ≠ 0, il doit calculer 1 * FACTORIELLE(0). Il se met en pause.
   • FACTORIELLE(0) est appelé. Le cas de base est atteint !

2. La montée (ou le dépilement et le calcul) :

   • FACTORIELLE(0) retourne 1.
   • FACTORIELLE(1), qui attendait, reçoit 1. Il peut finir son calcul : 1 * 1 et retourne 1.
   • FACTORIELLE(2), qui attendait, reçoit 1. Il peut finir son calcul : 2 * 1 et retourne 2.
   • FACTORIELLE(3), qui attendait, reçoit 2. Il peut finir son calcul : 3 * 2 et retourne 6.
   • FACTORIELLE(4), qui attendait, reçoit 6. Il peut finir son calcul : 4 * 6 et retourne 24.

Le résultat final est 24.

Pour renforcer cette idée, voici une autre façon de visualiser le traçage, sous forme de texte.

4. À vous de jouer !

Maintenant que vous avez vu comment construire et tracer une fonction récursive, il est temps de mettre la main à la pâte. Votre préférence pour la pratique va être servie !

Problème : Écrire une fonction récursive SommeCarres(n) qui calcule la somme des carrés des n premiers entiers.
Par exemple, SommeCarres(3) doit calculer $1^2+2^2+3^2=1+4+9=14$.
La formule est : $S_n=1^2+2^2+\cdots +n^2$

En utilisant la méthode vue plus haut, essayez d'écrire cette fonction en pseudo-code. Pour cela, répondez d'abord à ces deux questions :

1. Quelle est la version la plus simple de ce problème ? (le cas de base)
2. Comment pouvez-vous exprimer $S_n$ en fonction de $S_{n-1}$ ? (le cas récursif)

Prenez un papier et un crayon, et essayez de formuler l'algorithme complet.

...

Solution :

1. Cas de base : Le cas le plus simple est de calculer la somme des carrés pour n=0. La somme est vide, donc le résultat est 0. SommeCarres(0) = 0.
2. Cas récursif : La somme des carrés jusqu'à n est simplement la somme des carrés jusqu'à n-1, à laquelle on ajoute n au carré.
   $S_n=(1^2+2^2+\cdots +(n-1{)}^2)+n^2$
   Donc, $S_n=S_{n-1}+n^2$.
   En termes de fonction : SommeCarres(n) = SommeCarres(n-1) + n*n.

Avec ces deux éléments, nous pouvons écrire le pseudo-code :

Fonction SommeCarres(n : Entier) : Entier
DEBUT
    // Cas de base
    SI (n = 0) ALORS
        RETOURNER 0
    
    // Cas récursif
    SINON
        RETOURNER n*n + SommeCarres(n - 1)
    FIN SI
FIN

Félicitations si vous avez trouvé une solution similaire ! C'est exactement la même structure logique que pour la fonction factorielle.

Conclusion

Aujourd'hui, vous avez franchi une étape majeure en passant de l'analyse à la création. Vous avez écrit votre première fonction récursive, en suivant une méthode structurée qui sera votre guide pour des problèmes bien plus complexes.

Les points clés à retenir :

• L'écriture d'une fonction récursive suit une méthode en deux temps : d'abord le cas de base, ensuite le cas récursif.
• La structure SI ... SINON ... est l'outil parfait pour implémenter cette logique.
• La définition mathématique d'un problème récursif se traduit presque directement en pseudo-code.
• Comprendre le mécanisme de "descente" (empilement des appels) et de "montée" (calcul des retours) est essentiel pour maîtriser la récursivité.

Et après ?

Nous avons visualisé l'exécution d'une fonction récursive de manière intuitive. Dans la prochaine leçon, nous allons formaliser ce processus. Nous apprendrons à tracer l'exécution d'une fonction récursive simple en utilisant la "pile d'appels". C'est un outil mental et technique indispensable pour comprendre en profondeur, déboguer, et analyser le comportement de vos futurs algorithmes récursifs.