查看“︁互递归”︁的源代码

'''互递归'''是数学与计算机科学中一种[[递归]]，指两个数学或计算机对象如函数或数据类型互相定义。<ref>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.</ref>互递归在[[函數程式語言]]或某些问题域中非常常见，如{{tsl|en|recursive descent parser|递归下降分析器}}，其中数据类型是自然地互相递归定义的。

==例子==

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

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

在[[Standard ML]]，树与森林可互递归定义如下，允许空树：{{sfn|Harper|2000|loc="[http://www.cs.cmu.edu/~rwh/introsml/core/datatypes.htm Date Types]"}}
<syntaxhighlight lang=ocaml>
datatype 'a tree = Empty | Node of 'a * 'a forest
and      'a forest = Nil | Cons of 'a tree * 'a forest
</syntaxhighlight>

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

如同直接递归函数，[[递归 (计算机科学)|包装函数]]（wrapper function）对互递归函数是有用的作为包装函数的作用域内的{{tsl|en|nested function|嵌套函数}}（如果支持的话）。这对跨多个函数共享状态而不直接传递参数特别有用。 

====基本例子====
一个例子用于确定奇偶数。{{sfn|Hutton|2007|loc=6.5 Mutual recursion, pp. [https://books.google.com/books?id=olp7lAtpRX0C&pg=PA53&dq=%22mutual+recursion%22 53–55]}} C语言：
<syntaxhighlight lang=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);
}
</syntaxhighlight>

这套函数是基于对问题''4是偶数?''等价于''3是奇数?''，依次等价于''2是偶数?''，直到0. 这个例子是相互{{tsl|en|single recursion|单递归}}，很容易改写为迭代。这个例子中的互递归是[[尾调用]]，尾调用优化是必须的以能在常量大小栈空间完成计算。C语言这要求''O''(''n'')栈空间，除非重写用跳转代替调用。<ref>"[http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/c244.html Mutual Tail-Recursion] {{Wayback|url=http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/c244.html |date=20160410041236 }}" and "[http://www.cs.bu.edu/~hwxi/ATS/TUTORIAL/contents/tail-recursive-functions.html Tail-Recursive Functions] {{Wayback|url=http://www.cs.bu.edu/~hwxi/ATS/TUTORIAL/contents/tail-recursive-functions.html |date=20160410041150 }}", ''[http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/book1.html A Tutorial on Programming Features in ATS] {{Wayback|url=http://www.cs.bu.edu/~hwxi/ATS/DOCUMENT/TUTORIALATS/HTML/book1.html |date=20171227015220 }},'' Hongwei Xi, 2010</ref> 

Python语言实现树的例子:
<syntaxhighlight lang=python>
 def f_tree(tree):
     f_value(tree.value)
     f_forest(tree.children)

 def f_forest(forest):
     for tree in forest:
         f_tree(tree)
</syntaxhighlight>   

====高级例子====
[[递归下降解析器]]可以自然地实现为每个{{tsl|en|Production (computer science)|产生式规则}}对应一个函数，就可以是互递归、多递归，因为产生式规则一般要组合多个部分。 

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

有些算法自然地分成两个阶段，如[[极小化极大算法|minimax算法]]，每个阶段可以用一个函数实现。 

===数学函数===
数学上，{{tsl|en|Hofstadter Female and Male sequences}}是一对整数序列用互递归方式定义的例子。 

分形可用递归函数计算。有时用互递归计算更为精致，如{{tsl|en|Sierpiński curve}}。

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

[[彼德·諾米格]]不提倡使用互递归：<ref>{{Cite web |url=http://norvig.com/sudoku.html |title=Solving Every Sudoku Puzzle |accessdate=2017-12-01 |archive-date=2020-11-15 |archive-url=https://web.archive.org/web/20201115192044/http://norvig.com/sudoku.html |dead-url=no }}</ref>
{{quote|text=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.}}

==术语==
互递归也称{{tsl|en|indirect recursion|间接递归}}，与{{tsl|en|direct recursion|直接递归}}相对。 

== 转换为直接递归 ==
数学上，一套互递归函数是[[原始递归函数]], 可通过{{tsl|en|course-of-values recursion}}证明,<ref>"[http://planetmath.org/mutualrecursion mutual recursion] {{Wayback|url=http://planetmath.org/mutualrecursion |date=20180621221349 }}", ''PlanetMath''</ref> 构造单个函数''F''依次列出单个递归函数的值: <math>F = f_1(0), f_2(0), f_1(1), f_2(1), \dots,</math>，重写互递归为原始递归。 

任何两个过程之间的互递归可以转换为直接递归，这通过把一个过程内联至另一个过程实现。 <ref>[http://delivery.acm.org/10.1145/180000/176510/p151-kaser.pdf?key1=176510&key2=1857140721&coll=GUIDE&dl=GUIDE&CFID=82873082&CFTOKEN=54657523 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)</ref>  

任何数量的互递归过程可以合并为单一过程，这通过[[标签联合]] (一种[[代数数据类型]])表示选择过程与它的参数。这可以看作{{tsl|en|defunctionalization}}的有限应用.<ref>{{cite conference
  | first = John
  | last = Reynolds
  | authorlink = John_C._Reynolds
  | title = Definitional Interpreters for Higher-Order Programming Languages
  | booktitle = Proceedings of the ACM Annual Conference
  | date = August 1972
  | location = Boston, Massachusetts
  | pages = 717–740
  | url = http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf
  | access-date = 2017-12-01
  | archive-date = 2011-06-29
  | archive-url = https://web.archive.org/web/20110629171917/http://www.brics.dk/~hosc/local/HOSC-11-4-pp363-397.pdf
  | dead-url = no
  }}</ref>   
== 参见 ==
* [[递归 (计算机科学)]]
* {{tsl|en|Circular dependency|循环依赖}}

== 参考文献==
{{Reflist}}
* {{citation|first=Robert|last=Harper|authorlink=Robert Harper (computer scientist)|url=http://www.cs.cmu.edu/~rwh/introsml/|title=Programming in Standard ML|year=2000|accessdate=2017-12-01|archive-date=2020-06-29|archive-url=https://web.archive.org/web/20200629000935/https://www.cs.cmu.edu/~rwh/introsml/|dead-url=no}}
* {{cite book |title=Simply Scheme: Introducing Computer Science |last1=Harvey |first1=Brian |last2=Wright |first2=Matthew |year=1999 |publisher=MIT Press |isbn=978-0-26208281-5 |ref=harv }}
* {{cite book |title=Programming in Haskell |url=https://archive.org/details/programminginhas0000hutt |last=Hutton |first=Graham |year=2007 |publisher=Cambridge University Press |isbn=978-0-52169269-4 |ref=harv }}

== 外部链接 ==
* [http://rosettacode.org/wiki/Mutual_recursion Mutual recursion]{{Wayback|url=http://rosettacode.org/wiki/Mutual_recursion |date=20201111224941 }} at [[Rosetta Code]]
* "[https://stackoverflow.com/questions/10295735/example-demonstrating-good-use-of-mutual-recursion Example demonstrating good use of mutual recursion]{{Wayback|url=https://stackoverflow.com/questions/10295735/example-demonstrating-good-use-of-mutual-recursion |date=20161011013429 }}", "[https://stackoverflow.com/questions/2725038/are-there-any-example-of-mutual-recursion Are there any example of Mutual recursion?]{{Wayback|url=https://stackoverflow.com/questions/2725038/are-there-any-example-of-mutual-recursion |date=20161011013320 }}", ''Stack Overflow''
 
[[Category:递归论]]
[[Category:递归]]