有相互递归的例子吗？

Question

是否有一个递归函数的例子,它调用另一个调用第一个函数的函数？

示例:

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

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

Answer 1

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

Answer 2

适当的术语是相互递归.

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)表示返回数字的绝对值.

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

Answer 3

一个例子可能是常用于诸如国际象棋之类的游戏程序中的minmax算法.在博弈树的顶部开始,我们的目标是找到最大的水平以下,其值定义为所有节点的值最小下面的节点,其值定义为值的最大的以下值,其值......

Answer 4

我可以想到相互递归的两个常见来源。

处理相互递归类型的函数

考虑在每个节点中保存位置信息的抽象语法树 (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