L'inversion d'une chaîne de caractères

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.

Télécharger le code source Delphi