The notion of recursion is ubiquitous in ATS. For instance, there are
recursively defined sorts (datasorts) and types (datatypes) in the statics,
and there are also recursively defined functions in the dynamics.
Literally, the word *recurse* means "go back". When an entity is
defined recursively, it means that the entity being defined can appear in
its own definition. In the following presentation, I will show several ways
to define (or implement) recursive functions and non-recursive functions,
where the latter is just a special case of the former.

The keyword fun can be used to initiate the definition of a recursive function. For instance, following is the definition of a recursive function:

A non-recursive function is a special kind of recursive function that does make use of itself in its own definition. So one can certainly use fun to initiate the definition of a non-recursive function. However, if there is a need to indicate explicitly that a non-recursive is being defined, then one can use the keyword fn to do so. For instance, the definiton of a non-recursive function is given as follows: which is directly translated by the compiler into the following binding between a name and a lambda-expression: As another example, please note that the two occurrences of the symbol fact in the following code refer to two distinct functions: While the first fact (to the left of the equality symbol) refers to the (non-recursive) function being defined, the second one is supposed to have been declared previously.A recursive function can also be defined as a recursive value. For instance, the recursive function fact defined above can be defined as follows:

where the keyword rec indicates that fact is defined recursively, that is, it is allowed to appear in its own definition. In fact, the former definition of fact is directly translated into the latter one by the compiler. Of course, one may also use a reference to implement recursion:val fact = ref<int->int>($UNSAFE.cast(0)) val () = !fact := ( lam (x:int):int => if x > 0 then x * !fact(x-1) else 1 ) (* end of [val] *)

For defining mutually recursive functions, one can simply use the keyword and to concatenate function definitions. For instance, the following code defines two functions isevn and isodd mutually recursively:

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

val rec isevn : int -> bool = lam (x) => if x > 0 then isodd(x-1) else true and isodd : int -> bool = lam (x) => if x > 0 then isevn(x-1) else false

Even at this point, I have not presented all of the possible ways to define functions in ATS. For instance, one can also define stack-allocated closure-functions in ATS, which may be either recursive or non-recursive. I plan to introduce such functions elsewhere in this tutorial.

Often, the interface (that is, type) for a function is declared at one place and its definition (or implementation) is given at another place. For instance, one may first introduce the following declaration:

Later, one can implement fact according to the above declaration: When implement is used to initiate the definition of a function, any previously declared symbols (including the one that is being defined) can appear in the definition. If it is desirable, one may replace implement with implmnt.Please find on-line the entirety of the code used in this chapter.