let rec separer = function [] -> [], [] | [x] -> [x], [] | x1::x2::tail -> let t1,t2 = separer tail in (x1::t1), (x2::t2);;
On définit la fonction separer
par
récurrence sur la structure des listes ou, ce qui revient au même, par
récurrence sur la taille des listes. Remarquez qu'on doit définir non
seulement le cas par récurrence pour la taille n en
fonction de la taille n-1, mais également deux cas
de base pour n=0 et n=1.