CHAPITRE 11 : LA RECURSIVITE

Une fonction recursive s'appelle elle-meme. L'idee : resoudre un probleme en le ramenant a un probleme plus petit de meme nature.

1. Les deux elements indispensables

Le cas de base

C'est la condition qui arrete les appels. Sans lui, la fonction s'appelle indefiniment.

L'appel recursif

Chaque appel doit rapprocher du cas de base.

n  ──▶  n-1  ──▶  n-2  ──▶  ...  ──▶  0

2. La factorielle

0! = 1
n! = n x (n-1)!

Fonction Factorielle(n : entier) : entier;

Debut

    Si(n = 0) Alors
        Retourner(1);
    Sinon
        Retourner(n * Factorielle(n-1));
    FinSi

Fin

Le deroulement

F(4)
  ↓
4 x F(3)
  ↓
4 x 3 x F(2)
  ↓
4 x 3 x 2 x F(1)
  ↓
4 x 3 x 2 x 1 x F(0)
  ↓
4 x 3 x 2 x 1 x 1  =  24

3. La pile d'appels

Chaque appel est memorise dans une pile. Les resultats remontent ensuite dans l'ordre inverse.

Empilement        Depilement
F(4)                    24
F(3)                     6
F(2)                     2
F(1)                     1
F(0)                     1

Cette pile a une taille limitee : une recursivite trop profonde finit par la saturer.

4. La somme des N premiers entiers

S(0) = 0
S(n) = n + S(n-1)

Fonction Somme(n : entier) : entier;

Debut

    Si(n = 0) Alors
        Retourner(0);
    Sinon
        Retourner(n + Somme(n-1));
    FinSi

Fin

5. La suite de Fibonacci

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)

Fonction Fibonacci(n : entier) : entier;

Debut

    Si(n <= 1) Alors
        Retourner(n);
    Sinon
        Retourner(Fibonacci(n-1) + Fibonacci(n-2));
    FinSi

Fin

L'arbre des appels

           F4
        /      \
      F3        F2
    /   \      /   \
  F2    F1   F1    F0
 /  \
F1   F0

Observez : F2 est calcule deux fois, F1 trois fois. La version recursive de Fibonacci est donc tres peu efficace pour les grandes valeurs de n. C'est l'exemple classique d'une recursivite elegante mais couteuse.

6. Le PGCD d'Euclide

PGCD(a, b) = PGCD(b, a MOD b)   jusqu'a b = 0

Fonction PGCD(a, b : entier) : entier;

Debut

    Si(b = 0) Alors
        Retourner(a);
    Sinon
        Retourner(PGCD(b, a MOD b));
    FinSi

Fin

PGCD(18, 12)  ──▶  PGCD(12, 6)  ──▶  PGCD(6, 0)  ──▶  6

7. La puissance

Fonction Puissance(x, n : entier) : entier;

Debut

    Si(n = 0) Alors
        Retourner(1);
    Sinon
        Retourner(x * Puissance(x, n-1));
    FinSi

Fin

L'exponentiation rapide

Si n est pair, x^n = (x²)^(n/2) ; sinon x^n = x × x^(n-1). Cette methode reduit fortement le nombre de multiplications.

8. Recursivite ou iteration ?

La recursivite est adaptee quand le probleme est naturellement recursif et se decoupe facilement en sous-problemes identiques.

9. Les erreurs frequentes

• Oublier le cas de base → recursion infinie
• Le parametre ne se rapproche pas du cas de base. Ecrire Retourner(F(n+1)) fait grandir le probleme au lieu de le reduire.
• Oublier Retourner dans une branche
• Multiplier les appels inutiles, comme dans Fibonacci

A retenir

• Une fonction recursive s'appelle elle-meme
• Deux elements obligatoires : un cas de base et un appel recursif
• Chaque appel doit rapprocher du cas de base
• Les appels s'empilent, puis les resultats remontent
• Classiques : factorielle, somme, Fibonacci, PGCD, puissance

Bilan du cours

Vous disposez desormais de l'essentiel de l'algorithmique : structure d'un algorithme, variables et types, conditions, les trois boucles, tableaux et matrices, fonctions et procedures, enregistrements, et recursivite.

Le meilleur conseil pour la suite : traitez beaucoup d'exercices. L'algorithmique ne s'apprend pas en lisant, mais en cherchant, en se trompant, et en dressant des tableaux de trace quand un algorithme resiste.