Some more tail recursion... →
Let’s continue with tail recursion and folding (recollect our previous post. Let’s use those concepts to write insertion sort algorithm. In an earlier post we wrote a recursive implementation of insertion sort algorithm as below:
let rec insert x lst =
match lst with
| [] -> [x]
| h::t ->
if (x <= h) then x::h::t
else h::(insert x t);;
let rec isort lst =
match lst with
| [] -> []
| [x] -> [x]
| h::t -> insert h (isort t)
Now, let’s write a tail recursive version of insertion sort. Let’s just call it tr_isort
.
let tr_isort lst =
let rec aux lst acc =
match lst with
| [] -> acc
| h::t -> aux t (insert h acc)
in
aux lst [];;
Food for thought - is it possible to write a tail-recursive version of insert
function that we used above? If yes, why don’t we try it. If no, why not?