2. La Factorielle (n!)

C’est l’exemple classique. La factorielle de n est le produit de tous les entiers de 1 à n.

Définition :

• 0! = 1 (Convention mathématique, base)
• n! = n × (n-1)!

Algorithme :

Fonction Factorielle(n : entier) : entier;
Début
    Si n = 0 alors
        Retourne 1;
    Sinon
        Retourne n * Factorielle(n - 1);
    Fin Si;
Fin;

Trace pour Factorielle(4) :

1. Factorielle(4) veut calculer 4 * Factorielle(3)
2. Factorielle(3) veut calculer 3 * Factorielle(2)
3. Factorielle(2) veut calculer 2 * Factorielle(1)
4. Factorielle(1) veut calculer 1 * Factorielle(0)
5. Factorielle(0) retourne 1.

Remontée des résultats :

• Étape 4 reçoit 1 -> retourne 1 × 1 = 1.
• Étape 3 reçoit 1 -> retourne 2 × 1 = 2.
• Étape 2 reçoit 2 -> retourne 3 × 2 = 6.
• Étape 1 reçoit 6 -> retourne 4 × 6 = 24.

---

3. La Série de Fibonacci

La suite de Fibonacci est définie par la somme des deux termes précédents.

Définition :

• F(0) = 0
• F(1) = 1 (Bases)
• F(n) = F(n-1) + F(n-2) pour n ≥ 2

Algorithme :

Fonction Fibonacci(n : entier) : entier;
Début
    Si n <= 1 alors
        Retourne n; // Retourne 0 si n=0, ou 1 si n=1
    Sinon
        Retourne Fibonacci(n - 1) + Fibonacci(n - 2);
    Fin Si;
Fin;

Trace simplifiée pour Fibonacci(4) : Cet arbre montre pourquoi la récursivité simple pour Fibonacci peut être lente : on recalcule plusieurs fois les mêmes valeurs.

• Fib(4)
  • Appelle Fib(3)
    • Appelle Fib(2) -> (1+0) = 1
    • Appelle Fib(1) -> 1
    • Résultat : 2
  • Appelle Fib(2) -> (1+0) = 1
  • Résultat total : 2 + 1 = 3.

---

IV. Types de Récursivité (Approfondissement)

Il existe plusieurs “façons” d’être récursif :

1. Récursivité linéaire : La fonction s’appelle une seule fois par appel.
   • Exemple : Factorielle, Puissance2.
   • Complexité : Généralement O(n).
2. Récursivité multiple (ou arborescente) : La fonction s’appelle plusieurs fois par appel.
   • Exemple : Fibonacci (appelle n-1 ET n-2).
   • Complexité : Peut être exponentielle (O(2^n) pour Fibonacci), donc coûteuse.
3. Récursivité terminale (Tail Recursion) : L’appel récursif est la toute dernière action effectuée par la fonction. Il n’y a pas de calcul en attente après le retour de l’appel récursif (comme la multiplication par n dans la factorielle).
   • Avantage : Le compilateur peut optimiser pour ne pas saturer la mémoire (pile), transformant la récursion en boucle itérative.

---

V. Exemples Supplémentaires et Exercices

Pour bien comprendre, voici d’autres applications classiques.

Exemple 4 : Somme des N premiers entiers

Calculer S(n) = 1 + 2 + 3 + … + n.

• Base : S(0) = 0 (ou S(1) = 1).
• Récurrence : S(n) = n + S(n-1).

Fonction Somme(n : entier) : entier;
Début
    Si n = 0 alors
        Retourne 0;
    Sinon
        Retourne n + Somme(n - 1);
    Fin Si;
Fin;

Exemple 5 : Le PGCD (Algorithme d’Euclide)

Le Plus Grand Commun Diviseur de deux entiers a et b.

• Base : Si b = 0, alors PGCD(a, 0) = a.
• Récurrence : PGCD(a, b) = PGCD(b, a mod b).

Fonction PGCD(a : entier, b : entier) : entier;
Début
    Si b = 0 alors
        Retourne a;
    Sinon
        Retourne PGCD(b, a mod b);
    Fin Si;
Fin;

Exemple 6 : Inverser un tableau (Récursivité)

On veut afficher un tableau à l’envers sans utiliser de boucle “Pour” inversée.

• Idée : Pour afficher le tableau T de taille n, on affiche d’abord l’élément actuel T[i], puis on demande d’afficher le reste (i+1 à n) à l’envers… Ah non, pour inverser, on doit d’abord traiter la fin avant le début.
• Logique : On avance jusqu’à la fin, et à chaque retour, on affiche l’élément.

Procédure AfficherInverse(Var T : tableau; i : entier, n : entier);
Début
    Si i <= n alors
        // On descend d'abord jusqu'au bout
        AfficherInverse(T, i + 1, n);
        // Au retour (remontée), on affiche
        Ecrire(T[i]);
    Fin Si;
Fin;

Si on appelle AfficherInverse(T, 1, 3) avec T=[10,20,30] :

1. Appel i=1 -> Appel i=2 -> Appel i=3 -> Appel i=4 (arrêt).
2. Retour i=3 : Affiche 30.
3. Retour i=2 : Affiche 20.
4. Retour i=1 : Affiche 10. Résultat : 30, 20, 10.

VI. Résumé et Conseils

1. Toujours identifier la condition d’arrêt en premier. Demandez-vous : “Quel est le cas le plus simple ?”.
2. Vérifier la convergence : Assurez-vous que les paramètres passés lors de l’appel récursif se rapprochent de la condition d’arrêt (ex: n-1 se rapproche de 0).
3. La Pile (Stack) : Rappelez-vous que l’ordinateur “empile” les appels. Si la récursivité est trop profonde (ex: Factorielle de 1 000 000), le programme peut planquer par manque de mémoire (Stack Overflow). Dans ce cas, une boucle itérative (Tant que ou Pour) est préférable.