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.


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


$$ 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?

Check Bravo! When two or more functions call each other, it is a mutual recursion. Try again...

See also

Last update : 12/06/2022