CH 2 : La récursivité ~ Bac Info

Rappel du Cours : La récursivité

Introduction:

Les algorithmes récursifs et les fonctions récursives sont fondamentaux en informatique.Un algorithme est dit récursif s'il s'appelle lui-même.

Les premiers langages de programmation qui ont introduit la récursivité sont LISP et Algol 60 et maintenant tous les langages de programmation modernes proposent une implémentation de la récursivité.

On oppose généralement les algorithmes récursifs aux algorithmes dits impératifs ou itératifs
qui s'exécutent sans invoquer ou appeler explicitement l'algorithme lui-même.

Comment écrire un algorithme récursif:

- Exprimer le problème de "taille" n en fonction du même problème de taille (s) inférieure (s);

- Mettre une condition d'arrêt: ie lorsque le problème est de taille suffisamment petite
pour être résolu sans appel récursif. Attention: penser à tous les cas d'arrêts !!
(On peut constater sur les exemples que c'est le cas à chaque fois)

Un algorithme récursif est plus lent qu'un algorithme itératif car il y a la gestion
des appels de fonctions (empilement et dépilement du contexte).

Fonctions récursives:

La syntaxe la plus générale d'une fonction récursive est:

static <type_de_retour> <nomFct>(<args>){
            [déclaration de variables]
            [test d'arrêt]
            [suite d'instructions]
            [appel de <nomFct>(<args'>)]
            [suite d'instructions]
            return <résultat>;
}

Questions à se poser avant d'écrire une fonction récursive:

1. Quel paramètre caractérise la taille du problème?

[ Ce paramètre va constituer la variable d'induction.

2. Quelle est la taille init du problème pour laquelle la solution est triviale et quelle est cette solution?

[ La taille init va constituer la condition d'arrêt de la fonction récursive.

3. Si on connaît la solution du problème pour une taille donnée, quel calcul simple appliqué à cette solution permet de trouver la solution du problème pour une taille supérieure?

4. Comment faire varier la variable d'induction pour que celle-ci se rapproche de plus en plus de la valeur init?
Cela afin d'atteindre la condition d'arrêt en un nombre fini d'appels.

Une fois que l'on a les réponses à ces quatre questions, l'écriture de la fonction récursive devient très simple.

Fonctions récursives sur les listes:

Par définition, les listes sont des structures récursives. Une liste est :

- soit la liste vide '()

- soit composée d'un premier élément: le car et d'une liste: le cdr.

Cette nature récursive fait que la plupart des problèmes concernant des listes se résolvent par des fonctions récursives.

On aura souvent (mais ceci n'est pas systématique !) :

1. taille du problème: la longueur de la liste à traiter, et variable d'induction : la liste elle-même

2. condition d'arrêt : si la liste est vide

3. connaissant le résultat de la fonction sur le reste de la liste, on en déduit la solution pour la liste entière

4. on fait décroître la taille du problème en appelant récursivement la fonction sur le reste de la liste

Ex : Calcul de la longueur d'une liste L :

longueur :	Liste	$\longrightarrow$	Entier
	l	$\longmapsto$	$\left\{ \begin{array}{ll} 0 & \mbox{si } l \mbox{ est vide}\\ 1 + longueur(l') & \mbox{sinon, avec l=(x . l')} \end{array}\right.$

        (define longueur

           (lambda (L)

              (if (null? L)

                  (+ 1 (longueur (cdr L))))))

Ex : Renversement d'une liste: (a b c) -> (c b a)

1. variable d'induction : la liste

2. condition d'arrêt : liste vide
résultat : renversement d'une liste vide = liste vide

3. pour renverser une liste l, si on sait renverser son reste,
il suffit d'ajouter le premier élément à la fin du renversement du reste

4. on fait tendre le problème vers la liste vide en appelant récursivement la fonction sur le reste de l

renverse :	Liste	$\longrightarrow$	Liste
	l	$\longmapsto$	$\left\{ \begin{array}{ll} liste vide & \mbox{si } l \mbox{ est vide}\\ renverse(l').(x) & \mbox{sinon, avec l=(x . l')} \end{array}\right.$

        (define renverse

           (lambda (l)

              (if (null? l)

'()

                  (append (renverse (cdr l))

                          (list (car l))))))

Vérification minimum à faire lorsqu'on écrit une fonction récursive:

1. Vérifier qu'on a un critère d'arrêt et qu'on renvoie la bonne solution pour la taille minimale du problème.

2. Vérifier qu'on fait bien tendre le problème vers la solution triviale, i.e. qu'on atteindra bien le critère d'arrêt.

3. Vérifier la cohérence du nombre d'arguments et du type des expressions lors de l'appel récursif.

Applications:

Dans ce qui suit, nous allons utiliser le terme "procédure" pour désigner aussi bien une procédure qu'une fonction.

Une procédure récursive comporte un appel à elle-même,
alors qu'une procédure non récursive ne comporte que des appels à d'autres procédures.

Toute procédure récursive comporte une instruction (ou un bloc d'instructions)
nommée "point terminal" ou "point d'appui" ou "point d'arrêt",
qui indique que le reste des instructions ne doit plus être exécuté.

Exemple:

procédure récursive(paramètres);

// déclaration des variables locales

begin

if TEST_D'ARRET then

begin

instructions du point d'arrêt

end

else //----- exécution

begin

instructions;

recursive(paramètres changés); // appel récursif

instructions;

end;

end;

On constate, et il le faut, que les paramètres de l'appel récursif changent;
en effet, à chaque appel, l'ordinateur stocke dans la pile les variables locales;
le fait de ne rien changer dans les paramètres ferait que l'ordinateur effectuerait un appel infini à cette procédure, ce qui se traduirait en réalité par un débordement de pile, et d'arrêt de l'exécution de la procédure en cours.
Grâce à ces changements, tôt ou tard l'ordinateur rencontrera un ensemble de paramètres vérifiant le test d'arrêt, et donc à ce moment la procédure récursive aura atteint le "fond" (point terminal). Ensuite les paramètres ainsi que les variables locales sont désempilées au fur et à mesure qu'on remonte les niveaux.

La combinaison des lettres d'une chaîne de caractères:

Nous allons étudier en détail maintenant le mécanisme de la récursivité sur un exemple concret, la combinaison des lettres d'une chaîne de caractères (ou anagrammes). La réalisation de la procédure récursive faisant cela sera étudiée plus loin, nous allons décrire ici le mécanisme interne et le stockage des paramètres et des variables locales.

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;

Voici l'appel de cette procédure : combinaison('abc','');

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.

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

Pour continuer à expliquer la récursivité, 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.

Anagrammes:

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" suivie d'une rotation de "ca" donc "bac"

suivie de 2 rotations de "ca" donc "bca"

deuxième rotation : "cab" suivie d'une rotation de "ab" donc "cba"

suivie de 2 rotations de "ca" donc "cab"

troisième rotation : "abc" suivi d'une rotation de "bc" donc "acb"

suivie 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;

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;

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;

Une autre solution à ce problème 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;

begin

ch := 'abc'; l := length(ch);

anagram(ch, 1);

end;

Bac Info

mercredi 14 août 2013

CH 2 : La récursivité

0 commentaires:

Enregistrer un commentaire

Labels

Popular Posts