[MI] L'affichage d'une liste linéaire chaînée en utilisant la récursivité

La récursivité est une approche très pratique et très puissante pour concevoir des algorithmes. Dans cet article, nous allons prendre le cas de l'affichage d'une liste linéaire chaînée : la récursivité peut être utilisée pour afficher une liste dans un sens ou l'autre.

La récursivité devient possible (et facile) à implémenter dès que nous avons une définition du problème "en fonction de lui même" pour un élément plus petit, ou plus précisiment, en direction vers une condition qui arrête l'appel récursif (condition d'arrêt) (pour plus de détails : page du professeur D. E. Zegour sur la récursivité).
Vu cette caractéristique de la récursivité, il est facile de concevoir des algorithmes récursifs pour les listes linéaires chaînées. En effet, une liste est un ensemble de nœuds identiques dont on se rappelle du premier comme étant "la tête de la liste". Mais, tout nœud de la liste peut être considéré comme la tête d'une liste plus petit; les éléments qui précèdent ce nœud ne deviennent plus visible comme s'il s'agit d'une liste plus petite. En partant de cette idée, il est facile de concevoir un algorithme pour afficher une liste linéaire chaînée : il suffit de traîter le nœud en cours et de faire la même chose pour le reste de la liste, c'est-à-dire, la liste qui a le nœud suivant comme tête. Le traitement dans ce cas est un simple affichage.

Procedure AfficherRec1(L : Liste);
Begin
  If (L <> Nil) Then
  Begin
    WriteLn(L^.val);
    AfficherRec1(L^.suiv);
  End;
End;

Il est possible de faire un affichage dans le sens inverse : en commençant par le dernier nœud en direction du premier nœud. L'idée est de laisser le traitement du nœud actuel et de la faire après le traitement du reste de la liste (de la liste qui a le n&ud suivant comme tête). Ainsi, il suffit d'inverser deux instructions dans l'exemple précédent pour avoir le bon résultat.

Procedure AfficherRec2(L : Liste);
Begin
  If (L <> Nil) Then
  Begin
    AfficherRec2(L^.suiv);
    WriteLn(L^.val);
  End;
End;

Pour pouvoir tester ces deux procédures, il suffit de les mettre dans un programm complet qui définit le type Liste ainsi qu'un méthode de lecture. Dans l'exemple suivant, la procédure de lecture fait une insertion à la fin. Le programme principale permet de faire plusieurs lecture qui se terminent par un zéro (0) qui ne sera pas inséré dans la liste). Ensuite il appelle les deux foncontions d'affichage.

Program InsererQueue_Affichage;

Type

  Liste = ^Cellule;
  Cellule = Record
          val : Integer;
          suiv : Liste;
  end;

Procedure InsererQueue(var L : Liste; valeur : Integer);
Var
  P, Q : Liste;
Begin
  New(P);
  P^.val := valeur;
  P^.suiv := Nil;

  If (L = Nil) Then
  Begin
    L := P
  End
  Else
  Begin
     Q := L;
     While (Q^.suiv <> Nil) Do
     Begin
        Q := Q^.suiv;
     End;
     Q^.suiv := P;
  End;
End;

Procedure AfficherRec1(L : Liste);
Begin
  If (L <> Nil) Then
  Begin
    WriteLn(L^.val);
    AfficherRec1(L^.suiv);
  End;
End;

Procedure AfficherRec2(L : Liste);
Begin
  If (L <> Nil) Then
  Begin
    AfficherRec2(L^.suiv);
    WriteLn(L^.val);
  End;
End;

Var
  valeur : Integer;
  L : Liste;

Begin

  WriteLn('Faites entrer des nombres, 0 pour terminer');
  ReadLn(valeur);
  While (valeur <> 0) Do
  Begin
     InsererQueue(L, valeur);
     ReadLn(valeur);
  End;

  WriteLn('Affichage dans le même sens que la lecture');
  AfficherRec1(L);

  WriteLn('Affichage dans le même sens que la lecture');
  AfficherRec2(L);

End.

Le résultat de l'exécution de ce programme en insérant les valeurs de 1 à 9 (on termine la lecture par un zéro - 0) est le suivant :

Pour télécharger les codes ci-dessus, c'est par ici.