互递归

互递归是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。互递归在函數程式語言或某些问题域中非常常见，如，其中数据类型是自然地互相递归定义的。

例子

数据类型

采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）:
 f: [t[1], ..., t[k]]
 t: v f
森林f由一棵树的列表组成，同时一棵树t由一对：值v与森林f (子树)构成。这种定义是精致的，易于工作的抽象性（如用于证明关于树的属性的定理），因为它用简单术语表示一棵树：一个类型的列表，两个类型组成的一对。而且它匹配许多关于树的算法，这些对值做一些事，对子树做另外一些事。 

这种互递归定义可以转换为单个递归，这是通过森林定义内部化：
 t: v [t[1], ..., t[k]]
一颗树t包含一对：值v与子树的列表。这个定义更紧致，但是更难以处理：一棵树是一种类型的值与另一种类型的列表组成的一对，这要求解析开以证明结果。 

在Standard ML，树与森林可互递归定义如下，允许空树：
datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

计算机函数
如同在递归数据类型上的算法可以自然由递归函数给出，互递归数据结构上的算法可自然地由互递归函数给出。常见例子包括树与递归下降解析器。如同直接递归，对递归深度很大或者是无穷的情形尾调用优化是必须的，如使用互递归的多任务。注意一般的尾调用优化比作为特例情况的尾递归调用优化更难实现，因此有效实现互尾递归未被很多语言考虑。对Pascal语言要求先声明后使用，互递归要求前向声明。

如同直接递归函数，包装函数（wrapper function）对互递归函数是有用的作为包装函数的作用域内的（如果支持的话）。这对跨多个函数共享状态而不直接传递参数特别有用。

基本例子
一个例子用于确定奇偶数。 C语言：
bool is_even(unsigned int n) {
    if (n == 0)
        return true;
    else
        return is_odd(n - 1);
}

bool is_odd(unsigned int n) {
    if (n == 0)
        return false;
    else
        return is_even(n - 1);
}

这套函数是基于对问题4是偶数?等价于3是奇数?，依次等价于2是偶数?，直到0. 这个例子是相互，很容易改写为迭代。这个例子中的互递归是尾调用，尾调用优化是必须的以能在常量大小栈空间完成计算。C语言这要求O(n)栈空间，除非重写用跳转代替调用。 

Python语言实现树的例子:
 def f_tree(tree):
     f_value(tree.value)
     f_forest(tree.children)

 def f_forest(forest):
     for tree in forest:
         f_tree(tree)

高级例子
递归下降解析器可以自然地实现为每个对应一个函数，就可以是互递归、多递归，因为产生式规则一般要组合多个部分。 

互递归也可以实现有限状态机，每个函数表示一个状态，这要求尾递归优化因为状态变迁可能是非常大或无限的。互递归可用于，以代替协程。 

有些算法自然地分成两个阶段，如minimax算法，每个阶段可以用一个函数实现。

数学函数
数学上，是一对整数序列用互递归方式定义的例子。 

分形可用递归函数计算。有时用互递归计算更为精致，如。

流行性
互递归在函數程式語言风格中是常用的，如Lisp, Scheme, ML语言等。Prolog中互递归是不可避免。 

彼德·諾米格不提倡使用互递归：

术语
互递归也称，与相对。

转换为直接递归 
数学上，一套互递归函数是原始递归函数, 可通过证明, 构造单个函数F依次列出单个递归函数的值: ，重写互递归为原始递归。 

任何两个过程之间的互递归可以转换为直接递归，这通过把一个过程内联至另一个过程实现。   

任何数量的互递归过程可以合并为单一过程，这通过标签联合 (一种代数数据类型)表示选择过程与它的参数。这可以看作的有限应用.

参见 
 递归 (计算机科学)

参考文献

外部链接 
 Mutual recursion at Rosetta Code
 "Example demonstrating good use of mutual recursion", "Are there any example of Mutual recursion?", Stack Overflow
 
递归论
递归