## Tail-Recursive Functions

Probably the single most important optimization performed by the
ATS/Geizella compiler is the translation of tail-recursive function calls
into direct (local) jumps.

#### Tail-Recursion

When applied to an integer *n*, the following defined function
*sum1* sums up integers from *1* to *n*.
// [sum1] is recursive but not tail-recursive
fun sum1 (n: int): int = if n > 0 then n + sum1 (n-1) else 0

This function is recursive but not tail-recursive. The stack space it
consumes is proportional to the value of its argument. Essentially,
the ATS compiler translates the definition of
*sum1* into the following C code:
int sum1 (int n) {
if (n > 1) return n + sum1 (n-1) ; else return 1 ;
}

When applied to an integer *n*,
the following defined function *sum2* also sums up
integers from *1* to *n*.
fn sum2 (n: int): int = // sum2 is non-recursive
// [loop] is tail-recursive
let fun loop (n: int, res: int) = if n > 0 then loop (n-1, res+n) else res in
loop (n, 0)
end

The inner function *loop* in the definition of *sum2* is
tail-recursive. The stack space consumed by *loop* is a constant
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 > 1) {
res = res + n ; n = n - 1; goto loop;
} else {
res = 1;
}
return res ;
}
int sum2 (int n) { return sum2_loop (n, 0) ; }

#### Mutual Tail-Recursion

Sometimes, mutually tail-recursive functions are encountered. For
instance, in the following example, the functions *even* and
*odd* are mutually tail-recursive.
// [fn*] indicates the need to combine two or more functions
// so as to translate tail-recursive calls into direct jumps
fn* even (n: int): bool = if n > 0 then odd (n-1) else true
and odd (n: int): bool = if n > 0 then even (n-1) else false

The keyword *fn** is used to indicate to the ATS compiler
that the functions *even* and
*odd* need to be combined together so as to turn (mutually)
recursive function calls into direct jumps. Essentially, the ATS compiler
emits the following C code after compiling this example:
bool even_odd (int tag, int n) {
bool res ;
switch (tag) {
0: goto even ;
1: goto odd ;
default : exit (1) ;
}
even: if (n > 0) { n = n - 1; goto odd; } else { res = true; goto done; }
odd: if (n > 0) { n = n - 1; goto even; } else { res = false; goto done; }
done: return res ;
}
bool even (int n) { return even_odd (0, n) ; }
bool odd (int n) { return even_odd (1, n) ; }

Note that mutually recursive functions can be combined in such a manner
only if __they all have the same return type__. In the above case, both
*even* and *odd* have the same return type *bool*.
When translating C code involving embedded loops, we often encounter mutual
tail-recursion. For instance, the following C code prints out ordered pairs
of digits:

int main (int argc, char *argv[]) {
int i, j ;
for (i = 0; i <= 9; i += 1) {
for (j = i; j <= 9; j += 1) {
if (i < j) printf (", ") ; printf ("(%i, %i)", i, j) ;
}
printf ("\n") ;
}
return 0 ;
}

A straightforward translation of the C code into ATS (in functional style)
is given as follows:
implement main (argc, argv) = let
fn* loop1 {i:nat} (i: int i): void =
if i <= 9 then loop2 (i, i) else ()
and loop2 {i,j:nat} (i: int i, j: int j): void =
if j <= 9 then begin
if i < j then print ", "; printf ("(%i, %i)", @(i, j)); loop2 (i, j+1)
end else begin
print_newline (); loop1 (i+1)
end
in
loop1 0
end

where the mutually tail-recursive funtions *loop1* and *loop2*
correspond to the outer and inner loops in the C code, respectively.

The code used for illustration is available here.