let rec factorielle n = match n with
| 0 -> 1
| n -> n * (factorielle (n-1))
;;

let rec sommielle n = match n with
| 0 -> 0
| n -> n + (sommielle (n-1))
;;

let rec fibonacci n = match n with
| 0 -> 1
| 1 -> 1
| n -> fibonacci (n-1) + (fibonacci (n-2))
;;

fibonacci 40;;

let rec fib_aux n fnm1 fnm2 = match n with
| 0 -> fnm1+fnm2
| n -> fib_aux (n-1) (fnm1+fnm2) fnm1
;;

let fibo n = fib_aux (n-1) 1 0;;

(* Calcul de complexité ? *)

let rec impair n = match n with
| 0 -> false
| n -> not (pair (n-1))
and pair n = match n with
| 0 -> true
| n -> not (impair (n-1))
;;

let rec combinaison n k = match (n, k) with
| (0, 0) -> 1
| (0, _) -> 0
| (_, 0) -> 1
| (n, k) -> (combinaison (n-1) k) + (combinaison (n-1) (k-1))
;;

let rec ackermann = function
  | (0, n) -> n + 1
  | (m, 0) -> ackermann (m - 1, 1)
  | (m, n) -> ackermann (m - 1, ackermann (m, n - 1))
;;

(* Type entiers unaires (Peano) *)

type entier = Zero 
            | Succ of entier
;;

let rec entier_to_int = function
    | Zero -> 0
    | Succ(n) -> 1 + (entier_to_int n)
;;
let rec int_to_entier = function
    | 0 -> Zero
    | n -> Succ(int_to_entier (n-1))
;;
let rec add x y = match x with
| Zero -> y
| Succ(n) -> add n Succ(y)
;;
add (int_to_entier 5) (int_to_entier 4);;

let rec mult x y = match x with
| Zero -> Zero
| Succ(n) -> add (mult n y) y
;;
entier_to_int (mult (int_to_entier 5) (int_to_entier 4));;

let rec facto = function
    | Zero -> Succ(Zero)
    | Succ(n) -> mult (Succ(n)) (facto n)
;;
entier_to_int (facto (int_to_entier 5));;