Cours sur la récursivité

Pour continuer à expliquer la récursivité dans ce livre, nous allons commencer par un exemple très simple:
- l'inversion d'une chaîne de caractères.

Soit une chaîne de caractères; supposons qu'on veuille faire aussi bien la fonction que la procédure qui nous renvoient l'inverse de cette chaîne; la fonction admet donc un paramètre qui est la chaîne initiale (transmise par valeur), et la procédure un paramètre qui est une variable de type "string" (transmis par adresse, c'est à dire en utilisant le mot "var" devant, qui indique que toutes les modifications du paramètre à un niveau quelconque de la procédure récursive se répercuteront sur le paramètre initial).

De manière itérative, cette fonction et cette procédure se font très facilement :on parcourt la chaîne d'un bout à l'autre et on accumule les caractères un par un dans une chaîne auxiliaire en prenant soin de mettre chaque nouveau caractère en tête de la chaîne auxiliaire. Voici cette première solution :

function inverse(st: string): string;
var aux: string;
  i: integer;
begin
  aux := '';
  for i := 1 to length(st) do
    aux := st[i] + aux;
  inverse := aux;
end;
 
procedure inverse(var st: string);
var aux: string;
  i: integer;
begin
  aux := '';
  for i := 1 to length(st) do
    aux := st[i] + aux;
  st := aux;
end;

Voici une autre solution, qui consiste à lire les caractères de la chaîne passée en paramètre en sens inverse et de les accumuler dans une variable auxiliaire :

function inverse(st: string): string;
var aux: string;
  i: integer;
begin
  aux := '';
  for i := length(st) downto 1 do
    aux := aux + st[i];
  inverse := aux;
end;
 
procedure inverse(var st: string);
var aux: string;
  i: integer;
begin
  aux := '';
  for i := length(st) downto 1 do
    aux := aux + st[i];
  st := aux;
end;

Transformons le principe de cette fonction et de cette procédure, de façon à les transformer en une fonction récursive et une procédure récursive; en appliquant le principe décrit à la fonction et la procédure ci-dessus, on voit qu'il faut toujours mettre en tête le dernier caractère; on en déduit donc l'algorithme:

- soit une chaîne 'abc'
- pour obtenir son inverse on met le dernier caractère en tête:
"c" et on le colle à l'inverse du reste qui est "ab"
- pour obtenir l'inverse de "ab" on met le dernier caractère en tête:
"b" et on le colle à l'inverse du reste qui est "a"
- pour obtenir l'inverse de "a" on met le dernier caractère en tête:
"a" et on le colle à l'inverse du reste qui est ""
- on a donc "cba"

function inverse(st: string): string;
var dernier_caractere: char;
  reste: string;
  inverse_du_reste: string;
begin
  if st = '' then
    inverse := '' {--- ceci est le point d'appui ---}
  else
  begin
    dernier_caractere := st[length(st)];
    reste := copy(st, 1, length(st) - 1);
    inverse_du_reste := inverse(reste);
    inverse := dernier_caractere + inverse_du_reste;
  end;
end;
 
procedure inverse(var st: string);
var dernier_caractere: char;
  reste: string;
begin
  if st = '' then st := '' //--- ceci est le point d'appui, inutile ici
  else //--- on aurait pu traduire cela par "if st<>'' then"
  begin
    dernier_caractere := st[length(st)];
    reste := copy(st, 1, length(st) - 1);
    inverse(reste); //--- on inverse le reste
    st := dernier_caractere + reste;
  end;
end;

Cette fonction et cette procédure sont convertibles en une fonction et une procédure sans variables internes, qui leur sont identiques du point de vue du résultat :

function inverse(st: string): string;
begin
  if st = '' then inverse := ''
  else inverse := st[length(st)] + inverse(copy(st, 1, length(st) - 1));
end;
 
procedure inverse(var st: string);
var c: char;
begin
  if st <> '' then
  begin
    c := st[length(st)];
    delete(st, length(st), 1);
    inverse(st);
    st := c + st;
  end;
end;

Pour obtenir l'inverse d'une chaîne avec cette procédure on fait tout simplement l'appel "inverse(s);", mais à condition que la chaîne soit déclarée comme une variable de type string, à cause du mot "var"; donc l'appel à cette procédure avec "inverse('abc');" ne fonctionnera pas.

Code des exemples : chap_II_1.zip Miroir 1 , chap_II_1.zip Miroir 2

Nous allons réaliser maintenant un programme permettant d'évaluer un nombre romain, mais auparavant on va introduire les chiffres romains:

• M = 1000
• D = 500
• C = 100
• L = 50
• X = 10
• V = 5
• I = 1

On constate que les nombres s'arrêtaient au milliers; cela montre le progrès des mathématiques depuis le temps des romains.

• 1 s'écrit I.
• 2 s'écrit II.
• 3 s'écrit III.
• 4 s'écrit IV.
• 5 s'écrit V.
• 6 s'écrit VI.
• 7 s'écrit VII.
• 8 s'écrit VIII.
• 9 s'écrit IX.
• 10 s'écrit X.

Tous les nombres finissant par 1,2 ou 3 se terminent dans l'écriture romaine par I,II ou III. Idem pour 6,7 ou 8.

Ceci est valable aussi bien pour les unités, comme on vient de le voir que pour les dizaines et les centaines; ainsi 30 s'écrit XXX, 300 s'écrit CCC.

Tous les nombres finissant par 4, se terminent dans l'écriture romaine par IV.

Tous les nombres finissant par 9, se terminent dans l'écriture romaine par IX. Ainsi 49 se termine par IX, et il s'écrit XLIX.

Identiquement, les nombres finissant par 90 se terminent dans l'écriture domaine par XC.

• 15 s'écrit XV.
• 47 s'écrit XLVII.
• 97 s'écrit XCVII.
• 14 s'écrit XIV.
• 149 s'écrit CXLIX (et non CIL, comme on pourrait le penser) On constate ici la décomposition 100+40+9 = C + XL + IX
• 1490 s'écrit MCDXC = 1000 + 400 + 90 = M + CD + XC
• 1900 s'écrit MCM = 1000+900 = M + CM.
• 1990 s'écrit MCMXC (et non MXM, comme on pourrait le penser) 1000+900+90 = M + CM + XC
• 1999 = MCMXCIX

Observations

Soit deux chiffres romains. Si le premier chiffre a une valeur inférieure au deuxième, alors on le soustrait de la valeur de tout le reste, sinon on l'additionne à la valeur de tout le reste.

En effet, étudions cela sur un exemple :
MCMXCIX.
|On est sur le premier M.
|Son successeur est C, il est plus petit, donc notre résultat final sera la 
|valeur de M (1000) plus la valeur du reste (CMXCIX).
|  La valeur du reste est la suivante :
|  C est plus petit que M (une soustraction aura lieu) donc la valeur de 
|  CMXCIX est égale à la valeur de MXCIX moins la valeur de C
|  |   La valeur de MXCIX est la suivante :
|  |   |M est plus grande que X donc on a 1000+valeur(XCIX).
|  |   |   La valeur de XCIX est égale à la valeur de CIX moins la valeur de X 
|  |   |   |car le premier X est plus petit que son successeur.
|  |   |   |   La valeur de CIX est égale à 100 + valeur(IX) car C est plus
|  |   |   |   |grand que I.
|  |   |   |   |    La valeur de IX est égale à la valeur de X moins la valeur    
|  |   |   |   |    de I, soit 10-1 = 9.
|  |   |   |   CIX = C + 9 = 109
|  |   |   XCIX = CIX - X = 109 - 10 = 99
|  |   MXCIX = M + XCIX = 1000 + 99 = 1099
|  CMXCIX = MXCIX - C = 1099 - 100 = 999
MCMXCIX = 1000 + 999 = 1999

On voit la forme de l'algorithme général:

Soit un nombre romain. Si le premier chiffre de ce nombre a une valeur inférieure au deuxième, alors on le soustrait de la valeur de tout le reste, sinon on l'additionne à la valeur de tout le reste.

Si le nombre romain a un seul chiffre, alors on prend simplement la correspondance (M=1000, D = 500,...).

Appelons "Eval" la fonction d'évaluation d'un nombre romain.

Son point d'appui est "Eval(r)= valeur(r)" si r est un caractère romain.

Le cas général est le suivant :
si la valeur du premier chiffre romain est plus grande que la valeur du deuxième, alors "Eval(r)=valeur(premier chiffre)+Eval(reste)"
si la valeur du premier chiffre romain est plus petite que la valeur du deuxième, alors "Eval(r)=Eval(reste)-valeur(premier chiffre)"

On constate qu'avec l'algorithme ci-dessus, le nombre MIM (qui pourtant n'existe pas chez les romains) est évalué à 1999. Le programme décrit ci-dessus n'effectue pas un test d'exactitude de la chaîne passée en paramètre pour être évaluée, il se contente seulement de l'évaluer.

function valeur(c: char): integer;
begin
  case c of
    'M': valeur := 1000;
    'D': valeur := 500;
    'C': valeur := 100;
    'L': valeur := 50;
    'X': valeur := 10;
    'V': valeur := 5;
    'I': valeur := 1;
  end;
end;
 
function eval(s: string): integer;
var n1: integer;
begin
  if length(s) = 1 then
    eval := valeur(s[1])
  else
  begin
    n1 := valeur(s[1]);
    if n1 < valeur(s[2]) then n1 := -n1;
    eval := n1 + eval(copy(s, 2, length(s) - 1));
  end;
end;

Code des exemples : chap_II_2.zip Miroir 1 , chap_II_2.zip Miroir 2

On appelle "palindrome" un mot ou une phrase qui se lit de la même façon à l'endroit comme à l'envers, sans tenir compte des espaces.

exemple : le mot "ABCBA" est un palindrome.

La phrase "ESOPE RESTE ET SE REPOSE" (sans tenir compte des espaces on obtient le mot "ESOPERESTEETSEREPOSE") se lit de façon identique de la gauche vers la droite ou de la droite vers la gauche.

L'algorithme qui teste si un mot est un palindrome est extrêmement simple:
- un mot de longueur 0 (le mot vide, ou en programmation, la variable string '') est un palindrome
- un mot de longueur 1 (donc une lettre) est un palindrome
- un mot est un palindrome si sa première lettre est identique à sa dernière et si son intérieur (le sous-mot commençant à la deuxième position et finissant à l'avant dernière lettre: dans le cas de "ABCBA" le sous-mot est "BCB") est un palindrome.

On voit donc à cette dernière ligne l'apparition de la récursivité : "un mot est un palindrome si... et si son sous-mot est un palindrome".

Voici le programme qui teste si un mot est un palindrome:

function palindrome(s: string): boolean;
begin
  if length(s) < 2 then
    palindrome := true
  else
    if (s[1] = s[length(s)]) then
      palindrome := palindrome(copy(s, 2, length(s) - 2))
    else
      palindrome := false;
end;

Code des exemples : chap_II_3.zip Miroir 1 , chap_II_3.zip Miroir 2

Soit une chaîne de caractères du type "s:='5+3+4+7';";faisons le programme qui évalue cette chaîne de caractères.

Voyons l'algorithme de cette procédure :
- d'abord on sait que la valeur d'une chaîne vide est 0
- ensuite on sait évaluer un nombre seul avec la fonction "strToInt".
- on sait extraire une sous-chaîne avec la fonction "copy" et nous allons extraire des caractères jusqu'au premier signe "+"
- l'évaluation de la chaîne initiale est égale à la valeur du nombre extrait plus la valeur de la chaîne restante (appel récursif).

Voici le programme correspondant :

function eval(st: string): integer;
var a, i: integer;
begin
  if length(st) = 0 then
    eval := 0
  else
  begin
    i := 1;
    repeat inc(i)until (i > length(st)) or (st[i] = '+');
    a := strToInt(copy(st, 1, i - 1));
    delete(st, 1, i - 1);
    eval := a + eval(st)
  end;
end;

On appelle cette fonction de la façon suivante : b:=eval('+51+7+67+31');

Code des exemples : chap_II_4.zip Miroir 1 , chap_II_4.zip Miroir 2

Soit une chaîne de caractères du type "s:='5+3*4/2-5*3+4*7/2';";faisons le programme qui évalue cette chaîne de caractères.

La première chose à faire est la séparation des termes; on doit en effet extraire tous les termes qui sont séparés par des "+" et des "-".

Ensuite nous devons évaluer chacun des termes extraits, pour arriver à la fin à une somme (ou à une différence) de termes.

Pour commencer, on suppose qu'on doit évaluer une somme (ou une différence) de termes. Pour cela, nous reprenons le programme fait précédemment, et nous l'enrichissons, de façon à ce qu'il puisse évaluer aussi les différences.

function eval(st: string): integer;
var a, i: integer;
begin
  if length(st) = 0 then
    eval := 0
  else
  begin
    i := 1;
    repeat inc(i)until (i > length(st)) or (st[i] in ['+', '-']);
    a := strToInt(copy(st, 1, i - 1));
    delete(st, 1, i - 1);
    eval := a + eval(st)
  end;
end;

Maintenant, on doit créer la procédure qui évalue une expression formée uniquement de produits et quotients; ici, on ne peut pas appliquer la même méthode : pour les sommes, on évaluait le premier terme auquel on ajoutait le résultat du reste.

Mais avec les produits et les quotients, c'est différent : en effet, si on veut évaluer le résultat de "12/4*6/2" on ne peut pas dire qu'il est égal à la valeur du premier terme "12" divisé par la valeur du reste "4*6/2". Le résultat est en réalité "((12/4)*6)/2" soit 9.

Il faut donc lire non pas de gauche à droite, mais de droite à gauche.
Ainsi le résultat de "12/4*6/2" est égal au résultat de "12/4*6" divisé par 2.
-Le résultat de "12/4*6" est égal au résultat de "12/4" multiplié par 6
--Le résultat de "12/4" est égal au résultat de "12" divisé par 4.
--On peut évaluer cette expression, soit 3.
-On a, en remontant dans les appels récursifs, 3*6=18.
On a, en remontant encore une fois dans les appels récursifs, 18/2=9.

• - on lit une expression de la droite vers la gauche.
• - si on est sur un signe "*" alors :
• • - on extrait le dernier nombre de la chaîne
  • - on évalue la chaîne restante
  • - le résultat est égal à l'évaluation de la chaîne restante (appel récursif) multipliée par le dernier nombre
• - si on est sur un signe "/" alors :
• • - on extrait le dernier nombre de la chaîne
  • - on évalue la chaîne restante
  • - le résultat est égal à l'évaluation de la chaîne restante (appel récursif) divisée par le dernier nombre
• - si on est au début de la chaîne (aucune multiplication, ni division) alors :
• • - le résultat est égal à l'évaluation du nombre.

Voici le programme qui évalue une expression mathématique contenant des nombres entiers et les 4 opérations mathématiques. Ce programme fonctionne avec des nombres entiers. Ainsi, quand vous faites une division, si elle ne tombe pas juste, le résultat est arrondi, grâce à la fonction "div". Mais la transformation en réels est très facile.

function eval0(st: string): integer;
var a, i: integer;
  signe: char;
begin
  i := length(st);
  repeat dec(i)until (i = 0) or (st[i] in ['*', '/']);
  a := strToInt(copy(st, i + 1, length(st) - i));
  if i > 0 then signe := st[i] else signe := #0;
  delete(st, i, length(st) - 1 + i);
  if signe = '*' then eval0 := eval0(st) * a else
    if signe = '/' then eval0 := eval0(st) div a else
      eval0 := a;
end;
 
function eval(st: string): integer;
var a, i: integer;
begin
  if length(st) = 0 then
    eval := 0
  else
  begin
    i := 1;
    repeat inc(i)until (i > length(st)) or (st[i] in ['+', '-']);
    a := eval0(copy(st, 1, i - 1));
    delete(st, 1, i - 1);
    eval := a + eval(st)
  end;
end;

Code des exemples : chap_II_5.zip Miroir 1 , chap_II_5.zip Miroir 2

Supposons qu'on veuille faire un programme qui affiche les combinaisons d'une chaîne de caractères; par exemple les anagrammes des lettres de "abc" sont "abc, acb, bac, bca, cab, cba".

Pour réaliser ce programme nous allons commencer par des petites chaînes, et nous allons d'abord le faire de manière itérative.

Pour "a", toutes les combinaisons sont : "a".
Pour "ab", toutes les combinaisons sont : "ab,ba".

On remarque que ces combinaisons ne sont en fait qu'une rotation de la chaîne initiale vers la gauche, et ceci 2 fois de suite.

On peut donc en déduire l'algorithme général, qui ne sera constitué que de rotations successives vers la gauche.

Pour "abc", toutes les combinaisons sont :
   première rotation  : "bca" suivi d'une rotation de "ca" donc "bac"
                              suivi de 2 rotations de "ca" donc "bca"
   deuxième rotation  : "cab" suivi d'une rotation de "ab" donc "cba"
                              suivi de 2 rotations de "ca" donc "cab"
   troisième rotation : "abc" suivi d'une rotation de "bc" donc "acb"
                              suivi de 2 rotations de "bc" donc "abc"

Nous allons écrire la procédure qui affiche les combinaisons des lettres d'une chaîne de 3 caractères.

procedure combinaison(st: string);
var i1, i2, i3: integer;
  tete1, tete2, reste1, reste2: string;
begin
  for i1 := 1 to 3 do
  begin
    tete1 := st[1];
    reste1 := copy(st, 2, length(st) - 1);
    st := reste1;
    for i2 := 1 to 2 do
    begin
      tete2 := st[1];
      reste2 := copy(st, 2, length(st) - 1);
      st := reste2;
      for i3 := 1 to 1 do
        memo1.lines.add(tete1 + tete2 + st); { on affiche les têtes successives }
      st := reste2 + tete2; { ici on fait la rotation }
    end;
    st := reste1 + tete1; { ici on fait la rotation }
  end;
end;

Nous allons transformer maintenant cette procédure itérative en une procédure récursive. On obtient la procédure suivante, qui est appelée avec l'instruction "combinaison('abc','');" :

procedure combinaison1(st, tete: string);
var i: integer;
  tete_local, reste_local: string;
begin
  if length(st) = 1 then memo1.lines.add(tete + st)
  else
    for i := 1 to length(st) do
    begin
      tete_local := st[1];
      reste_local := copy(st, 2, length(st) - 1);
      combinaison1(reste_local, tete + tete_local);
      st := reste_local + tete_local;
    end;
end;

Maintenant on peut supprimer les variables locales qui sont "tete_local" et "reste_local" et on obtient :

procedure combinaison2(st, tete: string);
var i: integer;
begin
  if length(st) = 1 then memo1.lines.add(tete + st)
  else
    for i := 1 to length(st) do
    begin
      combinaison1(copy(st, 2, length(st) - 1), tete + st[1]);
      st := copy(st, 2, length(st) - 1) + st[1];
    end;
end;

Une autre solution à ce problème, et qui appartient à mon ancien professeur d'informatique de lycée, est la suivante :

on prend un mot et on permute sa première lettre avec chacune des autres lettres. Ensuite pour chacun des nouveaux mots obtenus, on ne touche pas à la première lettre et à partir de la deuxième lettre on refait les permutations entre la deuxième lettre et toutes les autres lettres jusqu'à la fin; ensuite pour chacun des nouveaux mots obtenus, on ne touche pas à la deuxième lettre et à partir de la troisième lettre on refait les permutations entre la troisième lettre et toutes les autres lettres jusqu'à la fin; on voit donc la récursivité :

procedure combinaisons;
var ch: string;
  l: byte;
 
  procedure EchangeCar(var ch: string; i, j: byte);
  var car: char;
  begin
    if i <> j then
    begin
      car := ch[i];
      ch[i] := ch[j];
      ch[j] := car;
    end
  end;
 
  procedure anagram(ch: string; i: byte);
  var j: byte;
  begin
    if i = l then memo1.lines.add(ch)
    else
      for j := i to l do
      begin
        EchangeCar(ch, i, j);
        Anagram(ch, i + 1);
        EchangeCar(ch, i, j);
      end;
  end;
 
begin
  ch := 'abc'; l := length(ch);
  anagram(ch, 1);
end;