# Lesson 13.2. Mutual recursion

## Mutual recursion

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.

## Example

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);
}``````

## Exercise

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
```

## Quiz

When are we in a mutual recursion?