We introduced tail recursion in our previous post. Let’s see some more examples of tail recursion. Let’s do a simple one, very similar to our introductory example in order to illustrate the win that tail-recursion optimization by the compiler provides. Let’s consider the function lst_rev, introduced in one of our earlier posts which takes a list lst and returns the reversed list. Here’s it is for your reference:

let rec lst_rev lst =
  match lst with
  | [] -> []
  | h::t ->
     (lst_rev t) @ [h];;

Recollect that in Ocaml, @ is the operator for list concatenation. Let’s work out how the execution of this function on our list [1; 2; 3 4] would look like:

	lst_rev [1; 2; 3; 4]
= 	lst_rev [2; 3; 4] @ [1]
= 	lst_rev [3; 4] @ [2] @ [1]
= 	lst_rev [4] @ [3] @ [2] @ [1]
= 	lst_rev [] @ [4] @ [3] @ [2] @ [1]
=	[] @ [4] @ [3] @ [2] @ [1]
= 	[4; 3; 2; 1]

Here is our tail-recursive version of the same. Let’s call it tr_lst_rev.

let tr_lst_rev lst =
  let rec aux_lst_rev lst acc =
    match lst with
    | [] -> acc
    | h::t -> aux_lst_rev t (h::acc)
  in
  aux_lst_rev lst [];;

Again, very similar to our previous example, we use an accumulator acc to collect the results of intermediate computations (results of each recursive step).

	tr_lst_rev [1; 2; 3; 4]
=	aux_lst_rev [2; 3; 4]	1::[]
=	aux_lst_rev [3; 4] 	2::[1]
=	aux_lst_rev [4] 	3::[2; 1]
=	aux_lst_rev [] 		4::[3; 2; 1]
= 	[4; 3; 2; 1]