Cours sur la récursivité


précédentsommairesuivant

I. Boucles

I-A. Transformer une boucle en une procédure récursive

Soit la procédure suivante :

 
Sélectionnez

procedure compter;
var i: integer;
begin
  for i := 1 to 10 do
    memo1.lines.add(inttostr(i));
end;

Cette procédure peut être traduite en une procédure récursive, qui admet un paramètre; l'instruction qui l'appellera sera "compter(1);":

 
Sélectionnez

procedure compter(i: integer);
begin
  if i < 11 then
  begin
    memo1.lines.add(inttostr(i));
    compter(i + 1);
  end;
end;

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

I-B. Transformer deux boucles imbriquées en une procédure récursive

Supposons qu'on ait maintenant deux boucles imbriquées. Nous allons traduire progressivement cette procédure itérative en une procédure récursive avec deux paramètres :

 
Sélectionnez

procedure affiche;
var a, b: integer;
begin
  for a := 0 to 3 do
    for b := 0 to 9 do
      memo1.lines.add(inttostr(a * 10 + b));
end;

Pour supprimer les deux boucles, on commence par supprimer la première en suivant l'exemple ci-dessus;on obtient la procédure suivante que l'on appelle avec "affiche(0);" :

 
Sélectionnez

procedure affiche(a: integer);
var b: integer;
begin
  if a < 4 then
  begin
    for b := 0 to 9 do
      memo1.lines.add(inttostr(a * 10 + b));
    affiche(a + 1);
  end;
end;

Il ne nous reste plus qu'à supprimer la deuxième boucle; en sachant que lorsque "b=10" dans la procédure initiale, le programme revient à la boucle sur "a" et remet "b" à zéro, alors on a 2 appels récursifs :

  • - le premier dans le cas où "b" est inférieur à 10 et alors on appelle la procédure avec "a" inchangé et "b" incrémenté de 1
  • - le deuxième où "b=10" et alors on appelle la procédure avec "a" incrémenté de 1 et "b" initialisé à 0.

L'appel sera "affiche(0,0);".

 
Sélectionnez

procedure affiche(a, b: integer);
begin
  if a < 4 then
    if b < 10 then
    begin
      memo1.lines.add(inttostr(a * 10 + b));
      affiche(a, b + 1);
    end
    else
      affiche(a + 1, 0);
end;

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

I-C. Calculer la factorielle d'un entier

L'exemple ci-dessous est utilisé pour calculer la factorielle d'un nombre.

La factorielle d'un nombre "n" se note "n!" et représente le nombre de permutations de "n" objets.

On rappelle que la factorielle d'un nombre "n" est égale au produit de tous les nombres de 1 jusqu'à "n". Ainsi, "5!"="1*2*3*4*5"

La fonction itérative est donnée ci-dessous :

 
Sélectionnez

function fact(n: integer): integer;
var i, j: integer;
begin
  j := 1;
  for i := 1 to n do
    j := j * i;
  fact := j;
end;

En reprenant l'exemple de la transformation d'une boucle simple en une procédure récursive, on obtient pour "factorielle" la fonction récursive suivante :

 
Sélectionnez

function fact(n: integer): integer;
begin
  if n = 1 then fact := 1
  else fact := n * fact(n - 1)
end;

On constate, et c'est vrai en général, que les procédures récursives sont plus courtes que celles itératives.

I-D. Remplir un carré en diagonale

Supposons qu'on a un carré de 10x10 cases, et qu'on veut noircir toutes ses cases; le remplissage ne s'effectuera pas en ligne ou en colonne mais en diagonale, de gauche à droite et du bas vers le haut.

Pour cela, si à un instant t on se trouve à la case de coordonnées (x,y), alors la prochaine case à noircir sera la case de coordonnées (x+1,y-1).

Il faut prendre soin de tester les effets de bord (ne pas sortir du carré à force de décrémenter x ou d'incrémenter y).

On en déduit donc que le point d'arrêt de la procédure est atteint quand les coordonnées x ou y se retrouvent en dehors du carré.

On sait ensuite que lorsqu'on aura atteint la première ligne (y=1), alors il faut redémarrer le remplissage à la première colonne.

 
Sélectionnez

procedure trace(x, y, x_droite, y_bas, total_posees: integer);
begin
  tab[x, y] := '$';
  afficher_tableau;
  if (x >= dim) and (y >= dim) then exit; // point d'arrêt
  if y = 1 then
  begin
    if x >= dim then inc(x_droite); // effet de bord
    x := x_droite;
    y := y_bas + 1;
    if y > dim then dec(y); // effet de bord
    y_bas := y;
    if total_posees < dim * dim then // carré rempli ?
      trace(x, y, x_droite, y_bas, total_posees + 1);
  end
  else
    if x >= dim then
    begin
      if y_bas = dim then inc(x_droite); // effet de bord
      x := x_droite; y := y_bas;
      if total_posees < dim * dim then // carré rempli ?
        trace(x, y, x_droite, y_bas, total_posees + 1);
    end
    else
      if total_posees < dim * dim then // carré rempli ?
        trace(x + 1, y - 1, x_droite, y_bas, total_posees + 1);
end;

On appelle cette procédure avec l'instruction suivante: "trace(1,1,1,1,1);".

I-E. Sources des exemples


précédentsommairesuivant

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Copyright © 2005 Axel CHAMBILY et Pétrut CONSTANTINE. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.