mutual recursion happens when two functions call each other.
A function f1()
performs a computation by calling a function f2()
, which itself calls the function f1()
.
The risk is that the stopping conditions are never true and that the depth limit is reached.
Here is an example of functions even()
and odd()
that check the parity of an integer n
with a cross recursion.
This example is clearly not optimal, it is just an illustration:
// Returns 1 if n is even
char even(int n) {
if (n==0) return 1;
return odd(n-1);
}
// Returns 1 if n is odd
char odd(int n) {
if (n==0) return 0;
return even(n-1);
}
To write in recursive form the functions \(u_n\) and \(v_n\) according to the following description:
Initial values:
$$ u_0=1 $$ $$ v_0=2 $$
Definition:
$$ u_n = 3.u_{n-1} + 2.v_{n-1} $$ $$ v_n = 2.u_{n-1} + 3.v_{n-1} $$
Here is the expected output:
u(0) = 1 v(0)=2 u(1) = 7 v(1)=8 u(2) = 37 v(2)=38 u(3) = 187 v(3)=188 u(4) = 937 v(4)=938
When are we in a mutual recursion?