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

P(0) = 1

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

Q(0) = 0

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