有没有相互递归的例子?

相互递归在解析数学表达式(和其他语法)的代码中很常见。基于以下语法的递归下降解析器自然包含相互递归: 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 )

恰当的术语是相互递归。

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

在那个页面上有一个例子,我将在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);
}

其中abs(n)表示返回一个数的绝对值。

显然,这并不是有效的,只是为了证明一点。

例如,在象棋等游戏程序中常用的minmax算法。从游戏树的顶部开始,目标是找到 最大限度 下面级别上所有节点的值,其值定义为 最低限度 其值定义为 最大限度 下面的值,其值…

我可以想到两个共同的递归源。

处理相互递归类型的函数

考虑一个抽象语法树(ast),它在每个节点中保存位置信息。类型可能如下所示:

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

编写操作这些类型值的函数的最简单方法是编写相互递归的函数。例如,用于查找自由变量集的函数:

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

状态机

考虑一个状态机,它可以打开、关闭或暂停,并带有启动、停止、暂停和恢复指令(F代码):

type Instruction = Start | Stop | Pause | Resume

状态机可以写成相互递归的函数,每个状态有一个函数:

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

它有点做作,效率也不是很高,但是您可以使用函数计算fibbonacci数,如下所示:

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;
}

在这种情况下,如果语言支持 memoization

在具有适当尾部调用的语言中,相互尾部递归是实现自动机的一种非常自然的方法。

这是我的密码解决方案。对于一个执行 * , / , - 使用相互递归的操作。它还检查括号( () )决定优先顺序。

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