Mutual recursion is a way of defining functions via recursion involving several functions simultaneously. In mutual recursion, the value of the next argument of any function involved depends on values of the current arguments of all functions involved. The following are two simple examples:
the pair of functions such that and , with and is defined via mutual recursion. It is easy to see that and .
Fibonacci numbers can be interpreted via mutual recursion: and , with and .
Definition. Functions are said to be defined by mutual recursion via functions and functions , if
for any , and .
Mutual recursion is an apparent generalization of primitive recursion, where the value of the next argument of a function depends on the value of the current argument of the same function, apparent because it is in fact equivalent to primitive recursion.
As above, if all of and are primitive recursive, so are all of .
We use the multiplicative encoding technique. Define function as follows:
where is the -th prime number (, etc…). Furthermore,
where denotes the exponent of prime in . Then
Since each of the is primitive recursive, is primitive recursive. Since each of the is primitive recursive, is primitive recursive. So is primitive recursive, as it is defined via primitive recursion by and . Therefore, each is primitive recursive. ∎
Remark. The primitive recursiveness of mutual recursion can be derived from course-of-values recursion. The idea is the following: list the ’s in order, and construct a single function so the its values correspond to the values of the ’s in the order given. For example, if two unary functions and defined by mutual recursion, then