Notations et conventions

La récursivité est particulièrement adaptée lorsque l'on souhaite manipuler des listes chaînées. Nous utiliserons pour ce faire les fonctions suivantes :

1. $premier(l)$ retourne la donnée se trouvant dans le premier élément de la liste chaînée $l$.
2. $suivants(l)$ retourne un pointeur $l^\prime$ vers le deuxième élément de $l$, cette fonction ne produit aucun effet de bord et ne modifie pas le chaînage.
3. $ajoute(z, l)$ ajoute la donnée $z$ au début de la liste $l$ et retourne un pointeur vers la liste obtenue, elle modifie le chaînage.
4. $estVide(l)$ retourne vrai si et seulement si la liste $l$ ne contient aucun élément.
5. $listeVide()$ retourne une constante que nous identifierons à la liste vide, c'est-à-dire ne contenant aucun élément.

Vous prendrez soin de ne pas confondre les listes et les données. Ces dernières sont génériques, vous pouvez placer dans une liste des données de n'importe quel type, même d'autres listes... Nous noterons mathématiquement les listes entre des crochets, par exemple $[1, 4, 3, 7]$. La liste vide, retournée par la fonction $listeVide()$ sera notée $[]$. Vous pourrez créer une liste à un élément par exemple en écrivant

$$ajoute(4, listeVide())$$

Cette instruction crée la liste $[4]$. Pour créer une liste à deux éléments, vous utiliserez le même principe :

$$ajoute(3, ajoute(4, listeVide()))$$

Cette instruction crée la liste $[3, 4]$. Les éléments de la liste sont indicés à partir de $1$. Nous ne gérerons pas la mémoire, on considérera qu'un garbage collector s'en occupera.