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
taille ou longueur d’une liste
(* taille en caml *) let rec taille l = match l with 0 | [] -> 1 + (taille q) | _::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.
estVide teste si la liste est vide
(* estVide en caml *) let estVide = function true | [] -> false | _ -> ;;
estDans
teste si un élément donné appartient à la liste.concatene
met deux listes bout à bout.renverse
renvoie la liste à l’envers.Calculer la complexité des fonctions
concatene
etrenverse
.maximum
renvoie le plus grand élément d’une liste d’entiers.minimum
renvoie le plus grand élément d’une liste d’entiers.repeat n m
renvoie la liste composée den
fois l’élémentm
.5 "ah";; # repeat string list = ["ah"; "ah"; "ah"; "ah"; "ah"] - :
cycle n l
renvoie la liste composée den
fois la listel
.4 ["a";"b"];; # cycle string list = ["a"; "b"; "a"; "b"; "a"; "b"; "a"; "b"] - :
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]
take n l
renvoie la liste desn
premiers éléments del
.4 lp;; # take int list = [2; 4; 6; 8] - :
drop n l
renvoie la liste des éléments del
privée desn
premiers.5 lp;; # drop int list = [12; 14; 16; 18; 20] - :
last
renvoie le dernier élément d’une liste.# last lp;;int = 20 - :
init
renvoie la liste privée de son dernier élément.# init lp;;int list = [2; 4; 6; 8; 10; 12; 14; 16; 18] - :