更改

递归 (查看源代码)

2022年3月15日 (二) 16:06的版本

删除688字节、 2022年3月15日 (二) 16:06

无编辑摘要

第12行：第12行：

| chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html

| chapter=1: Recurrent Problems

−

}}</ref>这种问题一般可以通过迭代来解决，但这需要在编程时识别和索引较小的问题实例。递归通过使用从自己的代码中调用自己的函数来解决这种'''~~~~ 递归问题 recursive problem~~~~'''。这种方法可以应用于许多类型的问题，于是递归成为了计算机科学的核心思想之一。<ref>{{cite book

+

}}</ref>这种问题一般可以通过迭代来解决，但这需要在编程时识别和索引较小的问题实例。递归通过使用从自己的代码中调用自己的函数来解决这种''' 递归问题 recursive problem'''。这种方法可以应用于许多类型的问题，于是递归成为了计算机科学的核心思想之一。<ref>{{cite book

|author-last = Epp

|author-first = Susanna

第29行：第29行： −

大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些'''~~~~ 函数式编程语言 functional programming language~~~~'''(例如Clojure<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref>)不定义任何循环结构，而只依赖递归来重复调用代码。在'''~~~~可计算性理论 computability theory~~~~'''中证明了这些递归语言是'''~~~~图灵完备 Turing complete ~~~~'''这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(可以用于解决相同的问题)。

+

大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些''' 函数式编程语言 functional programming language'''(例如Clojure<ref>{{Cite web|title=Functional Programming {{!}} Clojure for the Brave and True|url=https://www.braveclojure.com/functional-programming/#Recursion_Instead_of_for_while|access-date=2020-10-21|website=www.braveclojure.com}}</ref>)不定义任何循环结构，而只依赖递归来重复调用代码。在'''可计算性理论 computability theory'''中证明了这些递归语言是'''图灵完备 Turing complete '''这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(可以用于解决相同的问题)。

第37行：第37行：

==递归函数和算法==

−

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

+

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

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

−

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

+

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

−

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

+

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

==递归数据类型==

−

许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。'''~~~~ 自引用self-referential~~~~'''定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。

+

许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。''' 自引用self-referential'''定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。

===归纳定义的数据===

第57行：第57行：

上面的代码指定了一个字符串列表，要么是空的，要么是包含一个字符串和一个字符串列表的结构。定义中的自引用允许构建任意（有限）数量的字符串列表。

−

归纳定义的另一个例子是'''~~~~自然数 natural numbers~~~~'''（或正整数）：

+

归纳定义的另一个例子是'''自然数 natural numbers'''（或正整数）：

<pre>一个自然数是1或 n + 1，其中 n 是一个自然数。</pre>

−

类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用'''~~~~ BNF： Backus–Naur form~~~~''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：

+

类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用''' BNF： Backus–Naur form''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：

第83行：第83行：

这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数的头<code>head</code>和尾<code>tail</code>以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。

−

共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''惰性编程语言 lazy programming language~~~~'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。

+

共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''惰性编程语言 lazy programming language'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。

==递归的类型==

第91行：第91行： −

只包含单个自引用的递归称为'''~~~~ 单重递归 single recursion~~~~'''，而包含多个自引用的递归称为'''~~~~ 多重递归 multiple recursion~~~~'''。单重递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多重递归的标准例子包括'''~~~~ 树遍历tree traversal~~~~'''，如深度优先搜索。

+

只包含单个自引用的递归称为''' 单重递归 single recursion'''，而包含多个自引用的递归称为''' 多重递归 multiple recursion'''。单重递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多重递归的标准例子包括''' 树遍历tree traversal'''，如深度优先搜索。

单重递归的效率往往比多重递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多重递归则可能需要指数级的时间和空间，而且递归得更根本更彻底，在没有明确的堆栈的情况下，不能用迭代来代替。

第148行：第148行：

大多数递归的基本例子，以及这里介绍的大多数例子，都是直接递归，即一个函数调用自己。间接递归是指一个函数不是被它自己调用，而是被它调用的另一个函数（直接或间接）调用。例如，如果f调用f，那是直接递归，但如果f调用g，而g又调用f，那就是f的间接递归。三个或更多的函数链是可能的，例如，函数1调用函数2，函数2调用函数3，函数3再调用函数1。

−

间接递归也叫'''~~~~互递归 mutual recursion~~~~'''，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。

+

间接递归也叫'''互递归 mutual recursion'''，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。

===匿名递归===

−

递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为'''~~~~ 匿名递归 anonymous recursion~~~~'''。

+

递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为''' 匿名递归 anonymous recursion'''。

下面是计算斐波那契数列第10项的javascript代码，通过匿名递归实现。

第465行：第465行： −

'''~~~~ 汉诺塔 Towers of Hanoi ~~~~'''是一个数学难题，它的解法说明了递归的思想<ref>Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi</ref><ref>Epp 1995, pp. 427–430: The Tower of Hanoi</ref>。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？

+

''' 汉诺塔 Towers of Hanoi '''是一个数学难题，它的解法说明了递归的思想<ref>Graham, Knuth & Patashnik 1990, §1.1: The Tower of Hanoi</ref><ref>Epp 1995, pp. 427–430: The Tower of Hanoi</ref>。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？

第555行：第555行：

====二分搜索====

−

'''~~~~ 二分搜索 binary search~~~~'''算法是通过每次递归将数组切成两半来搜索''有序''数组中某个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后产生三种可能之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。

+

''' 二分搜索 binary search'''算法是通过每次递归将数组切成两半来搜索''有序''数组中某个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后产生三种可能之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。

第756行：第756行：

</syntaxhighlight>

−

这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 ''' 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。~~~~'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。

+

这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 ''' 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。

==实现问题==

第763行：第763行：

* 包装器函数（在顶部）

−

* 短路到基本情况，也就是 '''远程递归 Arm's-length recursion~~~~'''（在底部）

+

* 短路到基本情况，也就是 '''远程递归 Arm's-length recursion'''（在底部）

* 混合算法（在底部）——一旦数据足够小，就切换到另一个的算法

第772行：第772行： −

'''~~~~ 包装器函数 wrapper function~~~~'''是指被直接调用但本身不递归的函数，而是调用一个单独的辅助函数，由这个辅助函数实际上进行递归。

+

''' 包装器函数 wrapper function'''是指被直接调用但本身不递归的函数，而是调用一个单独的辅助函数，由这个辅助函数实际上进行递归。

第802行：第802行： −

在二叉树的'''~~~~ 深度优先搜索 depth-first search~~~~'''（DFS）中给出了一个短路的基本例子。

+

在二叉树的''' 深度优先搜索 depth-first search'''（DFS）中给出了一个短路的基本例子。

DFS的标准递归算法是：

第861行：第861行：

===混合算法===

−

由于重复的函数调用和返回，递归算法对于小规模数据往往效率不高。出于这个原因，递归算法的高效实现往往是先实现一个标准递归算法，但当输入变小时，再切换到不同的算法。一个重要的例子是归并排序，当数据足够小的时候，常常通过切换到非递归的插入排序来实现，如'''~~~~平铺合并排序 tiled merge sort~~~~'''。混合递归算法往往可以进一步完善，如Timsort中，就是由混合归并排序/插入排序派生出来的。

+

由于重复的函数调用和返回，递归算法对于小规模数据往往效率不高。出于这个原因，递归算法的高效实现往往是先实现一个标准递归算法，但当输入变小时，再切换到不同的算法。一个重要的例子是归并排序，当数据足够小的时候，常常通过切换到非递归的插入排序来实现，如'''平铺合并排序 tiled merge sort'''。混合递归算法往往可以进一步完善，如Timsort中，就是由混合归并排序/插入排序派生出来的。

==递归 VS 迭代==

第1,003行：第1,003行：

−

递归算法的'''~~~~ 时间效率 time efficiency ~~~~'''可以用关于大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。

+

递归算法的''' 时间效率 time efficiency '''可以用关于大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。

===捷径规则（主定理）===

薄荷

7,129

个编辑

更改

递归 (查看源代码)

2022年3月15日 (二) 16:06的版本

导航菜单

搜索