Tail-Recursive Call Optimization

Tail-recursion is of crucial importance in functional programming as loops in imperative programming are often implemented as tail-recursive functions.

Suppose that a function bar calls another function bar, that is, there is a call to bar appearing in the body of foo, where foo and bar may actually be the same fuction. If the return value of the call to bar also happens to be the return value of foo, then this call is often referred to as a tail-call. If foo and bar are the same, then this call is a (recursive) self tail-call. For instanace, there are two recursive calls in the body of the following defined function f91, where the outer call to f91 is a tail-call while the inner one is not:

fun f91 (n: int): int = if n > 100 then n - 10 else f91 (f91 (n+11))

If each self call in the body of a function is a tail-call, then this function is tail-recursive.

It is arguably that the single most important optimization performed by the ATS compiler is the translation of every self tail-call into a direct (local) jump. This optimization effectively turns every tail-recursive function into the equivalent of a loop, guaranteeing that a fixed amount of stack space is adequate for executing each call to the function.

Let us now see some examples that can help further illustrate the notion of tail-recursive call optimization. The following recursive function sum1 sums up all the natural numbers less than or equal to n, where n is the given parameter:

fun sum1 (n: int): int = if n > 0 then n + sum1 (n-1) else 0

Clearly, sum1 is not recursive as the only self call in its body is not a tail-call. The counterpart of sum1 in C can essentially be given as follows:

int sum1 (int n) {
  return (n > 0) ? n + sum1 (n-1) : 1 ;
} // end of [sum1]

When applied to an integer n, the following defined function sum2 also sums up all the natural numbers less than or equal to n:

fn sum2 (n: int): int = let
  fun loop (n: int, res: int): int =
    if n > 0 then loop (n-1, res + n) else res
  // end of [loop]
in
  loop (n, 0)
end // end of [sum2]

The inner function loop in the definition of sum2 is tail-recursive. The stack space consumed by loop is constant, that is, it is independent of th value of the argument of sum2. Essentially, the ATS compiler translates the definition of sum2 into the following C code:

int sum2_loop (int n, int res) {
  loop:
  if (n > 0) {
    res = res + n ; n = n - 1; goto loop; 
  } else {
    // do nothing
  }
  return res ;
}

int sum2 (int n) { return sum2_loop (n, 0) ; }

Translating sum1 into sum2 is a fairly straightforward process. However, it can be highly involved, sometimes, to turn a non-tail-recursive implementation into an equivalent one that is tail-recurisve.