Key Takeaway

Mutual Recursion: A programming technique where two or more functions call each other. It's essential to ensure that mutual recursion progresses towards a base case to avoid infinite recursion and non-terminating programs.

Summary: Mutual Recursion

Definition

• Mutual Recursion: Occurs when two or more functions call each other.
• Base Case: Each mutually recursive function must progress towards a base case to ensure termination.

Example: Even and Odd Functions

• Problem: Determine if a positive number is even without using the modulus operator.

isEven Function:

int isEven(unsigned int n) {
  if (n == 0) {
    return 1;  // Base case
  }
  if (n == 1) {
    return 0;  // Base case
  }
  return isOdd(n - 1);  // Call isOdd for complex step
}

isOdd Function:

int isOdd(unsigned int n) {
  if (n == 0) {
    return 0;  // Base case
  }
  if (n == 1) {
    return 1;  // Base case
  }
  return isEven(n - 1);  // Call isEven for complex step
}

Complete Example with Prototypes:

int isOdd(unsigned int n);  // Prototype for isOdd

int isEven(unsigned int n) {
  if (n == 0) {
    return 1;
  }
  if (n == 1) {
    return 0;
  }
  return isOdd(n - 1);
}

int isOdd(unsigned int n) {
  if (n == 0) {
    return 0;
  }
  if (n == 1) {
    return 1;
  }
  return isEven(n - 1);
}

Practical Uses

• Recursive Descent Parsing: A common application of mutual recursion, used in parsing input text to determine its meaning.
  • parseCall: Parses a function call and calls parseExpression for each argument.
  • parseExpression: Parses expressions and may call parseCall if it encounters a function call.

Example:

f(3, g(42), h(x, y, z(1)))

• parseCall handles f and its arguments.
• parseExpression handles each argument, calling parseCall when encountering function calls like g(42) and h(x, y, z(1)).