let rec mac (n:int) : int = 
    if n>100 then (n-10) else mac(mac(n+11));;


(*récurrence croisée*)
let rec paire (n:int) : bool = 
        if (n=0) then true 
                 else  (not (impaire (n-1)))
    and 
        impaire (n:int) : bool =
        if (n=0) then false 
                 else (not (paire (n-1)));;



let rec u (n:int) (v:int) :int = i
  (*implantation de la suite de Syracuse. (u n m= = le nième terme de la suite de Syracuse pour laquelle U_0 vaut m *)
        if (n=0) then v
                 else if ((u (n-1) v) mod 2)=1 then 3*( u (n-1) v)+1
                       else (u (n-1) v)/2;;

let rec fib (m:int) : int =
  (*fib(m) est le mième nombre de la suite de Fibonnacci*) 
  match m with 
        0 -> 1
      | 1 -> 1
      | _ -> (fib (m-1) + fib (m-2))
     ;;

let rec double (m:int) : (int*int) =
(* double (m) =(fibonnacci(m-1),fibonnacci (m) *)
     match m with
             1 -> (1,1)
            |n  ->  let (a,b)=double (n-1)
      in (b,a+b);;         

let fib_dyn (n:int) : int =
    snd (double n);;

(*Naturels*)

type naturel = Zero | Succ of naturel;;

let rec naturel_to_int (n:naturel) : int =
(*transforme un naturel en l'int correspondant*)
    match n with 
           Zero    -> 0 
          |Succ(p) -> 1 + (naturel_to_int p);;

let rec int_to_naturel (x:int) : naturel = 
(*transforme l'int en le naturel correspondant*)
    match x with 
           0 -> Zero
          |_ -> Succ(int_to_naturel (x-1));;

(*arithmetique sur les naturels*)

let rec add (m:naturel) (n:naturel) : naturel = 
(* addition de deux naturels *)
    match m with 
          Zero    -> n 
         |Succ(p) -> Succ(add p n);;
  
let rec mul (m:naturel) (n:naturel) : naturel = 
(* multiplication de deux naturels *)
    match m with 
           Zero -> Zero
         | Succ(p) -> (add n (mul p n));;
 
let rec exposant (n:naturel) (m:naturel) : naturel = 
(* calcule de l'exposant : exposant n m = n^m *)
    match m with 
            Zero    -> Succ(Zero)
          | Succ(p) -> (mul n (exposant n p));;