互递归

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

例子

数据类型

Template:Further 采取互递归定义的最重要的基本数据类型是树。这可以用于定义森林（树的列表）:

f: [t[1], ..., t[k]]
t: v f

森林f由一棵树的列表组成，同时一棵树t由一对：值v与森林f (子树)构成。这种定义是精致的，易于工作的抽象性（如用于证明关于树的属性的定理），因为它用简单术语表示一棵树：一个类型的列表，两个类型组成的一对。而且它匹配许多关于树的算法，这些对值做一些事，对子树做另外一些事。

这种互递归定义可以转换为单个递归，这是通过森林定义内部化：

t: v [t[1], ..., t[k]]

一颗树t包含一对：值v与子树的列表。这个定义更紧致，但是更难以处理：一棵树是一种类型的值与另一种类型的列表组成的一对，这要求解析开以证明结果。

在Standard ML，树与森林可互递归定义如下，允许空树：Template:Sfn

datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest

计算机函数

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

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

基本例子

一个例子用于确定奇偶数。Template:Sfn 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. 这个例子是相互Template:Tsl，很容易改写为迭代。这个例子中的互递归是尾调用，尾调用优化是必须的以能在常量大小栈空间完成计算。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)

高级例子

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

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

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

数学函数

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

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

流行性

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

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

术语

互递归也称Template:Tsl，与Template:Tsl相对。

转换为直接递归

数学上，一套互递归函数是原始递归函数, 可通过Template:Tsl证明, 构造单个函数F依次列出单个递归函数的值: $F=f_1(0),f_2(0),f_1(1),f_2(1),\dots ,$，重写互递归为原始递归。

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

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

参见

• 递归 (计算机科学)
• Template:Tsl

参考文献

• Template:Citation
• Template:Cite book
• Template:Cite book

外部链接

• Mutual recursionTemplate:Wayback at Rosetta Code
• "Example demonstrating good use of mutual recursionTemplate:Wayback", "Are there any example of Mutual recursion?Template:Wayback", Stack Overflow