2,367
个编辑
更改
跳到导航
跳到搜索
第247行：
第247行： − − A classic example of a recursive procedure is the function used to calculate the [[factorial]] of a [[natural number]]: − − A classic example of a recursive procedure is the function used to calculate the factorial of a natural number: 第299行：
第295行： − − This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above: − − This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above: 第323行：
第315行： − This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages: − − This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages: 第373行：
第362行： − − The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'': − − The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'': 第390行：
第375行： − − The definition above translates straightforwardly to [[functional programming language]]s such as [[Scheme (programming language)|Scheme]]; this is an example of iteration implemented recursively. 第397行：
第380行： − The [[Euclidean algorithm]], which computes the [[greatest common divisor]] of two integers, can be written recursively. − − '' − Function definition'': 第474行：
第453行： − The recursive program above is [[tail-recursive]]; it is equivalent to an iterative algorithm, and the computation shown above shows the steps of evaluation that would be performed by a language that eliminates tail calls. Below is a version of the same algorithm using explicit iteration, suitable for a language that does not eliminate tail calls. By maintaining its state entirely in the variables ''x'' and ''y'' and using a looping construct, the program avoids making recursive calls and growing the call stack.+ 第522行：
第501行： − The iterative algorithm requires a temporary variable, and even given knowledge of the Euclidean algorithm it is more difficult to understand the process by simple inspection, although the two algorithms are very similar in their steps.+ 第530行：
第509行： − {{main|Towers of Hanoi}} − − The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion.<ref>{{harvnb|Graham|Knuth|Patashnik|1990|loc=§1.1: The Tower of Hanoi − }}</ref><ref>{{harvnb|Epp|1995|pp=427–430: The Tower of Hanoi − }}</ref> There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with ''n'' disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack? 第631行：
第605行： − − The [[binary search]] algorithm is a method of searching a [[sorted array]] for a single element by cutting the array in half with each recursive pass. The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for. − Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new (and smaller) array. Typically the array's size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass. − − Example implementation of binary search in C: 第713行：
第682行： − − {{main|Recursive data type}} − − An important application of recursion in computer science is in defining dynamic data structures such as [[list (abstract data type)|lists]] and [[tree (data structure)|trees]]. Recursive data structures can dynamically grow to a theoretically infinite size in response to runtime requirements; in contrast, the size of a static array must be set at compile time. 第727行：
第692行： − − − The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively. − As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.<ref name="Felleisen 2002 108"/> 第741行：
第702行： − − {{main|Linked list}} − − Below is a C definition of a linked list node structure. Notice especially how the node is defined in terms of itself. The "next" element of ''struct node'' is a pointer to another ''struct node'', effectively creating a list type. 第756行：
第713行： − − Because the ''struct node'' data structure is defined recursively, procedures that operate on it can be implemented naturally as recursive procedures. The ''list_print'' procedure defined below walks down the list until the list is empty (i.e., the list pointer has a value of NULL). For each node it prints the data element (an integer). In the C implementation, the list remains unchanged by the ''list_print'' procedure. 第775行：
第730行： − {{main|Binary tree}} − Below is a simple definition for a binary tree node. Like the node for linked lists, it is defined in terms of itself, recursively. There are two self-referential pointers: left (pointing to the left sub-tree) and right (pointing to the right sub-tree). 第790行：
第743行： − Operations on the tree can be implemented using recursion. Note that because there are two self-referencing pointers (left and right), tree operations may require two recursive calls: 第805行：
第757行： − At most two recursive calls will be made for any given call to ''tree_contains'' as defined above. 第819行：
第770行： − − The above example illustrates an [[Tree traversal|in-order traversal]] of the binary tree. A [[Binary search tree]] is a special case of the binary tree where the data elements of each node are in order. 第826行：
第775行： − − Since the number of files in a [[filesystem]] may vary, [[recursion]] is the only practical way to traverse and thus enumerate its contents. Traversing a filesystem is very similar to that of [[tree traversal]], therefore the concepts behind tree traversal are applicable to traversing a filesystem. More specifically, the code below would be an example of a [[preorder traversal]] of a filesystem. 第872行：
第819行： − This code blends the lines, at least somewhat, between recursion and [[iteration]]. It is, essentially, a recursive implementation, which is the best way to traverse a [[filesystem]]. It is also an example of direct and indirect recursion. '''<font color=''32CD32''> The method "rtraverse" is purely a direct example; the method "traverse" is the indirect, which calls "rtraverse". </font>''' This example needs no "base case" scenario due to the fact that there will always be some fixed number of files or directories in a given filesystem.+
→递归程序
====阶乘====
====阶乘====
递归过程的一个经典例子是用于计算自然数阶乘的函数:
递归过程的一个经典例子是用于计算自然数阶乘的函数:
:<math>b_n = nb_{n-1}</math>
:<math>b_n = nb_{n-1}</math>
:<math>b_0 = 1</math>
:<math>b_0 = 1</math>
这种对递归关系的求值展示了在执行上述伪代码时将进行的计算。
这种对递归关系的求值展示了在执行上述伪代码时将进行的计算。
|}
|}
这个阶乘函数也可以在不使用递归的情况下，通过使用典型的循环结构来描述，这些循环结构在命令式编程语言中可以找到：
这个阶乘函数也可以在不使用递归的情况下，通过使用典型的循环结构来描述，这些循环结构在命令式编程语言中可以找到：
'''结束''' 阶乘
'''结束''' 阶乘
|}
|}
上面的命令式代码相当于这个使用累加器变量{{math|<var>t</var>}的数学定义:
上面的命令式代码相当于这个使用累加器变量{{math|<var>t</var>}的数学定义:
\end{array}
\end{array}
</math>
</math>
上面的定义可以直接翻译成函数式编程语言，比如Scheme；这就是一个递归实现迭代的例子。
上面的定义可以直接翻译成函数式编程语言，比如Scheme；这就是一个递归实现迭代的例子。
====最大公约数====
====最大公约数====
计算两个整数最大公除数的欧氏算法，可以递归写成。
计算两个整数最大公除数的欧氏算法，可以递归写成。
函数定义：
函数定义：
:<math> \gcd(x,y) =
:<math> \gcd(x,y) =
|}
|}
上面的递归程序是尾部递归；它相当于一个迭代算法，上面显示的计算显示了一个消除尾部调用的语言将执行的评估步骤。 下面是使用显式迭代的相同算法的一个版本，适用于不消除尾部调用的语言。 通过将其状态完全保持在变量''x''和''y''中，并使用循环结构，该程序避免了递归调用和增加调用栈。
上面的递归程序是尾部递归；它相当于一个迭代算法，上面显示的计算显示了一个消除尾部调用的语言将执行的评估步骤。 下面是使用显式迭代的相同算法的一个版本，适用于不消除尾部调用的语言。 通过将其状态完全保持在变量''x''和''y''中，并使用循环结构，该程序避免了递归调用和增加调用栈。
|}
|}
迭代算法需要一个临时变量，且即使给出了欧几里得算法的知识，但要通过简单的检查来理解其过程是比较困难的，虽然两种算法的步骤非常相似。
迭代算法需要一个临时变量，且即使给出了欧几里得算法的知识，但要通过简单的检查来理解其过程是比较困难的，虽然两种算法的步骤非常相似。
[[File:Tower of Hanoi.jpeg|thumb|汉诺塔]]
[[File:Tower of Hanoi.jpeg|thumb|汉诺塔]]
'''<font color="#ff8000"> 汉诺塔 Towers of Hanoi </font>'''是一个数学难题，它的解法说明了递归的思想<ref>{{harvnb|Graham|Knuth|Patashnik|1990|loc=§1.1: The Tower of Hanoi}}</ref><ref>{{harvnb|Epp|1995|pp=427–430: The Tower of Hanoi}}</ref>。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？
'''<font color="#ff8000"> 汉诺塔 Towers of Hanoi </font>'''是一个数学难题，它的解法说明了递归的思想<ref>{{harvnb|Graham|Knuth|Patashnik|1990|loc=§1.1: The Tower of Hanoi}}</ref><ref>{{harvnb|Epp|1995|pp=427–430: The Tower of Hanoi}}</ref>。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？
====二分搜索====
====二分搜索====
'''<font color="#ff8000"> 二分搜索 binary search</font>'''算法是通过每次递归将数组切成两半来搜索''有序''数组中某个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后产生三种可能之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。
'''<font color="#ff8000"> 二分搜索 binary search</font>'''算法是通过每次递归将数组切成两半来搜索''有序''数组中某个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后产生三种可能之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。
在这个算法中使用了递归，因为算法每一轮都会把旧的数组切成两半，以创建一个新的数组。然后递归地调用二分搜索过程，这次是在新的（更小的）数组上。通常情况下，数组的大小是通过操作开始和结束索引来调整的。该算法表现对数级增长复杂度，因为它基本上是将问题域对半分。
在这个算法中使用了递归，因为算法每一轮都会把旧的数组切成两半，以创建一个新的数组。然后递归地调用二分搜索过程，这次是在新的（更小的）数组上。通常情况下，数组的大小是通过操作开始和结束索引来调整的。该算法表现对数级增长复杂度，因为它基本上是将问题域对半分。
C语言中二分搜索的实现实例:
C语言中二分搜索的实现实例:
===递归数据结构（结构化递归）===
===递归数据结构（结构化递归）===
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大；相反，静态数组的大小必须在编译时设定。
</blockquote>
</blockquote>
本节的例子说明了所谓的 "结构化递归"。这个术语的意思是递''归程序作用于递归定义的数据''。
本节的例子说明了所谓的 "结构化递归"。这个术语的意思是递''归程序作用于递归定义的数据''。
<blockquote>
<blockquote>
只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。
只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数体中的递归会消耗给定复合值的某些部分。
====链表====
====链表====
下面是一个链表节点结构的C语言定义。特别注意节点是如何通过自身来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。
下面是一个链表节点结构的C语言定义。特别注意节点是如何通过自身来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。
</syntaxhighlight>
</syntaxhighlight>
由于''struct node''数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的''list_print''过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在''list_print''过程中保持不变。
由于''struct node''数据结构是递归定义的，因此对其进行操作的过程可以自然地实现为递归过程。下面定义的''list_print''过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在''list_print''过程中保持不变。
====二叉树====
====二叉树====
下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。
下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。
</syntaxhighlight>
</syntaxhighlight>
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
}
}
</syntaxhighlight>
</syntaxhighlight>
对于上面定义的''tree_contains''的任何给定函数调用，最多会产生两次递归调用。
对于上面定义的''tree_contains''的任何给定函数调用，最多会产生两次递归调用。
}
}
</syntaxhighlight>
</syntaxhighlight>
上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。
上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素按顺序排列。
====文件系统遍历====
====文件系统遍历====
由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树遍历非常相似，因此树遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的前序遍历的示例。
由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树遍历非常相似，因此树遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的前序遍历的示例。
</syntaxhighlight>
</syntaxhighlight>
这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 '''<font color=''32CD32''> 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。
这段代码至少在某种程度上糅合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。 '''<font color=''32CD32''> 方法 "rtraverse "是直接递归的例子，方法 "traverse "是则间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中文件和目录的数量总是有限的。