Mutually Recursive Functions

A collection of functions are defined mutually recursively if each function can make calls in its body to any functions in this collection. Mutually recursive functions are commonly encountered in practice.

As an example, let P be a function on natural numbers defined as follows:

Let us introduce a function Q such that Q(n) is the sum of the products of i and P(i) for i ranging from 1 to n. Then the functions P and Q can be defined mutually recursively as follows:

The following implementation of P and Q is a direct translation of their definitions into ATS:

fun P (n:int): int = if n > 0 then 1 + Q(n-1) else 1 and Q (n:int): int = if n > 0 then Q(n-1) + n * P(n) else 0

Note that the keyword and is used to combine function definitions.