Récurrence d'ordre 1

Avant de commencer

Une suite mathématique comme U(n) = U(n-1) + 3 avec U(0) = 2 se calcule terme par terme. Comment traduire cela en algorithme ?

1. Définition

Exemple : U(n) = 2 × U(n−1) + 1 avec U(0) = 0.

Termes successifs : 0, 1, 3, 7, 15, 31, …

2. Algorithme itératif

L'idée : maintenir une variable qui contient le terme courant, puis appliquer la relation à chaque tour.

DEF FN U(n : entier) : entier
  res ← 0           { U(0) }
  Pour i de 1 à n Faire
    res ← 2 * res + 1
  FinPour
  U ← res
Fin U

DEF FN U(n : entier) : entier
  res ← 0           { U(0) }
  Pour i de 1 à n Faire
    res ← 2 * res + 1
  FinPour
  U ← res
Fin U

FUNCTION U(n : integer) : integer;
VAR
  i, res : integer;
BEGIN
  res := 0;
  FOR i := 1 TO n DO
    res := 2 * res + 1;
  U := res;
END;

3. Trace d'exécution

Pour U(n) = 2 × U(n−1) + 1 avec U(0) = 0, calcul de U(4) :

4. Exemples classiques

Suite arithmétique

U(n) = U(n−1) + r avec U(0) = a.

FUNCTION Arith(n : integer; a, r : integer) : integer;
VAR i, res : integer;
BEGIN
  res := a;
  FOR i := 1 TO n DO
    res := res + r;
  Arith := res;
END;

Suite géométrique

U(n) = U(n−1) × q avec U(0) = a.

FUNCTION Geo(n : integer; a, q : integer) : integer;
VAR i, res : integer;
BEGIN
  res := a;
  FOR i := 1 TO n DO
    res := res * q;
  Geo := res;
END;

5. Exercices

FUNCTION SommeJusqu(n : integer) : integer;
VAR
  i, res : integer;
BEGIN
  res := 0;
  FOR i := 1 TO n DO
    res := res + i;
  SommeJusqu := res;
END;

BEGIN
  Writeln(SommeJusqu(10));   { 55 }
  Writeln(10 * 11 DIV 2);    { 55 }
END.

FUNCTION Fibo(n : integer) : integer;
VAR
  i, a, b, c : integer;
BEGIN
  IF n < 2 THEN
    Fibo := n
  ELSE
  BEGIN
    a := 0; b := 1;
    FOR i := 2 TO n DO
    BEGIN
      c := a + b;
      a := b;
      b := c;
    END;
    Fibo := b;
  END;
END;

6. Erreurs fréquentes au bac

• Oublier l'initialisation res ← U(0) avant la boucle.
• Faire Pour i de 0 à n au lieu de 1 à n (cela ferait un tour de trop : U(n+1)).
• Confondre U(n−1) (ancien) et U(n) (nouveau) — écraser l'ancien avant de s'en servir.

7. Quiz