[MI] Quelques fonctions récursives sur les listes linéaires chaînées

Le raisonnement récursif est très adapté aux listes linéaires chaînées comme nous avons déjà mentionné (ici). La récursivité pour les liste peut être définie en précisant :

• Le traitement pour la liste vide : la liste vide est l'unique condition d'arrêt dans la majorité des cas, et même s'il y a une autre condition d'arrêt, la liste vide est aussi traitée.
• Le traitement pour la liste qui commence par le noeud (la cellule) suivant : appelé par "L^.suiv".

Cela revient, en quelque sorte, à la définition d'une suite mathématique de la forme :

Dans cet article, nous allons donner quelques fonctiones récursives pour faire des traitements communs sur les listes linéaires chaînées.

La longueur de la liste

La longueur d'une liste est une fonction fréquemment utilisée lorsqu'on veut traiter la liste dans une boucle de type "For" ou pour connaître est ce qu'on a pu récupérer toutes les données à partir d'un fichier. Cette fonction est facile à implémenter, soit sous forme itérative ou bien sous forme récursive. En effet, il suffit de se poser quelques questions :

• Quand est ce que je m'arrête ? Lorsque la liste est vide.
• Quelle est la taille (la longueur) de la liste vide ? Sa taille est égale à zéro (0).
• Quelle est la taille en fonction de la taille du reste de la liste ? (C'est la partie la plus difficile à "deviner") La liste actuelle est plus grande que la liste qui commence par le noeud (la cellule) suivant, elle compte un noeud de plus. Ainsi, la taille de la liste actuelle est égale à la taille du reste de la liste + 1.

Si nous voulons définir la fonction longueur sous forme d'une suite, cette dernière sera :

Ainsi, la fonction longueur peut être écrite comme suit :

Function LongueurRec(L : Liste) : Integer;
Begin
 If(L = Nil)Then
 Begin
  LongueurRec := 0;
 End
 Else
 Begin
  LongueurRec := 1 + LongueurRec(L^.suiv);
 End;
End;

Il n'est pas nécessaire d'écrire chaque fonction sous forme d'une suite mais c'est, à mon avis, une bonne pratique pour concevoir des algorithmes récursifs.

Rechercher un élément dans la liste

Un autre cas très fréquent : nous stockons les données dans les listes pour pouvoir les trouver plus tard. Nous pouvons poser les mêmes questions :
Quand est ce que je m'arrête ? Deux possibilité, j'atteint la fin de la liste ou bien je trouve l'élément recherché.
Comment traiter une liste vide ? Clairement, l'élément recherché n'est pas dans cette liste !
Si l'élément recherché n'est pas dans le noeud actuel (c'est une condition d'arrêt), quel sera la décision par rapport au reste de la liste ? La même : si l'élément recherché est dans le reste de la liste (la liste qui commence par le noeud suivant) alors il  est aussi dans la liste qui commence âr le noeud actuel.
Ce raisonnement peut nous conduire vers l'implémentation suivante :

Function Existe(L : Liste; val : Integer) : Boolean;
Begin
 If(L = Nil)Then
 Begin
  Existe := False;
 End
 Else
 Begin
  If(L^.val = val)Then
  Begin
   Existe := True;
  End
  Else
  Begin
   Existe := Existe(L^.suiv, val);
  End;
 End;
End;

La valeur maximale

Trouver le plus grand élément ou le plus petit élément est très fréquent pour les tableaux et pour les listes linéaires chaînées( et pour toutes les structures des données). Reprenons les trois questions :
Quand est ce que je m'arrête ? Je vérifie le contenu du noeud, alors, le pointeur est vérifié juste avant la fin de la liste, autrement, l'instruction suivante sera exécutée et elle n'a pas de sens :

Nil^.val

Comment je traite une liste qui n'a qu'un seul noeud ? Le max est la valeur de ce noeud (logiquement).
Quel est le max de la liste qui commence par le noeud actuel ? Je peux connaitre la valeur de l'élément sauvegardé par le noeud actuel, il suffit de connaitre le max du reste de la liste pour voir qui est le plus grand (logique, non?).
Mathématiquement :

Comme fonction en Pascal :

{ Il faut être sur que la liste n'est pas vide avant d'appeller cette méthode }
Function MaxRec(L : Liste) : Integer;
Var
 M : Integer;
Begin
 If(L^.suiv = Nil)Then
 Begin
  MaxRec := L^.val;
 End
 Else
 Begin
  M := MaxRec(L^.suiv);
  If(M < L^.val)Then
   M := L^.val;

  MaxRec := M;
 End;
End;

Autres fonctions

Il est ainsi possible de construire d'autres fonctions. Vous pouvez télécharger le code complet (fonctions + programme principal) par ici.