tail recursion

(* Recursive functions witch do not build up a growing intermediate
 * expression are known as tail recursive. The following example
 * function takes an integer n and raises it to the power of x. *)

(* not tail recursive *)
let rec power n x =
   match x with
   | 0 -> 1
   | 1 -> n
   | _ -> n * power n (x - 1);;

(* how it works with power 2 4:
power 2 4;;
2 * (power 2 3)
2 * (2 * (power 2 2))
2 * (2 * (2 * (power 2 1)))
2 * (2 * (2 * 2))
2 * (2 * 4)
2 * 8
16
*)

(* tail recursive *)
let power n x =
   let rec auxpow acc x =
      match x with
      | 0 -> acc
      | _ -> auxpow (acc * n) (x-1)
   in auxpow 1 x;;

(* how it works with power 2 4:
power 2 4;;
auxpow 1 4
auxpow 2 3
auxpow 4 2
auxpow 8 1
auxpow 16 0
16
*)