370
个编辑
更改
跳到导航
跳到搜索
第213行：
第213行： − + − 递归的类型+ + + − ===Single recursion and multiple recursion=== − 单次递归和多次递归 − 只包含单个自引用的递归称为单次递归，而包含多个自引用的递归称为多次递归。单次递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多次递归的标准例子包括'''<font color="#ff8000"> 树遍历tree traversal</font>'''，如深度优先搜索。+ 第228行：
第228行： − 单次递归的效率往往比多次递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多次递归则可能需要指数级的时间和空间，而且更根本的是递归，在没有明确的堆栈的情况下，不能用迭代来代替。+ 第234行：
第234行： − 多次递归有时可以转换为单次递归（如果需要，再转换为迭代）。例如，虽然天真地计算斐波那契序列是多次迭代，因为每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单递归来计算。这更自然地被定义为共递归。从初始值开始建立，在每一步都跟踪两个连续的值—参见：共递归。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多次递归。+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
→Types of recursion
共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''<font color="#f668800">惰性编程语言 lazy programming language</font>'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。
共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''<font color="#f668800">惰性编程语言 lazy programming language</font>'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。
==Types of recursion==
==递归的类型==
===单重递归和多重递归===
Recursion that only contains a single self-reference is known as '''{{visible anchor|single recursion}}''', while recursion that contains multiple self-references is known as '''{{visible anchor|multiple recursion}}'''. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include [[tree traversal]], such as in a depth-first search.
Recursion that only contains a single self-reference is known as '''{{visible anchor|single recursion}}''', while recursion that contains multiple self-references is known as '''{{visible anchor|multiple recursion}}'''. Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include [[tree traversal]], such as in a depth-first search.
Recursion that only contains a single self-reference is known as , while recursion that contains multiple self-references is known as . Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.
Recursion that only contains a single self-reference is known as , while recursion that contains multiple self-references is known as . Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.
只包含单个自引用的递归称为'''<font color="#ff8000"> 单重递归 single recursion</font>'''，而包含多个自引用的递归称为'''<font color="#ff8000"> 多重递归 multiple recursion</font>'''。单重递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多重递归的标准例子包括'''<font color="#ff8000"> 树遍历tree traversal</font>'''，如深度优先搜索。
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.
单重递归的效率往往比多重递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多重递归则可能需要指数级的时间和空间，而且递归得更根本更彻底，在没有明确的堆栈的情况下，不能用迭代来代替。
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see [[Corecursion#Examples|corecursion: examples]]. A more sophisticated example is using a [[threaded binary tree]], which allows iterative tree traversal, rather than multiple recursion.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see [[Corecursion#Examples|corecursion: examples]]. A more sophisticated example is using a [[threaded binary tree]], which allows iterative tree traversal, rather than multiple recursion.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see corecursion: examples. A more sophisticated example is using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see corecursion: examples. A more sophisticated example is using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.
多重递归有时可以转换为单重递归（如果需要，再转换为迭代）。例如，虽然简单地计算斐波那契序列是一种多次迭代，因为算出每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单重递归来计算。这被定义为共递归会更自然。从初始值开始建立，在每一步都跟踪两个连续的值。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多重递归。
下面是计算斐波那契数列第n项得python代码，分别使用多重递归和单重递归实现。
--[[用户:Qige96|Ricky]]代码实现并未经过大量测试，可能会有bug，如发现请在微信群@我
<syntaxhighlight lang="python">
def fib_MR(n):
"Multiple Recursion computing the n-th Fibonacci term"
assert n > 0 and isinstance(n, int), "n must be a positive integer"
if n == 1:
return 0
elif n == 2:
return 1
else:
return fib_MR(n-1) + fib_MR(n-2)
def fib_SR(n):
"Single Recursion computing the n-th Fibonacci term"
assert n > 0 and isinstance(n, int), "n must be a positive integer"
def _fib_SR(n):
"reutnr the n-th and the (n-1)-th Fibonacci term"
if n == 2:
return 0, 1
elif n == 3:
return 1, 1
else:
An_1, An_2 = _fib_SR(n-1)
return An_2 + An_1, An_1
if n == 1:
return 0
elif n == 2:
return 1
else:
return _fib_SR(n)[0]
print([fib_MR(i) for i in range(1,11)])
print([fib_SR(i) for i in range(1,11)])
</syntaxhighlight>
===Indirect recursion===
===Indirect recursion===