La récursivité appliquée aux chaînes de caractères et aux listes
Introduction
Une chaîne de caractère est une structure de données qui permet de rassembler en un unique objet une succession ordonnée de caractères. Ainsi, une définition récursive d’une chaîne de caractères pourrait être :
Une chaîne de caractères est :
- soit la chaîne de caractères vide ;
- soit constituée de son premier caractère et du reste des caractères qui forment aussi une chaîne de caractères (éventuellement vide).
Une liste est une structure de données qui permet de rassembler en un unique objet une succession ordonnée d’objets (ou de valeurs). Ainsi, une définition récursive d’une liste pourrait être :
Une liste est :
- soit la liste vide ;
- soit constituée de son premier élément et du reste des éléments qui forment aussi une liste (éventuellement vide).
Exercices
Penser à écrire, pour chacune des fonctions ci-dessous, sa spécification ainsi qu’un jeu de tests.
Écrire une fonction récursive nommée est_dans, qui, à partir d’un caractère e et d’une chaîne de caractères c, détermine si ce caractère appartient à la chaîne.
Tester cette fonction.
Remarque : la fonction est_dans est un prédicat.
Écrire une fonction récursive nommée rang, qui, à partir d’un caractère e et d’une chaîne de caractères c, détermine la (première) position de ce caractère dans la chaîne. Si le caractère n’est pas présent, retourner un nombre négatif.
Tester cette fonction dans un programme.
Écrire une fonction récursive nommée copie, qui, à partir d’une chaîne de caractères c, retourne une nouvelle chaîne copie de c.
Tester cette fonction.
Écrire une fonction récursive nommée inversion, qui, à partir d’une chaîne de caractères c, retourne la chaîne « mirroir », c’est à dire la chaîne égale à celle passée en argument quand on la lit de droite à gauche.
Tester cette fonction dans un programme.
Un palindrome est un mot (ou une phrase) qui se lit aussi bien de la gauche vers la droite que de la droite vers la gauche : par exemple « radar », « kayak », ou bien la phrase « esope reste et se repose » (si l’on ne tient pas compte des espaces).
Écrire une fonction récursive nommée est_palindrome qui reçoit comme argument une chaîne de caractères contenant le mot (ou la phrase). Cette fonction doit tester si les deux caractères opposés sont identiques, puis appeler récursivement la fonction sur la partie de la chaîne qui ne contient pas ces deux caractères (les espaces sont ignorés).
-
Écrire une fonction nommée
longueur_liste, récursive, qui, à partir d’une liste passée en argument, détermine sa longueur. -
Écrire une fonction nommée
somme_elements, récursive, qui, à partir d’une liste de nombres passée en argument, calcule la somme de tous les nombres. 2bis. Écrire une fonction nomméeproduit_elements, récursive, qui, à partir d’une liste de nombres passée en argument, calcule le produit de tous les nombres. -
Écrire une fonction nommée
plus_grand_element, récursive, qui, à partir d’une liste d’entiers passée en argument, détermine quel est l’entier le plus grand. -
Écrire une fonction nommée
plus_petit_element, récursive, qui, à partir d’une liste d’entiers passée en argument, détermine quel est l’entier le plus petit. -
Écrire une fonction nommée
somme_listes_imbriquees, récursive, qui additionne tous les entiers des listes.
Exemple de listes imbriquées :
- Remarque.
- Cette question peut illustrer, par exemple, la recherche de l’occupation disque de tous les fichiers dans la structure arborescente d’un système de fichiers à partir d’un point de cette structure.
- Écrire une fonction nommée
duplique, récursive, qui, à partir d’un élémenteet d’un entiern, retourne une liste qui contient l’élémenteun nombre de fois égal àn.
- Écrire une fonction nommée
extrait, récursive, qui, à partir d’une listelet d’un entiern, retourne une liste constituée par lesnpremiers éléments del.
-
Écrire une fonction nommée
renverse, récursive, qui, à partir d’une liste, retourne une liste dans laquelle les éléments sont renversés (les derniers apparaissent en premier). -
Écrire une fonction nommée
creation_liste_filtree, qui, à partir de deux entiersietjpassés en argument retourne une liste d’entiers compris entreietjmultiples de 3 ou de 5.
- Modifier la fonction précédente afin que le filtre « entiers multiples de 3 ou de 5 » soit passé en argument.