Are there any example of Mutual recursion?

Question

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

Example :

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

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

Olivia

You just provided one :) unless you meant real life example? – Blurb

The general term is “mutual recursion”, and yeah, there are many, many cases where the calls made by a function would be likely to cause a nested call into that function. – Bathesda

Answer 1

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 )

Boger

+1, I was thinking about this, too. In fact, using mutual tail recursion to implement automata is just a special case of a tail recursive descent parser, which in turn is a variant of a recursive descent parser. – Sacaton

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.

Evoke

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 ...

Conjuncture

Answer 4

I can think of two common sources of mutual recursion.

Functions dealing with mutually recursive types

Consider an Abstract Syntax Tree (AST) that keeps position information in every node. The type might look like this:

type Expr =
  | Int of int
  | Var of string
  | Add of ExprAux * ExprAux
and ExprAux = Expr of int * Expr

The easiest way to write functions that manipulate values of these types is to write mutually recursive functions. For example, a function to find the set of free variables:

let rec freeVariables = function
  | Int n -> Set.empty
  | Var x -> Set.singleton x
  | Add(f, g) -> Set.union (freeVariablesAux f) (freeVariablesAux g)
and freeVariablesAux (Expr(loc, e)) =
  freeVariables e

State machines

Consider a state machine that is either on, off or paused with instructions to start, stop, pause and resume (F# code):

type Instruction = Start | Stop | Pause | Resume

The state machine might be written as mutually recursive functions with one function for each state:

type State = State of (Instruction -> State)

let rec isOff = function
  | Start -> State isOn
  | _ -> State isOff
and isOn = function
  | Stop -> State isOff
  | Pause -> State isPaused
  | _ -> State isOn
and isPaused = function
  | Stop -> State isOff
  | Resume -> State isOn
  | _ -> State isPaused

Link

Answer 5

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

Sorrow

Mutual Recursion is not the same as Double Recursion, the question describes Mutual Recursion. Any mutually recursive set of functions can be unrolled into a single recursive function simply by inlining the code. – Evoke

You've fixed it now, my comment looks out of place! – Evoke

@Geoff: No problem... I got a little carried away and started writing stuff without thinking. – Sorrow

Answer 6

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

Fulvi

Answer 7

Here is my coded solution. For a calculator app that performs *,/,- operations using mutual recursion. It also checks for brackets (()) to decide the order of precedence.

Flow:: expression -> term -> factor -> expression 

    Calculator.h
    #ifndef CALCULATOR_H_
    #define CALCULATOR_H_

    #include <string>
    using namespace std;

    /****** A Calculator Class holding expression, term, factor ********/
    class Calculator
    {
    public:
        /**Default Constructor*/
        Calculator();

        /** Parameterized Constructor common for all exception
         * @aparam e exception value
         * */
        Calculator(char e);

        /**
         * Function to start computation
         * @param input - input expression*/
        void start(string input);

        /**
         * Evaluates Term*
         * @param input string for term*/
        double term(string& input);

         /* Evaluates factor*
         * @param input string for factor*/
        double factor(string& input);

         /* Evaluates Expression*
          * @param input string for expression*/
        double expression(string& input);


         /* Evaluates number*
          * @param input string for number*/
        string number(string n);

        /**
         * Prints calculates value of the expression
         * */
        void print();

        /**
         * Converts char to double
         * @param c input char
         * */
        double charTONum(const char* c);

        /**
         * Get error
         */
        char get_value() const;
        /** Reset all values*/
        void reset();
    private:
        int lock;//set lock to check extra parenthesis
        double result;// result
        char error_msg;// error message
    };

    /**Error for unexpected string operation*/
    class Unexpected_error:public Calculator
    {
    public:
        Unexpected_error(char e):Calculator(e){};
    };

    /**Error for missing parenthesis*/
    class Missing_parenthesis:public Calculator
    {
    public:
        Missing_parenthesis(char e):Calculator(e){};
    };

    /**Error if divide by zeros*/
    class DivideByZero:public Calculator{
    public:
        DivideByZero():Calculator(){};
    };
    #endif
    ===============================================================================

    Calculator.cpp

    //============================================================================
    // Name        : Calculator.cpp
    // Author      : Anurag
    // Version     :
    // Copyright   : Your copyright notice
    // Description : Calculator using mutual recursion in C++, Ansi-style
    //============================================================================

    #include "Calculator.h"
    #include <iostream>
    #include <string>
    #include <math.h>
    #include <exception>
    using namespace std;


    Calculator::Calculator():lock(0),result(0),error_msg(' '){

    }

    Calculator::Calculator(char e):result(0), error_msg(e) {

    }

    char Calculator::get_value() const {
        return this->error_msg;
    }

    void Calculator::start(string input) {
        try{
        result = expression(input);
        print();
        }catch (Unexpected_error e) {
            cout<<result<<endl;
            cout<<"***** Unexpected "<<e.get_value()<<endl;
        }catch (Missing_parenthesis e) {
            cout<<"***** Missing "<<e.get_value()<<endl;
        }catch (DivideByZero e) {
            cout<<"***** Division By Zero" << endl;
        }
    }

    double Calculator::expression(string& input) {
        double expression=0;
        if(input.size()==0)
            return 0;
        expression = term(input);
        if(input[0] == ' ')
            input = input.substr(1);
        if(input[0] == '+') {
            input = input.substr(1);
            expression += term(input);
        }
        else if(input[0] == '-') {
            input = input.substr(1);
            expression -= term(input);
        }
        if(input[0] == '%'){
            result = expression;
            throw Unexpected_error(input[0]);
        }
        if(input[0]==')' && lock<=0 )
            throw Missing_parenthesis(')');
        return expression;
    }

    double Calculator::term(string& input) {
        if(input.size()==0)
            return 1;
        double term=1;
        term = factor(input);
        if(input[0] == ' ')
            input = input.substr(1);
        if(input[0] == '*') {
            input = input.substr(1);
            term = term * factor(input);
        }
        else if(input[0] == '/') {
            input = input.substr(1);
            double den = factor(input);
            if(den==0) {
                throw DivideByZero();
            }
            term = term / den;
        }
        return term;
    }

    double Calculator::factor(string& input) {
        double factor=0;
        if(input[0] == ' ') {
            input = input.substr(1);
        }
        if(input[0] == '(') {
            lock++;
            input = input.substr(1);
            factor = expression(input);
            if(input[0]==')') {
                lock--;
                input = input.substr(1);
                return factor;
            }else{
                throw Missing_parenthesis(')');
            }
        }
        else if (input[0]>='0' && input[0]<='9'){
            string nums = input.substr(0,1) + number(input.substr(1));
            input = input.substr(nums.size());
            return stod(nums);
        }
        else {
            result = factor;
            throw Unexpected_error(input[0]);
        }
        return factor;
    }

    string Calculator::number(string input) {
        if(input.substr(0,2)=="E+" || input.substr(0,2)=="E-" || input.substr(0,2)=="e-" || input.substr(0,2)=="e-")
            return input.substr(0,2) + number(input.substr(2));
        else if((input[0]>='0' && input[0]<='9') || (input[0]=='.'))
            return input.substr(0,1) + number(input.substr(1));
        else
            return "";
    }

    void Calculator::print() {
        cout << result << endl;
    }

    void Calculator::reset(){
        this->lock=0;
        this->result=0;
    }
    int main() {

        Calculator* cal = new Calculator;
        string input;
        cout<<"Expression? ";
        getline(cin,input);
        while(input!="."){
            cal->start(input.substr(0,input.size()-2));
            cout<<"Expression? ";
            cal->reset();
            getline(cin,input);
        }
        cout << "Done!" << endl;
        return 0;
    }
    ==============================================================
    Sample input-> Expression? (42+8)*10 =
    Output-> 500

Gerrygerrymander

Answer 8

Top down merge sort can use a pair of mutually recursive functions to alternate the direction of merge based on level of recursion.

For the example code below, a[] is the array to be sorted, b[] is a temporary working array. For a naive implementation of merge sort, each merge operation copies data from a[] to b[], then merges b[] back to a[], or it merges from a[] to b[], then copies from b[] back to a[]. This requires n · ceiling(log2(n)) copy operations. To eliminate the copy operations used for merging, the direction of merge can be alternated based on level of recursion, merge from a[] to b[], merge from b[] to a[], ..., and switch to in place insertion sort for small runs in a[], as insertion sort on small runs is faster than merge sort.

In this example, MergeSortAtoA() and MergeSortAtoB() are the mutually recursive functions.

Example java code:

    static final int ISZ = 64;              // use insertion sort if size <= ISZ

    static void MergeSort(int a[])
    {
        int n = a.length;
        if(n < 2)
            return;
        int [] b = new int[n];
        MergeSortAtoA(a, b, 0, n);
    }
    
    static void MergeSortAtoA(int a[], int b[], int ll, int ee)
    {
        if ((ee - ll) <= ISZ){              // use insertion sort on small runs
            InsertionSort(a, ll, ee);
            return;
        }
        int rr = (ll + ee)>>1;              // midpoint, start of right half
        MergeSortAtoB(a, b, ll, rr);
        MergeSortAtoB(a, b, rr, ee);
        Merge(b, a, ll, rr, ee);            // merge b to a
    }
    
    static void MergeSortAtoB(int a[], int b[], int ll, int ee)
    {
        int rr = (ll + ee)>>1;              // midpoint, start of right half
        MergeSortAtoA(a, b, ll, rr);
        MergeSortAtoA(a, b, rr, ee);
        Merge(a, b, ll, rr, ee);            // merge a to b
    }
    
    static void Merge(int a[], int b[], int ll, int rr, int ee)
    {
        int o = ll;                         // b[]       index
        int l = ll;                         // a[] left  index
        int r = rr;                         // a[] right index
    
        while(true){                        // merge data
            if(a[l] <= a[r]){               // if a[l] <= a[r]
                b[o++] = a[l++];            //   copy a[l]
                if(l < rr)                  //   if not end of left run
                    continue;               //     continue (back to while)
                while(r < ee){              //   else copy rest of right run
                    b[o++] = a[r++];
                }
                break;                      //     and return
            } else {                        // else a[l] > a[r]
                b[o++] = a[r++];            //   copy a[r]
                if(r < ee)                  //   if not end of right run
                    continue;               //     continue (back to while)
                while(l < rr){              //   else copy rest of left run
                    b[o++] = a[l++];
                }
                break;                      //     and return
            }
        }
    }

    static void InsertionSort(int a[], int ll, int ee)
    {
        int i, j;
        int t;
        for (j = ll + 1; j < ee; j++) {
            t = a[j];
            i = j-1;
            while(i >= ll && a[i] > t){
                a[i+1] = a[i];
                i--;
            }
            a[i+1] = t;
        }   
    }

Quip

I'd be glad to uv, if you'd add some hints as to why the alternation is / could be needed. :) – Speed

I don't read Java freely. is your technique related to this or is it just about the length being something like 2^n+1 ? IOW what is the problem it is solving? – Speed

@WillNess - I updated my answer to include an explanation, and added insertion sort for small runs in the example code. – Quip

ok thanks. but when you merge from b[] to a[], the array b[] is still traversed left-to-right? I thought "direction" mean changing the traversal's direction. – Speed

@WillNess - Yes, the elements needs to be processed left to right for the merge sort to be stable. As for alternating direction of merge: one direction would move and merge elements from a[] to b[], and the other direction would move and merge elements from b[] to a[], without any copy step before or after a merge. – Quip