Prérequis

Introduction

On peut définir des fonctions récursives, on peut aussi définir des structures de données récursives ! Le premier tel exemple est la liste. Nous verrons ensuite les arbres.

La liste est l’équivalent récursif des tableaux. Une liste peut être vide. Ou bien être constituée d’un élément (la tête) et d’une liste des éléments suivants (la queue).

On peut imaginer une liste comme un serpent : si on lui coupe la tête, il reste la queue. Et la queue est elle-même un serpent.

Représentation graphique sur le blog de Philip Wadler

Exercices

1. taille ou longueur d’une liste

   (* taille en caml *)
   let rec taille l = match l with
   	| [] -> 0
   	| _::q -> 1 + (taille q)
   ;;

   Le filtrage recherche un motif qui pour une liste sera de la forme ou bien la liste vide, ou bien une tête suivie d’une queue. La fonction taille est définie de façon récursive puisqu’on la réappelle sur la queue de la liste.

2. estVide teste si la liste est vide

   (* estVide en caml *)
   let estVide = function
   | [] -> true
   | _  -> false
   ;;

3. estDans teste si un élément donné appartient à la liste.

4. concatene met deux listes bout à bout.

5. renverse renvoie la liste à l’envers.

6. Calculer la complexité des fonctions concatene et renverse.

7. maximum renvoie le plus grand élément d’une liste d’entiers.

8. minimum renvoie le plus grand élément d’une liste d’entiers.

9. repeat n m renvoie la liste composée de n fois l’élément m.

   # repeat 5 "ah";;
   - : string list = ["ah"; "ah"; "ah"; "ah"; "ah"]

10. cycle n l renvoie la liste composée de n fois la liste l.

    # cycle 4 ["a";"b"];;
    - : string list = ["a"; "b"; "a"; "b"; "a"; "b"; "a"; "b"]

11. pairs n renvoie la liste des n premiers nombres pairs.

    # let lp  = pairs 10;;
    val lp : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18; 20]

12. take n l renvoie la liste des n premiers éléments de l.

    # take 4 lp;;
    - : int list = [2; 4; 6; 8]

13. drop n l renvoie la liste des éléments de l privée des n premiers.

    # drop 5 lp;;
    - : int list = [12; 14; 16; 18; 20]

14. last renvoie le dernier élément d’une liste.

    # last lp;;
    - : int = 20

15. init renvoie la liste privée de son dernier élément.

    # init lp;;
    - : int list = [2; 4; 6; 8; 10; 12; 14; 16; 18]