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?

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

See also


Last update : 12/06/2022