互递归

维基百科，自由的百科全书

互递归是数学与计算机科学中一种递归，指两个数学或计算机对象如函数或数据类型互相定义。[1]互递归在函數程式語言或某些问题域中非常常见，如递归下降分析器（英语：recursive descent parser），其中数据类型是自然地互相递归定义的。

例子[编辑]

数据类型[编辑]

更多信息：递归数据类型

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

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

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

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

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

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

在Standard ML，树与森林可互递归定义如下，允许空树：[2] 

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

计算机函数[编辑]

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

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

基本例子[编辑]

一个例子用于确定奇偶数。[3] 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. 这个例子是相互单递归（英语：single recursion），很容易改写为迭代。这个例子中的互递归是尾调用，尾调用优化是必须的以能在常量大小栈空间完成计算。C语言这要求O(n)栈空间，除非重写用跳转代替调用。[4]

Python语言实现树的例子: 

 def f_tree(tree):
     f_value(tree.value)
     f_forest(tree.children)

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

高级例子[编辑]

递归下降解析器可以自然地实现为每个产生式规则（英语：Production (computer science)）对应一个函数，就可以是互递归、多递归，因为产生式规则一般要组合多个部分。

互递归也可以实现有限状态机，每个函数表示一个状态，这要求尾递归优化因为状态变迁可能是非常大或无限的。互递归可用于合作多任务（英语：cooperative multitasking），以代替协程。

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

数学函数[编辑]

数学上，Hofstadter Female and Male sequences（英语：Hofstadter Female and Male sequences）是一对整数序列用互递归方式定义的例子。

分形可用递归函数计算。有时用互递归计算更为精致，如Sierpiński curve（英语：Sierpiński curve）。

流行性[编辑]

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

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

If you have two mutually-recursive functions that both alter the state of an object, try to move almost all the functionality into just one of the functions. Otherwise you will probably end up duplicating code.

术语[编辑]

互递归也称间接递归（英语：indirect recursion），与直接递归（英语：direct recursion）相对。

转换为直接递归[编辑]

数学上，一套互递归函数是原始递归函数, 可通过course-of-values recursion（英语：course-of-values recursion）证明,[6] 构造单个函数F依次列出单个递归函数的值: ，重写互递归为原始递归。

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

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

参见[编辑]

参考文献[编辑]

  1. ^ Manuel Rubio-Sánchez, Jaime Urquiza-Fuentes,Cristóbal Pareja-Flores (2002), 'A Gentle Introduction to Mutual Recursion', Proceedings of the 13th annual conference on Innovation and technology in computer science education, June 30–July 2, 2008, Madrid, Spain.
  2. ^ Harper 2000，"Date Types".
  3. ^ Hutton 2007，6.5 Mutual recursion, pp. 53–55.
  4. ^ "Mutual Tail-Recursion （页面存档备份，存于互联网档案馆）" and "Tail-Recursive Functions （页面存档备份，存于互联网档案馆）", A Tutorial on Programming Features in ATS （页面存档备份，存于互联网档案馆）, Hongwei Xi, 2010
  5. ^ Solving Every Sudoku Puzzle. [2017-12-01]. （原始内容存档于2020-11-15）. 
  6. ^ "mutual recursion （页面存档备份，存于互联网档案馆）", PlanetMath
  7. ^ On the Conversion of Indirect to Direct Recursion by Owen Kaser, C. R. Ramakrishnan, and Shaunak Pawagi at State University of New York, Stony Brook (1993)
  8. ^ Reynolds, John. Definitional Interpreters for Higher-Order Programming Languages (PDF). Proceedings of the ACM Annual Conference. Boston, Massachusetts: 717–740. August 1972 [2017-12-01]. （原始内容存档 (PDF)于2011-06-29）. 

外部链接[编辑]

取自“https://zh.wikipedia.org/w/index.php?title=互递归&oldid=75521905”