Tail recursion as an idiom for space-efficient algorithms

Recursive algorithms are usually seen as memory-inefficient when compared to their looping counterparts. This is because with each recursive call, stack continues to grow until we hit the base case that returns a value that is used then to evaluate the call before it and so on. It turns out that there is a way to address this problem, at least in some cases, by using an idiom called tail recursion.

Idea behind tail recursion is simple - if we can make the expression that uses recursive call not do any additional work when it receives the value from the call, the compiler can optimize the code by popping the call frame off the stack immediately after the call is made.

For example…

Let's look at the function below that sums up the integers in a list:

let rec sumn l =
  match l with
    [] -> 0
  | h::t -> h + sumn t (* extra work needed after sumn t returns its value *)

As desribed in the comment, extra work of adding the head element to the value returned by the recursive call of the tail is required. This results in taking up memory proportional to the size of the list.

To convert this into a tail recursive function, we use an accumulator pattern where the addition is done using an accumulator variable which is an argument to the helper function:

let sumn_tr l =
  let rec helper acc l =
    match l with
      [] -> acc
    | h::t -> helper (h + acc) t in
  helper 0 l

Notice that our main function is not recursive. Instead, we create a recursive helper function inside that uses acc argument to update our result. We call the helper function with 0 as initial value of the accumulator, and at each recursive call, helper is called with an updated accumulator (by adding h to it). Finally, the base case now returns the accumulator when the list is empty. This modification results in constant memory requirement instead of linearly growing as in the original function.

It is worth noting that the tail-recursive function is less readable than the non-tail recursive. So I think the takeaway is to keep this idiom in mind to exploit when needed but not forcibly trying to make every function tail-recursive.