Récursivité : définition et écriture

Avant de commencer

Vous savez calculer 5! itérativement (1 × 2 × 3 × 4 × 5). Mais définition mathématique : n! = n × (n − 1)!. Cette définition contient elle-même (n−1)!. Comment exprimer cela en code ?

1. Qu'est-ce qu'une fonction récursive ?

2. Premier exemple : la factorielle

n! = 1                  si n ≤ 1   ← cas de base
n! = n × (n − 1)!       si n > 1   ← cas général

DEF FN Factorielle(n : entier) : entier
  Si n <= 1 Alors
    Factorielle ← 1            { cas de base }
  Sinon
    Factorielle ← n * Factorielle(n - 1)   { cas général }
  FinSi
Fin Factorielle

DEF FN Factorielle(n : entier) : entier
  Si n <= 1 Alors
    Factorielle ← 1            { cas de base }
  Sinon
    Factorielle ← n * Factorielle(n - 1)   { cas général }
  FinSi
Fin Factorielle

FUNCTION Factorielle(n : integer) : longint;
BEGIN
  IF n <= 1 THEN
    Factorielle := 1
  ELSE
    Factorielle := n * Factorielle(n - 1);
END;

3. Trace d'exécution de Factorielle(4)

Factorielle(4)
= 4 × Factorielle(3)
= 4 × (3 × Factorielle(2))
= 4 × (3 × (2 × Factorielle(1)))
= 4 × (3 × (2 × 1))           ← cas de base atteint
= 4 × (3 × 2)
= 4 × 6
= 24

4. Conditions pour qu'une récursion termine

1. Au moins un cas de base (test qui retourne sans appel récursif).
2. Les arguments convergent vers ce cas de base à chaque appel.
3. Le langage supporte des appels imbriqués (Pascal : OUI).

Contre-exemple : récursion infinie

FUNCTION Mauvaise(n : integer) : integer;
BEGIN
  Mauvaise := Mauvaise(n + 1);   { jamais de cas de base }
END;

S'exécute jusqu'à épuisement de la pile (erreur d'exécution).

5. Deuxième exemple : compter à rebours

PROCEDURE Decompter(n : integer);
BEGIN
  IF n = 0 THEN
    Writeln('Boum !')
  ELSE
  BEGIN
    Writeln(n);
    Decompter(n - 1);
  END;
END;

Decompter(3) affiche : 3, 2, 1, Boum !.

6. Exercices

FUNCTION Somme(n : integer) : integer;
BEGIN
  IF n <= 0 THEN
    Somme := 0                          { cas de base }
  ELSE
    Somme := n + Somme(n - 1);          { cas général }
END;

FUNCTION Puissance(base, exp : integer) : longint;
BEGIN
  IF exp = 0 THEN
    Puissance := 1
  ELSE
    Puissance := base * Puissance(base, exp - 1);
END;

PROCEDURE Hanoi(n : integer; A, B, C : char);
BEGIN
  IF n = 1 THEN
    Writeln('Déplacer disque 1 : ', A, ' -> ', C)
  ELSE
  BEGIN
    Hanoi(n - 1, A, C, B);              { n-1 disques de A vers B }
    Writeln('Déplacer disque ', n, ' : ', A, ' -> ', C);
    Hanoi(n - 1, B, A, C);              { n-1 disques de B vers C }
  END;
END;

BEGIN
  Hanoi(3, 'A', 'B', 'C');
END.

7. Erreurs fréquentes au bac

• Oublier le cas de base → récursion infinie.
• Cas général qui s'éloigne du cas de base (Somme(n+1) au lieu de Somme(n-1)).
• Récursion non terminée : n n'est pas modifié dans l'appel récursif.
• Confondre n := (affectation à une variable locale) avec la valeur retournée (Factorielle := ... en Pascal).

8. Quiz