Are there any example of Mutual recursion?

Mutual recursion is common in code that parses mathematical expressions (and other grammars). A recursive descent parser based on the grammar below will naturally contain mutual recursion: expression-terms-term-factor-primary-expression.

expression
    + terms
    - terms
    terms

terms
    term + terms
    term - terms

term
    factor
    factor * term
    factor / term

factor
    primary
    primary ^ factor

primary
    ( expression )
    number
    name
    name ( expression )

The proper term for this is Mutual Recursion.

http://en.wikipedia.org/wiki/Mutual_recursion

There's an example on that page, I'll reproduce here in Java:

boolean even( int number )
{    
    if( number == 0 )
        return true;
    else
        return odd(abs(number)-1)
}

boolean odd( int number )
{
    if( number == 0 )
        return false;
    else
        return even(abs(number)-1);
}

Where abs( n ) means return the absolute value of a number.

Clearly this is not efficient, just to demonstrate a point.

Tags:

Recursion