互递归（mutual recursion），是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。互递归在函數程式語言或某些问题域中非常常见，如，其中数据类型是自然地互相递归定义的。
例子
数据类型
采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）:
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依次列出单个递归函数的值: F = f_1(0), f_2(0), f_1(1), f_2(1), \dots,，重写互递归为原始递归。
任何两个过程之间的互递归可以转换为直接递归，这通过把一个过程内联至另一个过程实现。
任何数量的互递归过程可以合并为单一过程，这通过标签联合 (一种代数数据类型)表示选择过程与它的参数。这可以看作的有限应用.
参见
- 递归 (计算机科学)
*
参考文献
*
*
*
外部链接
- [http://rosettacode.org/wiki/Mutual_recursion Mutual recursion] at Rosetta Code
- "[https://stackoverflow.com/questions/10295735/example-demonstrating-good-use-of-mutual-recursion Example demonstrating good use of mutual recursion]", "[https://stackoverflow.com/questions/2725038/are-there-any-example-of-mutual-recursion Are there any example of Mutual recursion?]", Stack Overflow
评论 (0)