let rec deplace n i j k =
  if n = 1 then
    begin
    print_string (string_of_int 1 ^ " -> " ^ string_of_int j);
    print_newline ()
    end
  else
    begin
      deplace (n-1) i k j;
      print_string (string_of_int 1 ^ " -> " ^ string_of_int j);
      deplace (n-1) k j i;
      print_newline ()
    end
  ;;

  let hanoi n =
    deplace n 1 2 3;;
hanoi 10;;

(* let rec a n a0 b0= match n with
| 0 -> a0
| _  -> (a (n-1) a0 +. b(n-1) b0) /. 2.
and b n a0 b0 = match n with
| 0 -> b0 
| _ -> sqrt (a n a0 *. b n b0);; *)

let rec correctan a0 b0 n = match n with
| 0 -> a0
| _ -> (correctan a0 b0 (n-1) +. (correctbn a0 b0 (n-1))) /. 2.
and correctbn a0 b0 n = match n with
| 0 -> b0
| _-> sqrt ((correctan a0 b0 (n-1)) *. (correctbn a0 b0 (n-1)))

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

let rec facto n = match n with
| 0 -> 1
| _ -> n * facto (n-1)

let rec facto_aux n acc k = match k with
| k when k=n -> acc
| _ -> facto_aux n (acc*(k+1)) (k+1);;

let facto_term n =
  facto_aux n 1 0;;
let rec facto_aux2 n acc= match n with
| 0 -> acc
| _ -> facto_aux2 (n-1) (acc*(n));;

let facto_term2 n =
  facto_aux2 n 1;;

let rec puissance a n = match n with
| 0 -> 1
| _ -> a * puissance a (n-1);;


let rec puissanceaux1 a n acc k = match k with
| k when k=n -> acc
| _ -> puissanceaux1 a n (acc*a) (k+1);;  

let puissance_term1 a n =
  puissanceaux1 a n 1 0;;

let rec puissanceaux2 a n acc = match n with
| 0 -> acc
| _ -> puissanceaux2 a (n-1) (acc*a);;

let puissance_term2 a n = 
  puissanceaux2 a n 1;;

let rec f_un n f acc k = match n with
| k when k=n -> acc
| _ -> f_un n f (f acc) (k+1);;

let f_unterm1 n f u0 = f_un n f u0 0;;

let rec f_un2 n f acc = match n with
| 0 -> acc
| _ -> f_un2 (n-1) f (f acc);;

let f_unterm2 n f u0 = f_un2 n f u0;;

let rec suminv n k acc = match k with
| k when k=n -> acc
| _ -> suminv n (k+1) (acc +. 1. /. ((float_of_int k)**2.))

let rec suminvprof n acc = match n with
| 1.0 -> acc
| _ -> suminvprof (n-.1.0) (acc +.(1./.n)**2.);;

let sommeint n = suminvprof (float_of_int n) 1.0;;

let rec fibo_aux n acc1 acc2 = match n with
| 0 -> acc1
| _ -> fibo_aux (n-1) (acc2) (acc1+acc2);;

let fibo n = fibo_aux n 0 1;;

let rec pour phi d n = match n with
| 0 -> d
| _ -> phi (pour phi d (n-1));;

let rec pourterm phi d n =match n with
| 0 -> d
| _ -> pourterm phi (phi d) (n-1);;

let puissancepour a n = pour (function x -> a*x) 1 n;;

let rec tantque cond phi d = match (cond d) with
| true -> tantque cond phi (phi d)
| false -> d;;

let rec aux a x n= match n with
| 0 -> x
| _ -> aux a (a*x) (n-1);;

let puissanceaux3 a n = aux a 1 n;;

let rec auxfibo (x,y) n = match n with
| 0 -> x
| _ -> auxfibo (y, x+y) (n-1);;

let auxfiboterm n = auxfibo (0,1) n;;

(* let rec pgcd2prof a b = match (a,b) with
| (a,0) -> a
| (a,b) when a<b -> pgcd2prof b a
| _ -> pgcd2prof (a-b) b;; *)

let pgcd2iter a b = let c = ref a and d = ref b in
  while !d <> 0 do
    if !d > !c then
      begin
      let aux = !c in
      c := !d;
      d := aux
      end
    else
      c := !c - !d
    done;
    !c
  ;;