递归 - 版本历史

薄荷：/* 实现问题 */

2022-03-15T08:08:39Z

实现问题

薄荷：/* 协归纳定义的数据和共递归 */

2022-03-15T08:07:33Z

协归纳定义的数据和共递归

2022年3月15日 (二) 08:06 薄荷

2022-03-15T08:06:59Z

显示更改

Qige96：/* 递归数据结构（结构化递归） */

2021-01-21T08:19:00Z

递归数据结构（结构化递归）

Qige96：/* 递归数据类型 */

2021-01-21T08:16:40Z

递归数据类型

Qige96：/* 递归函数和算法 */

2021-01-21T08:16:08Z

递归函数和算法

薄荷：/* 实现问题 */

2021-01-03T14:45:30Z

实现问题

思无涯咿呀咿呀：/* 编者推荐 */

2020-12-28T00:06:14Z

编者推荐

思无涯咿呀咿呀：/* 编者推荐 */

2020-12-28T00:05:51Z

编者推荐

思无涯咿呀咿呀：/* 集智课程推荐 */

2020-12-27T16:30:22Z

集智课程推荐

@@ 第766行： / 第766行： @@
 * 包装器函数（在顶部）
-* 短路到基本情况，也就是 '''<font color="#f668800">远程递归 Arm's-length recursion'''（在底部）
+* 短路到基本情况，也就是 '''远程递归 Arm's-length recursion'''（在底部）
 * 混合算法（在底部）——一旦数据足够小，就切换到另一个的算法

@@ 第71行： / 第71行： @@
 这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 <code> (5 * ((3 * 6) + 8)) </code> ，在一个表达式中有多个乘积或和运算。
 ===协归纳定义的数据和共递归===
@@ 第83行： / 第84行： @@
 这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数的头<code>head</code>和尾<code>tail</code>以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。
-共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''<font color="#f668800">惰性编程语言  lazy programming language'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。
+共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''惰性编程语言  lazy programming language'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。
 ==递归的类型==

@@ 第633行： / 第633行： @@
 递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。
 <blockquote>
 "当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"<ref>Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. p. 126. ISBN 978-0-13022418-7.</ref>
 </blockquote>
@@ 第645行： / 第641行： @@
 <blockquote>
 只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。
 </blockquote>
@@ 第661行： / 第655行： @@
 };
 </syntaxhighlight>
 由于''struct node''数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的''list_print''过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在''list_print''过程中保持不变。
@@ 第675行： / 第668行： @@
+}
 </syntaxhighlight>
 ====二叉树====
 下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。
@@ 第691行： / 第681行： @@
 };
 </syntaxhighlight>
 对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
@@ 第721行： / 第710行： @@
 上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。
 ====文件系统遍历====
@@ 第767行： / 第755行： @@
+}
 </syntaxhighlight>
 这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 '''<font color=''32CD32''> 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。

@@ 第46行： / 第46行： @@
 ==递归数据类型==
 许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。'''<font color="#ff8000"> 自引用self-referential</font>'''定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。
 ===归纳定义的数据===
 归纳定义是指定如何构造数据实例的定义。例如，字符串列表可以被归纳定义为（这里使用Haskell语法）：
 <syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>
 上面的代码指定了一个字符串列表，要么是空的，要么是包含一个字符串和一个字符串列表的结构。定义中的自引用允许构建任意（有限）数量的字符串列表。
 归纳定义的另一个例子是'''<font color="#ff8000">自然数 natural numbers</font>'''（或正整数）：
 <pre>一个自然数是1或 n + 1，其中 n 是一个自然数。</pre>
 类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用'''<font color="#ff8000"> BNF： Backus–Naur form</font>''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：
@@ 第80行： / 第70行： @@
 这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 <code> (5 * ((3 * 6) + 8)) </code> ，在一个表达式中有多个乘积或和运算。
 ===协归纳定义的数据和共递归===
 协归纳数据定义规定了可以对一段数据进行怎样的操作；通常，自引用的协归纳定义可以用于定义无限大小的数据结构。
 用共归纳定义法来定义无限大小的字符串流，一个可能的例子是这样的：
   字符串流是s这样的对象：
    头部<code>head</code>是字符串，且
    尾部<code>tail</code>是字符串流。
 这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数的头<code>head</code>和尾<code>tail</code>以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。
 共递归与协归纳相关，可以用来计算无限规模的对象。作为一种编程技术，它最常被用于 '''<font color="#f668800">惰性编程语言  lazy programming language</font>'''中，当程序输出的大小或精度未知时，使用共递归会比递归更合适。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算出前n个质数的问题，就是能用一个核心递归程序来解决的问题。

@@ 第38行： / 第38行： @@
 一种常用的计算机编程策略是将一个问题划分为与原问题相同类型的子问题，解决这些子问题，并将结果合并。这通常被称为'''<font color="#ff8000"> 分治法 divede-and-conquer</font>'''；在此基础上，加上一个存储子问题结果的查找表时（以避免重复解子问题而产生额外的计算时间），就产生了称为'''<font color="#ff8000"> 动态规划dynamic programming </font>'''或'''<font color="#ff8000"> 记忆化 memoization</font>'''的方法。
 递归函数的定义有一个或多个基本情况，函数对于输入参数只产生一个简单结果；以及一个或多个递归情况，表示程序对于输入参数进行递归(调用自身)。例如，阶乘函数可以通过等式{{math|1=0! = 1}}，对于所有{{math|''n'' > 0}}，{{math|1=''n''! = ''n''(''n'' − 1)!}}来递归定义。这两个方程本身都不构成一个完整的定义，第一个方程是基本情况，第二个方程是递归情况。因为基本情况打破了递归的链条，所以有时也被称为 “终止情况”。
 递归情况的工作可以看作是将复杂的输入分解为更简单的输入。在一个设计得当的递归函数中，每一次递归调用，都要简化输入问题，使得最终必然达到基本情况。(在正常情况下不打算终止的函数（例如，一些系统和服务器进程）是这方面的例外)。忽略编写基本情况，或不正确地测试，可能会导致'''<font color="#ff8000"> 无限循环 infinite loop</font>'''。

@@ 第791行： / 第791行： @@
 ==实现问题==
 如果不是纯粹的递归函数(对基本情况进行单一检查，否则递归步骤)，而是实际的代码实现，则为了清晰或效率起见，可能会进行大量的修改。这些修改包括：
 * 包装器函数（在顶部）
@@ 第804行： / 第798行： @@
 * 混合算法（在底部）——一旦数据足够小，就切换到另一个的算法
-On the basis of elegance, wrapper functions are generally approved, while short-circuiting the base case is frowned upon, particularly in academia. Hybrid algorithms are often used for efficiency, to reduce the overhead of recursion in small cases, and arm's-length recursion is a special case of this.
+在优雅简洁的基础上，包装器函数一般都会被接受，而对基本情况的短路则是被不被认可的的，尤其是在学术界。混合算法往往是为了提高效率，减少小规模问题下递归的开销，远程递归是一种特殊情况。
 ===包装器函数===

@@ 第1,079行： / 第1,079行： @@
 ==编者推荐==
-[[File:Recursion_Color_Art_small2.jpg|400px|right|[https://campus.swarma.org/course/1196 Matlab数据结构]]]
+[[File:Recursion_Color_Art_small2.jpg|400px|right|thumb|[https://campus.swarma.org/course/1196 Matlab数据结构]]]
 ===教程推荐===

@@ 第1,094行： / 第1,094行： @@
 ===集智课程推荐===
 ====[https://campus.swarma.org/course/1196 Matlab数据结构]====
 本课程中，是北京师范大学教授张江主讲的Matlab基础及应用2020的部分内容，主要讲解 Matlab 中数据结构的函数句柄，以及 Arrayfun 和 Cellfun 两个函数，实现高效的运算的编程思想。
@@ 第1,102行： / 第1,101行： @@
 算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。<br/>