Introduction to Programming in ATS:
Prev	Chapter 3. Functions	Next

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:

P(0) = 1
P(n+1) = 1 + the sum of the products of i and P(i) for i ranging from 1 to n

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:

P(0) = 1
P(n+1) = 1 + Q(n)
Q(0) = 0
Q(n+1) = Q(n) + (n+1) * P(n+1)

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.

Prev	Home	Next
Example: The Eight-Queens Puzzle	Up	Mutually Defined Tail-Recursion