A Crash into FP through ATS:
Prev		Next

Chapter 3. Recursive Functions (2)

While recursion can be really powerful for solving problems, there is a serious issue of practicality with recursion. If we follow the semantics of C, then we know that the evaluation of a function call allocates a call frame on the run-time stack (for thread execution); this frame only unwinds after the evalutation returns; it is entirely possible that other function calls are made during the evaluation. Let us revisit the following implementation of the factorial function:

//
fun
fact(n: int): int =
if n > 0 then n * fact(n-1) else 1
//

Assume that we want to evaluate fact(1000000). Clearly, the evaluation of fact(1000000) calls fact(999999), and the evaluation of fact(999999) calls fact(999998), and so on. When fact(0) is called, there are 1000001 call frames on the run-time stack for evaluating fact(n), where n goes from 1000000 down to 0. In the case where the run-time stack is not deep enough for holding all of these call frames, stack overflow happens at some point of execution (and the evaluation of fact(1000000) terminates abnormally). Please write a program to evaluate fact(1000000) and see what actually happens when it is executed.

While evaluating fact(1000000) may be seen as a contrived example, stack overflow caused by deeply nested recursive calls is a very serious issue in practice. A common approach to addressing this issue makes use of tail-recursion as is illustrated in the following implementation of the factorial function:

//
fun
fact2(n: int): int = let
//
fun
loop(i: int, res: int): int =
if i < n
  then loop(i+1, (i+1)*res) else res
// end of [if]
//
in
  loop(0, n)
end // end of [fact2]
//

Note that loop is a recursive function. The recursive call in the body of loop is a tail-call in the sense that the return value of the call can be directly used as the return value of the caller. In contrast, the return value of the recursive call in the body of fact is not a tail-call (as the value needs to be multiplied by n in order to obtain the return value of the caller). Let us take a look at another example:

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

In the body of f91, there are two recursive calls; the outer call is a tail-call but the inner call is not (as the return value of the inner call needs to be passed to be outer call in order to obtain the return value of the caller).

If all of the recursive calls in the body of a function are tail-calls, the function is referred to as being tail-recursive. By default, the ATS compiler translates each tail-recursive call into a local jump. When a tail-recursive function is called, the evaluation of the call does not need to allocate any call frames for handling subseqent recursive calls and therefore it runs no risk of stack overflow due to deeply nested recursion. Please write a program to evaluate fact2(1000000) and see what actually happens when it is executed.

In ATS, mutually recursive functions can be defined by simply joining a sequence of function definitions together. For instance, the functions isevn and isodd are defined mutually recursively in the following code:

//
fun
isevn(n: int): bool =
if n > 0 then isodd(n-1) else true
//
and
isodd(n: int): bool =
if n > 0 then isevn(n-1) else false
//

Note that the keyword and is used for joining function definitions. The call to isodd in the body of isevn is a tail-call, and so is the call to isevn in the body of isodd. In order for the ATS compiler to recognize that these two calls are tail-recursive calls (and thus can be translated into local jumps), the keyword fun needs to be replaced with fnx.

Please find on-line the entirety of the code used in this chapter. Also, it can be found in this article a detailed explanation on tail-recursion and the support in ATS for turning tail-recursive calls into local jumps.

Prev	Home	Next
Recursive Functions (1)		Example: Sierpinski Triangle