Info_MPSI/MP/concours/Premiere annee/recursivite.ml

let suite_iteratif u0 n f = let u = ref u0 in
  for i = 1 to n do
    u := f !u
  done;
  !u;;

let rec suite_recursif u0 n f = if n = 0 then u0 else f (suite_recursif u0 (n-1) f);;

let factorielle_iter n = let f = ref 1 in
  for i = 1 to n do
    f := !f * i
  done;
  !f;;

let rec factorielle_rec n = if n = 0 then 1 else n * factorielle_rec (n-1);;

let puissance_iter x n = let p = ref 1 in
  for i = 1 to n do
    p := !p * x
  done;
  !p;;

let rec puissance_rec x n = if n = 0 then 1 else x * puissance_rec x (n-1);;

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

let rec somme p q = match p with
| 0 -> q
| _ -> somme (p-1) (q+1);;

let rec produit p q = match p with
| 0 -> 0
| _ -> somme q (produit (p-1) q);;

let rec min1 t = let n = Array.length t in
  match n with
  | 1 -> t.(0)
  | _ -> let m = min1 (Array.sub t 1 (n-1)) in
    if t.(0) < m then t.(0) else m;;

(*On veut maintenant l'indice du minimum*)
let rec min2 t = let n = Array.length t in
  match n with
  | 1 -> 0
  | _ -> let m = min2 (Array.sub t 1 (n-1)) in
    if t.(0) < t.(m+1) then 0 else m+1;;

let rec produit_egyptien p q = match p with
| 0 -> 0
| _ -> if p mod 2 = 0 then produit_egyptien (p/2) (2*q)
  else q + produit_egyptien (p-1) q;;

let rec division_euclidienne p q = if p < q then (0,p) else
  let (a,b) = division_euclidienne (p-q) q in
  (a+1,b);;

let rec pgcd a b = if b = 0 then a else pgcd b (a mod b);;

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

let rec coefficient_binomial n p = if p = 0 || p = n then 1
  else coefficient_binomial (n-1) (p-1) + coefficient_binomial (n-1) p;;

(*Hanoi*)

let rec deplace n i j k = 
  if n = 1 then print_string ("Deplacer le disque de " ^ string_of_int i ^ " vers " ^ string_of_int j ^ "\n")
  else (deplace (n-1) i k j; deplace 1 i j k; deplace (n-1) k j i);;

let hanoi n = deplace n 1 2 3;;