互递归

在数学和计算机科学中，相互递归是递归的一种形式，其中两个数学或计算对象（例如函数或数据类型）是根据彼此定义的。 互递归在函数式编程和一些问题领域中非常常见，例如递归下降解析器，其中数据类型自然是相互递归的。

可以通过相互递归定义的数据类型的最重要的基本示例是树，它可以根据森林（树的列表）相互递归定义。

森林 f 由一列树组成，而树 t 由一对值 v 和森林 f（它的孩子）组成。 这个定义优雅且易于抽象地使用（例如在证明关于树的属性的定理时），因为它用简单的术语表达了一棵树：一种类型的列表和两种类型的一对。 此外，它匹配树上的许多算法，包括对值做一件事，对孩子做另一件事。

通过内联森林的定义，可以将此相互递归定义转换为单递归定义：

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

树 t 由一对值 v 和树列表（其子树）组成。 这个定义更紧凑，但有点混乱：一棵树由一对一种类型和另一种类型的列表组成，这需要解开来证明结果。

在标准 ML 中，树和森林数据类型可以相互递归定义如下，允许空树：

数据类型’一棵树=空| ‘a * ‘a forestand ‘a forest 的节点 = Nil | ‘一棵树 * ‘一片森林的缺点

正如递归数据类型的算法可以自然地由递归函数给出，相互递归数据结构的算法可以自然地由相互递归函数给出。 常见的例子包括树上的算法和递归下降解析器。 与直接递归一样，如果递归深度很大或无界，则尾调用优化是必要的，例如使用相互递归进行多任务处理。 请注意，尾调用优化通常（当调用的函数与原始函数不同时，如在尾递归调用中）可能比尾递归调用优化的特殊情况更难实现，因此高效实现 仅优化尾递归调用的语言可能不存在相互尾递归。 在 Pascal 等需要在使用前声明的语言中，相互递归函数需要前向声明，因为在定义它们时无法避免前向引用。

与直接递归函数一样，包装函数可能很有用，如果支持，则将相互递归函数定义为其范围内的嵌套函数。 这对于在一组函数之间共享状态而不必在它们之间传递参数特别有用。

互递归的一个标准示例（公认是人为的）通过定义两个相互调用的独立函数来确定非负数是偶数还是奇数，每次递减 1。

这些函数都是基于观察题是4偶？ 等价于 3 odd?，它又等价于 2 even?，依此类推直到 0。这个例子是相互单递归，可以很容易地用迭代代替。 在此示例中，相互递归调用是尾调用，并且尾调用优化对于在常量堆栈空间中执行是必要的。 在 C 中，这将占用 O(n) 堆栈空间，除非重写为使用跳转而不是调用。 这可以简化为单个递归函数 is_even。 在这种情况下，可以内联的 is_odd 会调用 is_even，但 is_even 只会调用自身。

作为更一般的一类示例，树上的算法可以分解为它对一个值的行为和它对孩子的行为，并且可以分成两个相互递归的函数，一个指定树上的行为，调用森林 子森林的函数，以及指定森林行为的函数，为森林中的树调用树函数。

def f_tree（树）-> 无：f_value(tree.value) f_forest(tree.children)def f_forest(forest) -> 无：对于森林中的树：f_tree(tree)

在这种情况下，树函数通过单次递归调用森林函数，但森林函数通过多次递归调用树函数。

使用上面的标准 ML 数据类型，可以通过以下相互递归函数计算树的大小（节点数）