Practical examples of Mutual Recursion?

Question

I was reading about mutual recursion.In almost all the materials,examples of it was problem to determine whether an integer is even or odd?

int is_even(unsigned int n)
{
    if (n==0) return 1;
    else return(is_odd(n-1));
}

int is_odd(unsigned int n)
{
    return (!iseven(n));
}

Obviously above problem can be solved in an easier manner using a modulus operator.

Other example was a problem to find out if a person is female or male.This can also be solved in easier manner without using recursion.

So is the mutual recursion just theoretical or is there anywhere i can use it to practically to make my solution simpler than using any other technique?

Could you please help me out by giving such an example?

Answer 1

Mutual recursion is not very common but it's useful sometimes. Parsing text with the "recursive descent" method is one practical setting where you can find it.

http://en.m.wikipedia.org/wiki/Recursive_descent_parser

Answer 2

One use case that I generally have is when I am writing a program to play a game. In that instance, you will often be using recursion to go through the game tree to calculate the best move.

Although it can often be done pretty simply without mutual recursion, it can be helpful to code it out that way when the logic for each player is complicated enough to warrant its own function, and there are enough distinct players to where trying to make one giant function gives with a giant mess.

Answer 3

Really late post, one instance is the Quickselect algorithm, if your strategy for the pivot is the Median-of-medians algorithm, since the median-of-medians pivot method calls the quickselect to calculate the median of the n/5 medians of each 5-element group.

Another popular one is the eval-apply method for compiling an s-expression in Scheme, the following implementation from Matt Might:

 eval takes an expression and an environment to a value
(define (eval e env) (cond
  ((symbol? e)       (cadr (assq e env)))
  ((eq? (car e) 'λ)  (cons e env))
  (else              (apply (eval (car e) env) (eval (cadr e) env)))))

; apply takes a function and an argument to a value
(define (apply f x)
  (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))

; read and parse stdin, then evaluate:
(display (eval (read) '())) (newline)