You are here
Homemutual recursion
Primary tabs
mutual recursion
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 $f,g$ such that $f(0)=0$ and $g(0)=1$, with $f(n+1)=f(n)g(n)$ and $g(n+1)=f(n)+g(n)$ is defined via mutual recursion. It is easy to see that $f(n)=0$ and $g(n)=1$.

Fibonacci numbers can be interpreted via mutual recursion: $F(0)=1$ and $G(0)=1$, with $F(n+1)=F(n)+G(n)$ and $G(n+1)=F(n)$.
Formally,
Definition. Functions $f_{1},\ldots,f_{m}:\mathbb{N}^{{k+1}}\to\mathbb{N}$ are said to be defined by mutual recursion via functions $g_{1},\ldots g_{m}:\mathbb{N}^{k}\to\mathbb{N}$ and functions $h_{1},\ldots,h_{m}:\mathbb{N}^{{k+m+1}}\to\mathbb{N}$, if
$\displaystyle f_{i}(\boldsymbol{x},0)$  $\displaystyle=$  $\displaystyle g_{i}(\boldsymbol{x}),$  
$\displaystyle f_{i}(\boldsymbol{x},n+1)$  $\displaystyle=$  $\displaystyle h_{i}(\boldsymbol{x},n,f_{1}(\boldsymbol{x},n),\ldots,f_{m}(% \boldsymbol{x},n)),$ 
for any $\boldsymbol{x}\in\mathbb{N}^{k}$, and $i=1,\ldots,m$.
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.
Proposition 1.
As above, if all of $g_{i}$ and $h_{i}$ are primitive recursive, so are all of $f_{i}$.
Proof.
We use the multiplicative encoding technique. Define function $F:\mathbb{N}^{{k+1}}\to\mathbb{N}$ as follows:
$F(\boldsymbol{x},n)=\operatorname{exp}(p_{1},f_{1}(\boldsymbol{x},n))\cdots% \operatorname{exp}(p_{m},f_{m}(\boldsymbol{x},n)),$ 
where $p_{i}$ is the $i$th prime number ($p_{1}=2$, etc…). Furthermore,
$(F(\boldsymbol{x},n))_{i}=f_{i}(\boldsymbol{x},n),$ 
where $(z)_{i}$ denotes the exponent of prime $p_{i}$ in $z$. Then
$\displaystyle F(\boldsymbol{x},0)$  $\displaystyle=$  $\displaystyle\prod_{{i=1}}^{m}\operatorname{exp}(p_{i},g_{i}(\boldsymbol{x}))=% G(\boldsymbol{x}),\mbox{ and}$  
$\displaystyle F(\boldsymbol{x},n+1)$  $\displaystyle=$  $\displaystyle\prod_{{i=1}}^{m}\operatorname{exp}(p_{1},f_{1}(\boldsymbol{x},n+% 1))$  
$\displaystyle=$  $\displaystyle\prod_{{i=1}}^{m}\operatorname{exp}(p_{i},h_{i}(\boldsymbol{x},n,% f_{1}(\boldsymbol{x},n),\ldots,f_{m}(\boldsymbol{x},n)))$  
$\displaystyle=$  $\displaystyle\prod_{{i=1}}^{m}\operatorname{exp}(p_{i},h_{i}(\boldsymbol{x},n,% (F(\boldsymbol{x},n))_{1},\ldots,(F(\boldsymbol{x},n))_{m})$  
$\displaystyle=$  $\displaystyle H(\boldsymbol{x},n,F(\boldsymbol{x},n))$ 
where
$G(\boldsymbol{x})=\prod_{{i=1}}^{m}\operatorname{exp}(p_{i},g_{i}(\boldsymbol{% x})),$ 
and
$H(\boldsymbol{x},y,z)=\prod_{{i=1}}^{m}\operatorname{exp}(p_{i},h_{i}(% \boldsymbol{x},y,(z)_{1},\ldots,(z)_{m})$ 
Since each of the $g_{i}$ is primitive recursive, $G$ is primitive recursive. Since each of the $h_{i}$ is primitive recursive, $H$ is primitive recursive. So $F$ is primitive recursive, as it is defined via primitive recursion by $G$ and $H$. Therefore, each $f_{i}=(F)_{i}$ is primitive recursive. ∎
Remark. The primitive recursiveness of mutual recursion can be derived from courseofvalues recursion. The idea is the following: list the $f_{i}$’s in order, and construct a single function $F$ so the its values correspond to the values of the $f_{i}$’s in the order given. For example, if two unary functions $f_{1}$ and $f_{2}$ defined by mutual recursion, then
$f_{1}(0)$  $f_{2}(0)$  $f_{1}(1)$  $f_{2}(1)$  $f_{1}(2)$  $\cdots$  $f_{1}(k)$  $f_{2}(k)$  $f_{1}(k+1)$  $f_{2}(k+1)$  $\cdots$ 
$F(0)$  $F(1)$  $F(2)$  $F(3)$  $F(4)$  $\cdots$  $F(2k)$  $F(2k+1)$  $F(2k+2)$  $F(2k+3)$  $\cdots$ 
Then it is not hard to see that $F(k+1)$ depends on $F(k),F(k1)$, and $F(k2)$, and an explicit formula can be derived expressing the dependency. Furthermore, this formula is easily seen to be primitive recursive, and hence so is $F(k)$.
Mathematics Subject Classification
03D20 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
Recent Activity
new question: Prove a formula is part of the Gentzen System by LadyAnne
Mar 30
new question: A problem about Euler's totient function by mbhatia
new problem: Problem: Show that phi(a^n1), (where phi is the Euler totient function), is divisible by n for any natural number n and any natural number a >1. by mbhatia
new problem: MSC browser just displays "No articles found. Up to ." by jaimeglz
Mar 26
new correction: Misspelled name by DavidSteinsaltz
Mar 21
new correction: underlinetypo by Filipe
Mar 19
new correction: cocycle pro cocyle by pahio
Mar 7
new image: plot W(t) = P(waiting time <= t) (2nd attempt) by robert_dodier
new image: expected waiting time by robert_dodier
new image: plot W(t) = P(waiting time <= t) by robert_dodier