Applications de la récursivité

Avant de commencer

La récursion est élégante pour les problèmes définis récursivement. Voyons des cas classiques où elle brille (et un où elle échoue).

1. Palindrome

Une chaîne est palindrome si elle se lit pareil dans les deux sens : "laval", "radar", "", "a".

Définition récursive :

• Longueur ≤ 1 → palindrome.
• Sinon : premier caractère = dernier ET le sous-mot intérieur est palindrome.

DEF FN Palindrome(CH : chaîne) : booléen
  Si Long(CH) <= 1 Alors
    Palindrome ← Vrai                     { cas particulier (Vrai) }
  Sinon Si CH[1] ≠ CH[Long(CH)] Alors
    Palindrome ← Faux                     { cas particulier (Faux) }
  Sinon
    Palindrome ← FN Palindrome(Sous_chaine(CH, 2, Long(CH) - 2))
  FinSi
Fin Palindrome

DEF FN Palindrome(CH : chaîne) : booléen
  Si Long(CH) <= 1 Alors
    Palindrome ← Vrai                     { cas particulier (Vrai) }
  Sinon Si CH[1] ≠ CH[Long(CH)] Alors
    Palindrome ← Faux                     { cas particulier (Faux) }
  Sinon
    Palindrome ← FN Palindrome(Sous_chaine(CH, 2, Long(CH) - 2))
  FinSi
Fin Palindrome

FUNCTION Palindrome(ch : string) : boolean;
VAR n : integer;
BEGIN
  n := Length(ch);
  IF n <= 1 THEN
    Palindrome := true                  { cas particulier (Vrai) }
  ELSE IF ch[1] <> ch[n] THEN
    Palindrome := false                 { cas particulier (Faux) }
  ELSE
    Palindrome := Palindrome(Copy(ch, 2, n - 2));   { récursion }
END;

Trace pour "laval" :

• Palindrome("laval") → 'l' = 'l' → Palindrome("ava")
• Palindrome("ava") → 'a' = 'a' → Palindrome("v")
• Palindrome("v") → longueur 1 → vrai.

2. Puissance rapide (exponentiation par carré)

base^exp :

• exp = 0 → 1.
• exp pair → (base^(exp/2))².
• exp impair → base × base^(exp-1).

FUNCTION PuissRapide(base : integer; exp : integer) : longint;
VAR temp : longint;
BEGIN
  IF exp = 0 THEN
    PuissRapide := 1
  ELSE IF exp MOD 2 = 0 THEN
  BEGIN
    temp := PuissRapide(base, exp DIV 2);
    PuissRapide := temp * temp;
  END
  ELSE
    PuissRapide := base * PuissRapide(base, exp - 1);
END;

Complexité : O(log exp) au lieu de O(exp). Pour 2^1000, environ 10 appels au lieu de 1000.

3. Fibonacci : le contre-exemple

FUNCTION FiboNaive(n : integer) : integer;
BEGIN
  IF n < 2 THEN
    FiboNaive := n
  ELSE
    FiboNaive := FiboNaive(n - 1) + FiboNaive(n - 2);
END;

Problème : on recalcule les mêmes valeurs exponentiellement.

FiboNaive(5) :

• F(5) appelle F(4) et F(3)
• F(4) appelle F(3) et F(2)
• F(3) appelle F(2) et F(1)
• ...
• F(3) est appelé 2 fois, F(2) 3 fois, F(1) 5 fois...

Total : environ 2^n appels. Pour n = 40, plusieurs secondes.

Solution : version itérative (vue au module 5) ou mémoïsation (stocker les valeurs déjà calculées).

4. Comparaison itératif ↔ récursif

5. Exercices

FUNCTION Inverser(ch : string) : string;
BEGIN
  IF Length(ch) <= 1 THEN
    Inverser := ch
  ELSE
    Inverser := Inverser(Copy(ch, 2, Length(ch) - 1)) + ch[1];
END;

FUNCTION SommeChiffres(n : integer) : integer;
BEGIN
  IF n = 0 THEN
    SommeChiffres := 0
  ELSE
    SommeChiffres := (n MOD 10) + SommeChiffres(n DIV 10);
END;

FUNCTION PGCD(a, b : integer) : integer;
BEGIN
  IF b = 0 THEN
    PGCD := a
  ELSE
    PGCD := PGCD(b, a MOD b);
END;

6. Erreurs fréquentes au bac

• Récursion infinie : argument qui ne décroît pas.
• Cas de base manquant ou jamais atteint.
• Utiliser Fibonacci récursif naïf en croyant que c'est rapide.
• Confondre Copy(ch, 2, n - 1) (n − 1 caractères à partir du 2ème) avec Copy(ch, 2, n).

7. Quiz