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 3:
power 2 3
2 * (power 2 2)
2 * (2 * (power 2 1))
2 * (2 * (2))
8
*)

(* 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 3:
power 2 3
auxpow 1 3
auxpow 2 2
auxpow 4 1
auxpow 8 0
8
*)