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.