Cours sur la récursivité
Date de publication : avril 2005 , Date de mise à jour : octobre 2009
VI. Récursivité croisée
VI-A. Suites à récurrence double
VI-B. Tri bulle boustrophédon
VI. Récursivité croisée
VI-A. Suites à récurrence double
Nous sommes parfois amenés à travailler sur des suites qui dépendent d'autres suites. Ainsi, dans l'exemple suivant, la suite u dépend de la suite v, qui elle dépend de u. Nous pouvons facilement réaliser le programme permettant de calculer les n-ièmes termes de ces deux suites, mais d'un point de vue algorithmique, cela nous amène à programmer une récursivité croisée; en effet, la fonction "u" appelle la fonction "v", cette dernière appelant "u".
Voici la définition des deux suites, suivie du programme;
u(0)=1, v(0)=2 et, pour tout entier naturel n :
u(n+1)=3u(n)+2v(n)
v(n+1)=2u(n)+3v(n)
Remarques :
- la suite u-v est constante égale à 1.
- Comme la fonction "v" est définie après "u", cela nous amène à utiliser le mot "forward".
function v(n: integer): int64; forward;
function u(n: integer): int64;
begin
if n = 0 then result := 1
else result := 3 * u(n - 1) + 2 * v(n - 1);
end;
function v;
begin
if n = 0 then result := 2
else result := 2 * u(n - 1) + 3 * v(n - 1);
end;
procedure TForm1.Button1Click(Sender: TObject);
var i: integer;
begin
Screen.Cursor := crHourGlass;
Memo1.Clear;
for i := 0 to SpinEdit1.Value - 1 do
begin
Memo1.Lines.Add('u(' + IntToStr(i) + ') = ' + IntToStr(u(i)));
Memo1.Lines.Add('v(' + IntToStr(i) + ') = ' + IntToStr(v(i)));
Memo1.Lines.Add(' ');
end;
Screen.Cursor := crDefault;
end;
|
VI-B. Tri bulle boustrophédon
Nous allons voir dans ce chapitre l'utilisation du tri bulle boustrophédon pour trier un tableau d'entiers. Mais auparavant nous allons expliquer le tri à bulle (ou tri bulle) simple. Soit un tableau d'entiers non trié. Prenons par exemple :
9, 2, 15, 7, 3, 1, 6, 13, 17, 4
Le tri bulle consiste à parcourir le tableau de gauche à droite et chaque fois qu'on est sur un nombre, si son voisin droit a une valeur inférieure, alors on permute ces deux nombres. Une fois qu'on est au bout, si une permutation a eu lieu alors on recommence depuis le début
Voici l'exemple: On est sur le premier nombre. Son voisin est plus petit que lui donc on les permute pour obtenir:
2, 9, 15, 7, 3, 1, 6, 13, 17, 4
Ensuite on avance pour tomber sur le deuxième nombre. Pas de permutation car 9<15. On avance. On est sur le troisième nombre. Comme 7<15 alors on les permute et on obtient :
2, 9, 7, 15, 3, 1, 6, 13, 17, 4
On passe ensuite au quatrième nombre qui est ici 3 et qui est plus petit que son voisin droit, donc on les permute:
2, 9, 7, 15, 1, 3, 6, 13, 17, 4
On continue, et on trouve une permutation à la dernière position :
2, 9, 7, 15, 1, 3, 6, 13, 4, 17
On est arrivé à la fin, mais des permutations ont eu lieu, donc on recommence depuis le début; voici les étapes successives:
position 1 : 2, 9, 7, 15, 1, 3, 6, 13, 4, 17 --> pas de changement
position 2 : 2, 7, 9, 15, 1,3, 6, 13, 4, 17
position 3 : 2, 7, 9, 15, 1,3, 6, 13, 4, 17 --> pas de changement
position 4 : 2, 7, 9, 1, 15, 3, 6, 13, 4, 17
position 5 : 2, 7, 9, 1, 3, 15, 6, 13, 4, 17
position 6 : 2, 7, 9, 1, 3, 6, 15, 13, 4, 17
position 7 : 2, 7, 9, 1, 3, 6, 13, 15, 4, 17
position 8 : 2, 7, 9, 1, 3, 6, 13, 4, 15, 17
position 9 : 2, 7, 9, 1, 3, 6, 13, 4, 15, 17 --> pas de changement
|
Mais on a eu des permutations, donc on recommence
position 1 : 2, 7, 9, 1, 3, 6, 13, 4, 15, 17 --> pas de changement
position 2 : 2, 7, 9, 1, 3, 6, 13, 4, 15, 17 --> pas de changement
position 3 : 2, 7, 1, 9, 3, 6, 13, 4, 15, 17
position 4 : 2, 7, 1, 3, 9, 6, 13, 4, 15, 17
position 5 : 2, 7, 1, 3, 6, 9, 13, 4, 15, 17
position 6 : 2, 7, 1, 3, 6, 9, 13, 4, 15, 17 --> pas de changement
position 7 : 2, 7, 1, 3, 6, 9, 4, 13, 15, 17
position 8 : 2, 7, 1, 3, 6, 9, 4, 13, 15, 17 --> pas de changement
position 9 : 2, 7, 1, 3, 6, 9, 4, 13, 15, 17 --> pas de changement
|
A cette étape nous avons eu 4 permutations, donc on recommence:
position 1 : 2, 7, 1, 3, 6, 9, 4, 13, 15, 17 --> pas de changement
position 2 : 2, 1, 7, 3, 6, 9, 4, 13, 15, 17
position 3 : 2, 1, 3, 7, 6, 9, 4, 13, 15, 17
position 4 : 2, 1, 3, 6, 7, 9, 4, 13, 15, 17
position 5 : 2, 1, 3, 6, 7, 9, 4, 13, 15, 17 --> pas de changement
position 6 : 2, 1, 3, 6, 7, 4, 9, 13, 15, 17
position 7 : 2, 1, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
position 8 : 2, 1, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
position 9 : 2, 1, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
|
A cette étape nous avons eu 4 permutations, donc on recommence:
position 1 : 1, 2, 3, 6, 7, 4, 9, 13, 15, 17
position 2 : 1, 2, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
position 3 : 1, 2, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
position 4 : 1, 2, 3, 6, 7, 4, 9, 13, 15, 17 --> pas de changement
position 5 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17
position 6 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
position 7 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
position 8 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
position 9 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
|
A cette étape nous avons eu 2 permutations, donc on recommence:
position 1 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
position 1 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
position 1 : 1, 2, 3, 6, 4, 7, 9, 13, 15, 17 --> pas de changement
position 1 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17
position 5 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17 --> pas de changement
position 6 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17 --> pas de changement
position 7 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17 --> pas de changement
position 8 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17 --> pas de changement
position 9 : 1, 2, 3, 4, 6, 7, 9, 13, 15, 17 --> pas de changement
|
A cette étape nous avons eu une permutation, donc on recommence, et quand on arrive à la fin aucune permutation n'a été effectuée, donc le tableau est trié et le programme s'arrête. Le tri a été réalisé en 7 boucles.
On constate que la première amélioration possible est de limiter le nombre d'avancées du curseur. En effet, chaque boucle sur les éléments du tableau a pour effet de ramener le plus grand nombre rencontré à la fin du tableau (ou à sa position correcte). Sachant donc qu'après le premier parcours le nombre 17 se trouve à la fin, il ne sera plus nécessaire à l'étape suivante d'aller jusqu'à 17, il suffira de s'arrêter à son prédécesseur. Ainsi à chaque étape le nombre de paires à comparer diminue.
Mais on peut encore améliorer cet algorithme : c'est le tri bulle boustrophedon.
Le parcours du tableau se fait alternativement de gauche à droite et de droite à gauche.
Quand on va de gauche à droite (cas ci-dessus), le plus grand nombre se trouve à l'extrémité droite du tableau (et la nouvelle extrémité devient don prédécesseur).
Quand on va de droite à gauche, le plus petit nombre se trouve à l'extrémité gauche du tableau et la nouvelle extrémité gauche devient son successeur. Quand les deux extrémités se rejoignent, alors le tableau est trié et le programme s'arrête. On peut aussi affirmer que si pendant un parcours (de gauche à droite ou inversement) aucune permutation n'a lieu, alors le tableau est trié.
Pour réaliser le tri bulle boustrophedon, nous allons réaliser deux procédures qui s'appellent l'une l'autre, d'où le nom de récursivité croisée.
Dans ce programme, nous allons utiliser une procédure de permutation de deux nombres. Voici un moyen d'échanger la valeur de deux nombres sans utiliser de variable auxiliaire :
soit deux variables a et b; a=3, b=5. On veut avoir à la fin a=5 et b=3.
On fait donc les opérations suivantes :
a := a + b = 8
b := a - b = 8 - 5 = 3
a := a - b = 8 - 3 = 5
Et comme on peut le constater, les deux valeurs sont échangées.
Nous allons voir les structures de données utilisées : le type "tab" qui est un tableau d'entiers, un tableau de type "tab" qui est un tableau de constantes (et que nous allons copier dans la variable "t2" pour pouvoir effectuer le tri dessus).
Comme on a une récursivité croisée, et comme nous n'avons pas utilisé la programmation orientée objet, il faut déclarer l'une des deux procédures en "forward".
type tab = array[1..10] of integer;
const t1: tab = (9, 2, 15, 7, 3, 1, 6, 13, 17, 4);
var t2: tab;
procedure arriere(var t: tab; limg, limd: integer); forward;
procedure affiche(t: tab);
var i: integer;
s: string;
begin
s := '';
for i := 1 to 10 do
s := s + inttostr(t[i]) + '; ';
form1.memo1.lines.add(s);
end;
procedure echange(var a, b: integer);
begin
a := a + b;
b := a - b;
a := a - b;
end;
procedure avant(var t: tab; limg, limd: integer);
var permute: boolean;
i: integer;
begin
permute := false;
for i := limg to limd - 1 do
if t[i] > t[i + 1] then
begin
echange(t[i], t[i + 1]);
permute := true;
end;
if permute then
begin
affiche(t);
arriere(t, limg, limd - 1);
end;
end;
procedure arriere(var t: tab; limg, limd: integer);
var permute: boolean;
i: integer;
begin
permute := false;
for i := limd downto limg + 1 do
if t[i] < t[i - 1] then
begin
echange(t[i], t[i - 1]);
permute := true;
end;
if permute then
begin
affiche(t);
avant(t, limg + 1, limd);
end;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
move(t1, t2, sizeof(t1));
avant(t2, 1, 10);
end;
|
Copyright © 2005 Axel CHAMBILY et Pétrut CONSTANTINE.
Aucune reproduction, même partielle, ne peut être faite
de ce site ni 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.
