370
个编辑
更改
无编辑摘要
{{Short description|Use of functions that call themselves (on smaller inputs)}}
{{Short description|Use of functions that call themselves (on smaller inputs)}}
{{Use dmy dates|date=March 2020|cs1-dates=y}}
{{Use dmy dates|date=March 2020|cs1-dates=y}}
[[File:recursiveTree.JPG|thumb|300px|Tree created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.]]
[[File:recursiveTree.JPG|thumb|300px|Tree created using the [[Logo (programming language)|Logo programming language]] and relying heavily on recursion. Each branch can be seen as a smaller version of a tree. 使用Logo 编程语言创建的树，主要使用递归方法。每一个分支都可以看作是一棵树的缩小版。]]
{{Programming paradigms}}
{{Programming paradigms}}
In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.
在计算机科学中，递归是一种解决问题的方法，其解决方案取决于同一问题的较小实例的解决方案。<ref>{{cite book
|author-last1 = Graham
|author-first1 = Ronald
|author-first2 = Donald |author-last2=Knuth |author-first3=Oren |author-last3=Patashnik
| title = Concrete Mathematics
| date= 1990 |isbn=0-201-55802-5
| ref=harv
| chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html
| chapter=1: Recurrent Problems
}}</ref>这种问题一般可以通过迭代来解决，但这需要在编程时识别和索引较小的问题实例。递归通过使用从自己的代码中调用自己的函数来解决这种'''<font color="#ff8000"> 递归问题 recursive problem</font>'''。这种方法可以应用于许多类型的问题，于是递归成为了计算机科学的核心思想之一。<ref>{{cite book
|author-last = Epp
|author-first = Susanna
|title = Discrete Mathematics with Applications
|date = 1995
|isbn = 978-0-53494446-9
|edition = 2nd
|ref=harv
|page = [https://archive.org/details/discretemathema000epps/page/427 427]
|url = https://archive.org/details/discretemathema000epps/page/427
}}</ref>
{{quote|text=The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.|author=[[Niklaus Wirth]]|source=''Algorithms + Data Structures = Programs'', 1976<ref>{{cite book |last = Wirth
{{quote|text=The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.|author=[[Niklaus Wirth]]|source=''Algorithms + Data Structures = Programs'', 1976<ref>{{cite book |last = Wirth
}}</ref>}}
}}</ref>}}
-- [[用户:Qige96|Ricky]]：这里缺了一个quote模板。正确的显示应该是一段文摘引用：The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement. In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions
Most computer [[programming language]]s support recursion by allowing a function to call itself from within its own code. Some [[functional programming]] languages (for instance, [[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> do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in [[computability theory]] that these recursive-only languages are [[turing completeness|Turing complete]]; this means that they are as powerful (they can be used to solve the same problems) as [[imperative language]]s based on control structures such as {{code|while}} and {{code|for}}.
Most computer [[programming language]]s support recursion by allowing a function to call itself from within its own code. Some [[functional programming]] languages (for instance, [[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> do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in [[computability theory]] that these recursive-only languages are [[turing completeness|Turing complete]]; this means that they are as powerful (they can be used to solve the same problems) as [[imperative language]]s based on control structures such as {{code|while}} and {{code|for}}.
Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as {{code|while}} and {{code|for}} .
Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as {{code|while}} and {{code|for}} .
大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些'''<font color="#ff8000"> 函数式编程语言 functional programming language</font>'''(例如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>)不定义任何循环结构，而只依赖递归来重复调用代码。在'''<font color="#ff8000">可计算性理论 computability theory</font>'''中证明了这些递归语言是'''<font color="#ff8000">图灵完备 Turing complete </font>'''这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(可以用于解决相同的问题)。
Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for large problems, it is fundamental to use optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}}
Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for large problems, it is fundamental to use optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}}
Repeatedly calling a function from within itself may cause the call stack to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less efficient, and, for large problems, it is fundamental to use optimization techniques such as tail call optimization.
从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的（因为尾递归调用可以沿用原函数的栈空间，不会新增栈帧，可以避免栈溢出——译者注）。
{{toclimit|3}}
{{toclimit|3}}
==递归函数和算法==
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]].
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.
一种常用的计算机编程策略是将一个问题划分为与原问题相同类型的子问题，解决这些子问题，并将结果合并。这通常被称为'''<font color="#ff8000"> 分治法 divede-and-conquer</font>'''；在此基础上，加上一个存储子问题结果的查找表时（以避免重复解子问题而产生额外的计算时间），就产生了称为'''<font color="#ff8000"> 动态规划dynamic programming </font>'''或'''<font color="#ff8000"> 记忆化 memoization</font>'''的方法。
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 [[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".
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 [[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.
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.
递归情况的工作可以看作是将复杂的输入分解为更简单的输入。在一个设计得当的递归函数中，每一次递归调用，都要简化输入问题，使得最终必然达到基本情况。(在正常情况下不打算终止的函数（例如，一些系统和服务器进程）是这方面的例外)。忽略编写基本情况，或不正确地测试，可能会导致'''<font color="#ff8000"> 无限循环 infinite loop</font>'''。
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 (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)".
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! + ...}}）的输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个参数（比如在上面级数例子中，可以是需要计算的项的数量）来提供一个 "停止标准"，以建立基本情况。这个例子用'''<font color="#ff8000"> 共递归corecursion</font>'''来处理其实会更自然，每次后续输出的项就是前面所有项的和；而这可以通过使用索引参数表示“计算第n项(第n部分的和)”来转换为递归。
==递归数据类型==
Many [[computer program]]s must process or generate an arbitrarily large quantity of [[data]]. Recursion is a technique for representing data whose exact size is unknown to the [[programmer]]: the programmer can specify this data with a [[Self reference|self-referential]] definition. There are two types of self-referential definitions: inductive and [[Coinduction|coinductive]] definitions.
Many [[computer program]]s must process or generate an arbitrarily large quantity of [[data]]. Recursion is a technique for representing data whose exact size is unknown to the [[programmer]]: the programmer can specify this data with a [[Self reference|self-referential]] definition. There are two types of self-referential definitions: inductive and [[Coinduction|coinductive]] definitions.
Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is a technique for representing data whose exact size is unknown to the programmer: the programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions.
Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is a technique for representing data whose exact size is unknown to the programmer: the programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions.
许多计算机程序必须处理或生成大量的数据。递归是一种表示未知确切大小的数据的技术：程序员可以使用“自引用”技术来定义这些数据。'''<font color="#ff8000"> 自引用self-referential</font>'''定义有两种类型: 归纳（inductive）定义和协归纳（coinductive）定义。
===归纳定义的数据===
{{main|Recursive data type}}
{{main|Recursive data type}}
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax):
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax):
归纳定义是指定如何构造数据实例的定义。例如，字符串列表可以被归纳定义为（在这里，使用Haskell语法）：
<syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>
<syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>
Another example of inductive definition is the natural numbers (or positive integers):
Another example of inductive definition is the natural numbers (or positive integers):
归纳定义的另一个例子是'''<font color="#ff8000">自然数 natural numbers</font>'''（或正整数）：
<pre>A natural number is either 1 or n+1, where n is a natural number.</pre>
<pre>A natural number is either 1 or n+1, where n is a natural number.</pre>
一个自然数是1或 n + 1，其中 n 是一个自然数
<pre>一个自然数是1或 n + 1，其中 n 是一个自然数。</pre>
Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages. Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:
Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages. Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:
类似的递归定义也经常被用来对编程语言中表达式和语句的结构建模。语言设计者经常用'''<font color="#ff8000"> BNF： Backus–Naur form</font>''' 这样的方法来表达程序语法。下面的实例语法，适用于表示简单的有乘法和加法的算术表达式：
<syntaxhighlight lang="bnf">
<syntaxhighlight lang="bnf">
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 < code > (5 * ((3 * 6) + 8)) </code > ，在一个表达式中有多个乘积或和运算。
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 < code > (5 * ((3 * 6) + 8)) </code > ，在一个表达式中有多个乘积或和运算。
===Coinductively defined data and corecursion===
===Coinductively defined data and corecursion===
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"> 树遍历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.
Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.
间接递归也叫'''<font color="#ff8000">相互递归 mutual recursion</font>'''，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是相互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。
===Anonymous recursion===
===Anonymous recursion===
Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.
Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.
递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为'''<font color="#ff8000"> 匿名递归anonymous recursion</font>'''。
===Structural versus generative recursion===
===Structural versus generative recursion===
}}</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?
}}</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?
'''<font color="#ff8000"> 河内塔Towers of Hanoi </font>'''是一个数学难题，它的解法说明了递归的问题。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？
''Function definition'':
''Function definition'':
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.
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.
'''<font color="#ff8000"> 二分搜索binary search</font>'''二分搜索算法是通过每次递归将数组切成两半来搜索排序数组中单个元素的方法。其诀窍是在数组中心附近选取一个中点，将该点的数据与被搜索的数据进行比较，然后响应三种可能的条件之一：在中点找到数据，中点的数据大于被搜索的数据，或者中点的数据小于被搜索的数据。
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.
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.
</syntaxhighlight>
</syntaxhighlight>
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.
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.
这段代码至少在某种程度上融合了递归和迭代之间的界限。本质上，它是一个递归的实现，这是遍历文件系统的最佳方式。它也是直接递归和间接递归的一个例子。'''<font color=''32CD32''>方法 "rtraverse "是纯粹的直接例子，方法 "traverse "是间接的，它调用 "rtraverse"。</font>'''这个例子不需要 "基本情况"，因为在给定的文件系统中总会有一些固定数量的文件或目录。
==Implementation issues==
==Implementation issues==
A [[wrapper function]] is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.
A [[wrapper function]] is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.
'''<font color="#ff8000"> 包装函数wrapper function</font>'''是指直接调用但本身不递归的函数，而是调用一个单独的辅助函数，它实际上进行递归。
Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for [[memoization]], and handle exceptions and errors. In languages that support [[nested function]]s, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using [[pass-by-reference]].
Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for [[memoization]], and handle exceptions and errors. In languages that support [[nested function]]s, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using [[pass-by-reference]].
A basic example of short-circuiting is given in [[depth-first search]] (DFS) of a binary tree; see [[#Binary trees|binary trees]] section for standard recursive discussion.
A basic example of short-circuiting is given in [[depth-first search]] (DFS) of a binary tree; see [[#Binary trees|binary trees]] section for standard recursive discussion.
在二叉树的'''<font color="#ff8000"> 深度优先搜索depth-first search</font>'''（DFS）中给出了一个短路的基本例子；标准递归讨论见二叉树部分。
The standard recursive algorithm for a DFS is:
The standard recursive algorithm for a DFS is:
递归算法的时间效率
递归算法的时间效率
The [[time complexity|time efficiency]] of recursive algorithms can be expressed in a [[recurrence relation]] of [[Big O notation]]. They can (usually) then be simplified into a single Big-O term.
The [[time complexity|time efficiency]] of recursive algorithms can be expressed in a [[recurrence relation]] of [[Big O notation]]. They can (usually) then be simplified into a single Big-O term.
递归算法的'''<font color="#ff8000"> 时间效率time efficiency </font>'''可以用大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。
===Shortcut rule (master theorem)===
===Shortcut rule (master theorem)===