Transformer une boucle en une procédure récursive

Soit la procédure suivante :

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);":

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

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 :

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);" :

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);".

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;

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 :

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 :

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.

Télécharger le code source Delphi