更改

递归 (查看源代码)

2020年12月27日 (日) 22:59的版本

删除4,497字节、 2020年12月27日 (日) 22:59

→‎递归函数和算法

第44行：第44行：

==递归函数和算法==

−

A common [[computer programming]] tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the [[divide-and-conquer method]]; when combined with a [[lookup table]] that stores the results of solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as [[dynamic programming]] or [[memoization]].

−

A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method; when combined with a lookup table that stores the results of solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as dynamic programming or memoization.

一种常用的计算机编程策略是将一个问题划分为与原问题相同类型的子问题，解决这些子问题，并将结果合并。这通常被称为''' 分治法 divede-and-conquer'''；在此基础上，加上一个存储子问题结果的查找表时（以避免重复解子问题而产生额外的计算时间），就产生了称为''' 动态规划dynamic programming '''或''' 记忆化 memoization'''的方法。

−

A recursive function definition has one or more ''base cases'', meaning input(s) for which the function produces a result [[Trivial (mathematics)|trivial]]ly (without recurring), and one or more ''recursive cases'', meaning input(s) for which the program recurs (calls itself). For example, the [[factorial]] function can be defined recursively by the equations {{math|1=0! = 1}} and, for all {{math|''n'' > 0}}, {{math|1=''n''! = ''n''(''n'' − 1)!}}. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

−

A recursive function definition has one or more base cases, meaning input(s) for which the function produces a result trivially (without recurring), and one or more recursive cases, meaning input(s) for which the program recurs (calls itself). For example, the factorial function can be defined recursively by the equations and, for all , . Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

递归函数的定义有一个或多个基本情况，函数对于输入参数只产生一个简单结果；以及一个或多个递归情况，表示程序对于输入参数进行递归(调用自身)。例如，阶乘函数可以通过等式{{math|1=0! = 1}}，对于所有{{math|''n'' > 0}}，{{math|1=''n''! = ''n''(''n'' − 1)!}}来递归定义。这两个方程本身都不构成一个完整的定义，第一个方程是基本情况，第二个方程是递归情况。因为基本情况打破了递归的链条，所以有时也被称为 “终止情况”。

−

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some [[Daemon (computer software)|system and server processes]]—are an exception to this.) Neglecting to write a base case, or testing for it incorrectly, can cause an [[infinite loop]].

−

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones. In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached. (Functions that are not intended to terminate under normal circumstances—for example, some system and server processes—are an exception to this.) Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.

递归情况的工作可以看作是将复杂的输入分解为更简单的输入。在一个设计得当的递归函数中，每一次递归调用，都要简化输入问题，使得最终必然达到基本情况。(在正常情况下不打算终止的函数（例如，一些系统和服务器进程）是这方面的例外)。忽略编写基本情况，或不正确地测试，可能会导致''' 无限循环 infinite loop'''。

−

For some functions (such as one that computes the [[series (mathematics)|series]] for {{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}}) there is not an obvious base case implied by the input data; for these one may add a [[parameter]] (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by [[corecursion]],{{how?|date=September 2020}} where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the ''n''th term (''n''th partial sum)".

−

For some functions (such as one that computes the series for {{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}} )there is not an obvious base case implied by the input data; for these one may add a parameter (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by corecursion, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".

一些函数（例如计算级数{{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}}）的输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个参数（比如在上面级数例子中，可以是需要计算的项的数量）来提供一个 "停止标准"，以建立基本情况。这个例子用''' 共递归corecursion'''来处理其实会更自然，每次后续输出的项就是前面所有项的和；而这可以通过使用索引参数表示“计算第n项(第n部分的和)”来转换为递归。

−

==递归数据类型==

思无涯咿呀咿呀

管理员

2,443

个编辑

更改

递归 (查看源代码)

2020年12月27日 (日) 22:59的版本

导航菜单

搜索