let rec longueur l = match l with
| [] -> 0
| t::q -> 1 + longueur q;;

let rec appartient x l = match l with
| [] -> false
| t::q -> if t = x then
  true
else
  appartient x q;;
 
let rec occurence x l = match l with
| [] -> 0
| t::q -> if t = x then
    1+ occurence x q
else
  occurence x q;;

let rec dernier l = match l with
| [a] -> a
| t::q -> dernier q;;

let rec ajout_fin x l = match l with
| [] -> [x]
| t::q -> t::ajout_fin x q;;

let rec ieme i l = let x::xs=l in
  if i = 0 then x else ieme (i-1) xs

let rec supprime i l = let t::q =l in
match i with
| 1 -> List.tl l
| _ -> t::(supprime (i-1) q);;


let rec supprimetout x l = match l with
| [] -> []
| t::q -> 
  if t=x then
    supprimetout x q
  else
    t::(supprimetout x q);;

let rec insere x i l= let t::q=l in
match i with
| 1 -> x::l 
| _ -> t::(insere x (i-1) q);;

let rec concatene l1 l2 =
match l2 with
| [] -> l1
| t::q -> t::(concatene l1 q);;

let rec concatene_inverse l1 l2 =
  match l1 with
  | [] -> List.rev l2
  | x :: xs -> concatene_inverse xs (x :: l2);;
let rec mirroir l =
  match l with
  | [] -> []
  | x :: xs -> mirroir xs @ [x];;

let rec addition l1 l2 =
  match (l1, l2) with
  | ([], _) -> l2
  | (_, []) -> l1
  | (x :: xs, y :: ys) -> (x + y) :: addition xs ys
;;
let rec fusion l1 l2 =
  match (l1, l2) with
  | ([], _) -> l2
  | (_, []) -> l1
  | (x :: xs, y :: ys) ->
      if x <= y then
        x :: fusion xs l2
      else
        y :: fusion l1 ys;;



let rec somme l = match l with
| [] -> 0
| t::q -> t+somme q;;

let rec maximum l =
  match l with
  | [] -> failwith "empty list"
  | [x] -> x
  | x :: xs ->
      let max_tail = maximum xs in
      if x > max_tail then x else max_tail


let rec second_max l =
  match l with
  | [] | [_] -> failwith "not enough elements"
  | [x; y] -> if x > y then y else x
  | x :: xs ->
      let (max_tail, second_max_tail) = (maximum xs, second_max xs) in
      if x > max_tail then
        if max_tail > second_max_tail then max_tail else second_max_tail
      else
        if x > second_max_tail then x else second_max_tail

let rec evaluation p x =
  match p with
  | [] -> 0.0
  | a :: [] -> a
  | a :: b :: xs ->
      let q = b +. x *. evaluation xs x in
      evaluation (q :: xs) x +. a


let rec binomial n p = match (n,p) with
| (n,0) -> 1
| (n,p) when p=n -> 1
| _ -> binomial(n-1) p + binomial (n-1) (p-1);;

let rec ligne_suivante l =
  match l with
  | [] -> [1]
  | x :: xs ->
      let rec aux acc prev = 
        match prev with
        | [] -> List.rev (1 :: acc)
        | y :: ys -> aux ((x + y) :: acc) ys
      in aux [] l;;

let rec pascal n =
  match n with
  | 0 -> []
  | 1 -> [[1]]
  | _ ->
      let prev = pascal (n - 1) in
      let last = List.hd (List.rev prev) in
      let next = ligne_suivante last in
      prev @ [next]