Are there any example of Mutual recursion?

Question

Are there any example for a recursive function that call an other one which calls the first one too ?

example

function1()
{    
    //do something 
    f2();
    //do something
}

function2()
{
    //do something 
    f1();
    //do something
}

Answer 1

It's a bit contrived and not very efficient, but you could do this with a function to calculate Fibbonacci numbers as in:

fib2(n) { return fib(n-2); }

fib1(n) { return fib(n-1); }

fib(n)
{
  if (n>1)
    return fib1(n) + fib2(n);
  else
    return 1;
}

In this case its efficiency can be dramatically enhanced if the language supports memoization

Answer 2

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.

Answer 3

An example might be the minmax algorithm commonly used in game programs such as chess. Starting at the top of the game tree, the goal is to find the maximum value of all the nodes at the level below, whose values are defined as the minimum of the values of the nodes below that, whose values are defines as the maximum of the values below that, whose values ...

Answer 4

In a language with proper tail calls, Mutual Tail Recursion is a very natural way of implementing automata.

Answer 5

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 )