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

Try online

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

Do the exercise

Solution

Quiz

When are we in a mutual recursion?

when a function is called itself

when two functions call each other

when three functions call each other

when two or more functions call each other

Check

Lesson 13.2 Summary Lesson 14.1

Lesson 13.2. Mutual recursion

Mutual recursion

Example

Exercise

Quiz

See also