90
个编辑
更改
跳到导航
跳到搜索
小第1行：
第1行： − 此词条暂由彩云小译翻译，翻译字数共5094，未经人工整理和审校，带来阅读不便，请见谅。+ 第9行：
第9行： − + − 标志编程语言和严重依赖递归。每个树枝都可以看作是一棵树的缩小版。]+ 第18行：
第18行： − − 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. − − 在计算机科学中，递归是一种解决问题的方法，其解决方案依赖于对同一问题的较小实例的解决方案。这类问题通常可以通过迭代解决，但是这需要在编程时识别和索引较小的实例。递归通过使用从自己的代码中调用自己的函数来解决这类递归问题。这种方法可以应用于许多类型的问题，递归是计算机科学的中心思想之一。 − − − − − − 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 and . − − 大多数计算机编程语言通过允许函数在自己的代码中调用自己来支持递归。一些函数式编程语言(例如 Clojure)不定义任何循环结构，而是完全依赖递归来重复调用代码。可计算性理论证明了这些递归只有语言是图灵完备的; 这意味着它们和基于控制结构的命令式语言一样强大(它们可以用来解决同样的问题) ，比如和。 − − − − 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. − − 从函数自身内部重复调用可能导致调用堆栈的大小等于所有相关调用的输入大小之和。因此，对于很容易通过迭代解决的问题，递归通常效率较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术是基本的。 − − − − − − − 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 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". − − 递归函数定义有一个或多个基本情况，即函数为其产生结果的意义输入(不重复)和一个或多个递归情况，即程序为其递归(调用自身)的意义输入。例如，阶乘函数可以由方程组递归地定义，并且对于所有方程组，。两个方程本身都不能构成一个完整的定义; 第一个是基本情形，第二个是递归情形。因为基本大小写打破了递归链，所以有时也称为“终止大小写”。 − − − − 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. − − 递归案例的工作可以看作是将复杂的输入分解为更简单的输入。在设计合理的递归函数中，每次递归调用都必须简化输入问题，以便最终达到基本情况。(在正常情况下不打算终止的功能(例如，一些系统和服务器进程)是这方面的例外。)忽略编写基本情况，或不正确地测试它，可能会导致无限循环。 − − − − For some functions (such as one that computes the series for ) 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)". − − 对于某些函数(例如计算序列的函数) ，输入数据并没有明显的基本情况; 对于这些函数，可以添加一个参数(例如在我们的系列示例中要添加的术语数量) ，以提供建立基本情况的“停止条件”。这样的例子更自然地用共递归处理，其中输出中的连续项是部分和; 这可以通过使用索引参数来转换为递归，即“计算第 n 项(第 n 次部分和)”。 − − + − + − 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. − − 许多计算机程序必须处理或生成任意大量的数据。递归是一种表示数据的技术，这些数据的确切大小程序员是不知道的: 程序员可以用自引用的定义指定这些数据。自指定义有两种类型: 归纳定义和协归纳定义。 − − − − − − + + + + − 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 语法) :+ − |ref=harv+ − + − <syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>+ − < syntaxhighlight lang = " haskell" > data ListOfStrings = EmptyList | Cons String ListOfStrings </syntaxhighlight > + − |url = https://archive.org/details/algorithmsdatast00wirt/page/126+ − }}</ref>}}+ − The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.+ − 上面的代码指定一个字符串列表为空，或者一个包含字符串和字符串列表的结构。定义中的自引用允许构造任意数量(有限)字符串的列表。+ + + + + − 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}}.+ − Another example of inductive definition is the natural numbers (or positive integers):+ − 归纳定义的另一个例子是自然数(或正整数) :+ + + − 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}}+ − <pre>A natural number is either 1 or n+1, where n is a natural number.</pre>+ − 一个自然数是1或 n + 1，其中 n 是一个自然数+ + + + + − + − 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:+ − 类似地，递归定义通常用于为编程语言中的表达式和语句的结构建模。语言设计者经常用诸如 Backus-Naur 形式这样的句法来表达语法，这里有一种语法，用于一种简单的带有乘法和加法的算术表达式语言:+ + + + + − ==Recursive functions and algorithms==+ − <syntaxhighlight lang="bnf">+ − “ bnf”“ syntaxhighlight lang”+ − 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]].+ + + − <expr> ::= <number>+ − < expr > : : = < number > + − | (<expr> * <expr>)+ − | (< expr > * < expr >)+ − 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". − | (<expr> + <expr>) − | (< expr > + < expr >)+ + − </syntaxhighlight> − </syntaxhighlight >+ − 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]].+ + + + + + + − 这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过递归引用第二行和第三行中的表达式，文法允许任意复杂的算术表达式，如 < code > (5 * ((3 * 6) + 8)) </code > ，在一个表达式中有多个乘积或和运算。+ − 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)".+ − + − + − + − + − 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. − 协同归纳数据定义是指可以对一段数据执行的操作; 通常，自参照协同归纳定义用于无限大小的数据结构。+ − + − − {{further|Algebraic data type}} − 非正式给出的无限弦流的共归纳定义可能是这样的:+ + + + + + − ===Inductively defined data===+ − A stream of strings is an object s such that:+ − 字符串流是这样的对象:+ − {{main|Recursive data type}}+ − head(s) is a string, and+ − 头是一根绳子，而+ + + + + + − tail(s) is a stream of strings.+ − Tail (s)是一个字符串流。+ − An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, [[linked list]]s can be defined inductively (here, using [[Haskell (programming language)|Haskell]] syntax):+ + + − This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the accessor functions <code>head</code> and <code>tail</code>—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.+ − 这非常类似于字符串列表的归纳定义; 区别在于这个定义指定了如何访问数据结构的内容ー即通过访问器函数 < code > head </code > 和 < code > tail </code > 以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及可以从哪些内容创建结构。+ − <syntaxhighlight lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</syntaxhighlight>+ + + + + − Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n prime numbers is one that can be solved with a corecursive program (e.g. here).+ − 共递归与共归纳相关，可用于计算(可能)无限对象的特定实例。作为一种编程技术，它最常用于惰性编程语言的上下文中，并且在程序输出的所需大小或精度未知时优于递归。在这种情况下，程序既需要一个无限大(或无限精确)结果的定义，又需要一个取得该结果的有限部分的机制。计算第一个 n 素数的问题是一个可以用余递归程序解决的问题。这里)。+ − The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.+ + + + + − Another example of inductive [[definition]] is the [[natural numbers]] (or positive [[integers]]):+ + + − <pre>A natural number is either 1 or n+1, where n is a natural number.</pre>+ + + − 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.+ − 只包含一个自引用的递归称为递归，而包含多个自引用的递归称为。单次递归的标准例子包括列表遍历，比如线性搜索，或者计算阶乘函数，而多次递归的标准例子包括树遍历，比如深度优先搜索遍历。+ + + + − Similarly recursive [[definition]]s are often used to model the structure of [[expression (programming)|expressions]] and [[statement (programming)|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:+ + − 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.+ − 单次递归通常比多次递归更有效，并且通常可以用迭代计算来代替，这种迭代计算在线性时间内运行，并且需要常量空间。相比之下，多次递归可能需要 EXPTIME 和空间，而且更基本上是递归的，没有明确的堆栈就不能被迭代替代。+ + + − <syntaxhighlight lang="bnf">+ − Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see corecursion: examples. A more sophisticated example is using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.+ + + + + + + + + + + + + + + − 多个递归有时可以转换为单个递归(如果需要，从那里转换为迭代)。例如，当天真地计算斐波那契序列是多次迭代时，因为每个值需要两个前面的值，所以可以通过传递两个连续的值作为参数来单次计算斐波那契序列。这更自然地被定义为共递归，从初始值开始构建，在每一步跟踪两个连续的值——参见共递归: 示例。一个更加复杂的例子是使用线索二叉树遍历，它允许迭代树遍历，而不是多次递归。+ − <expr> ::= <number>+ − | (<expr> * <expr>)+ − | (<expr> + <expr>)+ − </syntaxhighlight>+ + + − Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.+ − 大多数递归的基本例子和这里提供的大多数例子都演示了直接递归，即函数调用自身。间接递归不是由函数本身调用，而是由它直接或间接调用的另一个函数调用时发生。例如，如果 f 调用 f，这是直接递归，但如果 f 调用 g 调用 f，那么这是间接递归 f 的三个或更多的函数链是可能的; 例如，函数1调用函数2，函数2调用函数3，函数3再次调用函数1。+ − This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression.+ + + − 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.+ − 间接递归也被称为相互递归，这是一个更加对称的术语，尽管这只是强调的不同，而不是一个不同的概念。也就是说，如果 f 调用 g，然后 g 调用 f，然后 f 又调用 g，从 f 的角度来看，f 是间接递归的，而从 g 的角度来看，f 是间接递归的，而从两者的角度来看，f 和 g 是相互递归的。同样，一组三个或三个以上相互调用的函数也可以称为一组相互递归的函数。+ − + + − {{main|Coinduction|Corecursion}}+ + + + + − + + + + + + + + − A coinductive definition of infinite [[stream (computer science)|streams]] of strings, given informally, might look like this:+ − + − 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.+ − + − 递归通常是通过按名称显式调用函数来完成的。然而，递归也可以通过基于当前上下文隐式调用函数来实现，这对匿名函数特别有用，称为匿名递归。+ + + + + + + + + + + + + + + + + + + + − A stream of strings is an object s such that:+ − − head(s) is a string, and − tail(s) is a stream of strings.+ + + + + − Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:+ + + + − 有些作者将递归归类为“结构性”或“生成性”。这个区别与递归过程从哪里获得它所处理的数据以及它如何处理这些数据有关:+ + + + + + + + + + + + − + + + − Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of [[lazy evaluation|lazy]] programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n [[prime numbers]] is one that can be solved with a corecursive program (e.g. [[Fold (higher-order function)#Examples|here]]).+ − + − + − + − Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.+ − + − 因此，结构递归函数的定义特征是，每个递归调用的参数是原始输入字段的内容。结构递归包括几乎所有的树遍历，包括 XML 处理、二叉树创建和搜索等。通过考虑自然数的代数结构(也就是说，自然数要么是零，要么是自然数的继承者) ，阶乘等函数也可以被看作是结构递归。+ − + − ==Types of recursion==+ + + + + + + + + + + + + + + + + + + + + + + + + + + + + − is the alternative:+ − 是另一种选择:+ − ===Single recursion and multiple recursion===+ − + − Recursion that only contains a single self-reference is known as '''{{visible anchor|single recursion}}''', while recursion that contains multiple self-references is known as '''{{visible anchor|multiple recursion}}'''. 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.+ − + − + + + + + + − {{ quote | text = 许多著名的递归算法从给定的数据生成一段全新的数据并在其上重复使用。HtDP (如何设计程序)就是指这种类型的生成递归。生成递归的例子包括: gcd，快速排序，二进制搜索，归并，牛顿方法，分形和适应性集成+ + + + + − | url = ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Advanced%20Functional%20Programming%204%20conf.,%20AFP%202002%20(LNCS2638,%20Springer,%202003)(ISBN%203540401326)(O)(222s).pdf#page=109 + − 20programming% 204% 20conf.pdf # page = 109+ + + + + + + + + − 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.+ + + + + − }}+ − + − }}+ + + + + + + + + + + + + − This distinction is important in proving termination of a function. + + + + − 这种区别在证明函数的终止性时很重要。+ + + − Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see [[Corecursion#Examples|corecursion: examples]]. A more sophisticated example is using a [[threaded binary tree]], which allows iterative tree traversal, rather than multiple recursion.+ + + + + + + + + − + − + − {{main|Mutual recursion}}+ + + + + + + + + + − Most basic examples of recursion, and most of the examples presented here, demonstrate {{anchor|direct recursion}}'''''direct'' recursion''', in which a function calls itself. ''Indirect'' recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if ''f'' calls ''f,'' that is direct recursion, but if ''f'' calls ''g'' which calls ''f,'' then that is indirect recursion of ''f.'' Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.+ − + − + − + − 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.+ − + − + − + − ===Anonymous recursion===+ + + + + + + + + + + + + − {{main|Anonymous recursion}}+ + + + + + + + + + + + + + + − A classic example of a recursive procedure is the function used to calculate the factorial of a natural number:+ − 递归过程的一个经典例子是用于计算自然数阶乘的函数:+ + + + + + + + + − 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 function]]s, and is known as [[anonymous recursion]].+ − + + + + + + + + − + + + + + + + + − \begin{cases} + + + + + + + + + + + − 开始{ cases }+ + − + + + + + + + + + + + + + + − + + + + + + + + − 1 & mbox { if } n = 0+ + − {{see also|Structural recursion}}+ − n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\+ + + − N cdot 操作符/名称{ fact }(n-1) & mbox { if } n > 0+ + + + + + + + + + + + + − \end{cases}+ − + − 结束{ cases } − − Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data: − </math>+ − 数学+ + + − {{quote|text=[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.|author=Felleisen, Findler, Flatt, and Krishnaurthi|source=''[[How to Design Programs]]'', 2001<ref name="Felleisen HtDP 2001">{{harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= [http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html art V "Generative Recursion]}}+ − {| class="wikitable"+ − { | class = “ wikitable”+ − </ref>}}+ − |-+ − + − |-+ + + + + + + + + + + + + + + + + + + + + − ! Pseudocode (recursive):+ + + − !伪代码(递归) :+ + + + + + + + + + + + + + + + + + + + + − Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.+ + + + + + + + + + + − + + + − + + + + − |+ − |+ − '''{{visible anchor|Generative recursion}}''' is the alternative:+ − function factorial is:<br />+ + + − 函数阶乘是: < br/> + + + + + − input: integer n such that n >= 0<br /> + − 输入: 整数 n 使得 n > = 0 < br/> + − + + + + + + + − output: [n × (n-1) × (n-2) × … × 1] + + + + + + + − output: [n × (n-1) × (n-2) × … × 1] + − − | last = Felleisen − <br />+ − + + + + + + + + + + − | first = Matthias+ + + + + + + + + + − 1. if n is 0, return 1+ + + − 1. 如果 n 等于0，返回1+ − | chapter = Developing Interactive Web Programs |chapterurl=https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108+ − 2. otherwise, return [ n × factorial(n-1) ]+ + + + + + + + − 2. 否则返回[ n × 阶乘(n-1)]+ − | date = 2002+ − + − + + + + + + + + + + + − < br/>+ − | title = Advanced Functional Programming: 4th International School+ + + + + + + + + + − end factorial + − 终止阶乘+ − | editor-last = Jeuring+ + + − |}+ − |}+ + − | editor-first = Johan+ − | volume =+ + + − The function can also be written as a recurrence relation:+ + + + + + + + + + + + − 这个函数也可以写成一个递回关系式:+ + + + + + + − | page = 108+ + + + + + + − <math>b_n = nb_{n-1}</math>+ + − + − | publisher = Springer+ − <math>b_0 = 1</math>+ + + − 《数学》 b0 = 1+ − | isbn = 9783540448334+ + + + + + − This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:+ − 这个对递回关系式代码的评估演示了在评估上面的伪代码时所执行的计算:+ − }}+ + + − {| class="wikitable"+ − { | class = “ wikitable”+ − </ref>+ − + + + + − |-+ − | url = ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Advanced%20Functional%20Programming%204%20conf.,%20AFP%202002%20(LNCS2638,%20Springer,%202003)(ISBN%203540401326)(O)(222s).pdf#page=109 + − ! Computing the recurrence relation for n = 4:+ − !计算 n = 4的递回关系式:+ + + + + + + + + + + + + − }}+ − + + + − |-+ − This distinction is important in [[Termination analysis#Termination proof|proving termination]] of a function. + − |+ + − |+ − + − + − b<sub>4</sub> = 4 * b<sub>3</sub><br />+ + + + + − B < sub > 4 </sub > = 4 * b < sub > 3 </sub > < br/> + − * Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding [[infinite loops]] requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed.+ − = 4 * (3 * b<sub>2</sub>)+ − = 4 * (3 * b < sub > 2 </sub >)+ − * In terms of [[loop variant]]s, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step. + − = 4 * (3 * (2 * b<sub>1</sub>))+ − + + + + + + + + + + + + − * By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further analysis.+ − = 4 * (3 * (2 * (1 * b<sub>0</sub>)))+ − + − = 4 * (3 * (2 * (1 * b < sub > 0 </sub >))+ + + + + + + + + + + + + + + + + − = 4 * (3 * (2 * (1 * 1)))+ − = 4 * (3 * (2 * (1 * 1)))+ + + − ==Recursive programs==+ − = 4 * (3 * (2 * 1))+ + + − = 4 * (3 * (2 * 1))+ + + + − = 4 * (3 * 2)+ − + − = 4 * (3 * 2)+ − + − + + + + + + + + + + + − = 4 * 6+ − = 4 * 6+ + + − = 24+ + + + + + + + + + − = 24+ + + − ====Factorial====+ − + − |}+ − A classic example of a recursive procedure is the function used to calculate the [[factorial]] of a [[natural number]]:+ + + + + − This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages:+ − 这个阶乘函数也可以不使用递归来描述，方法是使用命令式编程语言中典型的循环结构:+ + + − :<math> \operatorname{fact}(n) =+ − − \begin{cases} − + + + − { | class = “ wikitable”+ − 1 & \mbox{if } n = 0 \\+ + + − |-+ − + + + − n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\+ − ! Pseudocode (iterative):+ + + − !伪代码(迭代) :+ − − \end{cases} + − + + + + + + + + + + + + + + + + + + + + + + + − </math>+ − − | − − | − + − function factorial is:<br />+ + + − 函数阶乘是: < br/> + + + + + + + + + − {| class="wikitable"+ − − input: integer n such that n >= 0<br /> − − 输入: 整数 n 使得 n > = 0 < br/> − − |- − − output: [n × (n-1) × (n-2) × … × 1] − − output: [n × (n-1) × (n-2) × … × 1] − − ! [[Pseudocode]] (recursive): − − <br /> − − < br/> − − |- − − 1. create new variable called running_total with a value of 1 − − 1. 创建名为 running _ total 的新变量，其值为1 − − | − − <br /> − − < br/> − − '''function''' factorial is:<br /> − − 2. begin loop − − 2. begin loop − − '''input''': integer ''n'' such that ''n'' >= 0<br /> − − 1. if n is 0, exit loop − − 1. 如果 n 是0，退出循环 − − '''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1] − − 2. set running_total to (running_total × n) − − 2. 将 running total 设置为(running total × n) − − <br /> − − 3. decrement n − − 3. 减少 − − 1. if ''n'' is 0, '''return''' 1 − − 4. repeat loop − − 4. 重复循环 − − 2. otherwise, '''return''' [ ''n'' × factorial(''n''-1) ] − − <br /> − − < br/> − − <br /> − − 3. return running_total − − 3. return running total − − '''end''' factorial − − <br /> − − < br/> − − |} − − end factorial − − 终止阶乘 − − − − |} − − |} − − The function can also be written as a [[recurrence relation]]: − − :<math>b_n = nb_{n-1}</math> − − The imperative code above is equivalent to this mathematical definition using an accumulator variable : − − 上面的命令代码使用累加器变量等价于这个数学定义: − − :<math>b_0 = 1</math> − − This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above: − − <math> − − 《数学》 − − {| class="wikitable" − − \begin{array}{rcl} − − 开始{ array }{ rcl } − − |- − − \operatorname{fact}(n) & = & \operatorname{fact_{acc}}(n, 1) \\ − − 操作符名称{ fact }(n) & = & operatorname { fact _ { acc }(n，1) − − ! Computing the recurrence relation for n = 4: − − \operatorname{fact_{acc}}(n, t) & = & − − 操作符名称{ fact _ { acc }(n，t) & = & − − |- − − \begin{cases} − − 开始{ cases } − − | − − t & \mbox{if } n = 0 \\ − − 0 − − b<sub>4</sub> = 4 * b<sub>3</sub><br /> − − \operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n > 0 \\ − − 操作符名称{ fact _ { acc }(n-1，nt) & mbox { if } n > 0 − − = 4 * (3 * b<sub>2</sub>) − − \end{cases} − − 结束{ cases } − − = 4 * (3 * (2 * b<sub>1</sub>)) − − \end{array} − − 结束{数组} − − = 4 * (3 * (2 * (1 * b<sub>0</sub>))) − − </math> − − 数学 − − = 4 * (3 * (2 * (1 * 1))) − − = 4 * (3 * (2 * 1)) − − The definition above translates straightforwardly to functional programming languages such as Scheme; this is an example of iteration implemented recursively. − − 上面的定义直接转换为函数式编程语言，例如 Scheme; 这是递归实现的迭代示例。 − − = 4 * (3 * 2) − − = 4 * 6 − − = 24 − − The Euclidean algorithm, which computes the greatest common divisor of two integers, can be written recursively. − − 计算2个整数的辗转相除法最大公约数，可以递归地写。 − − |} − − − − This factorial function can also be described without using recursion by making use of the typical looping constructs found in imperative programming languages: − − Function definition: − − 功能定义: − − − − <math> \gcd(x,y) = − − < math > gcd (x，y) = − − {| class="wikitable" − − \begin{cases} − − 开始{ cases } − − |- − − x & \mbox{if } y = 0 \\ − − 0 − − ! Pseudocode (iterative): − − \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\ − − Gcd (y，operatorname { remainder }(x，y)) & mbox { if } y > 0 − − |- − − \end{cases} − − 结束{ cases } − − | − − </math> − − 数学 − − '''function''' factorial is:<br /> − − '''input''': integer ''n'' such that ''n'' >= 0<br /> − − {| class="wikitable" − − { | class = “ wikitable” − − '''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1] − − |- − − |- − − <br /> − − ! Pseudocode (recursive): − − !伪代码(递归) : − − 1. '''create''' new variable called ''running_total'' with a value of 1 − − |- − − |- − − <br /> − − | − − | − − 2. '''begin''' loop − − function gcd is: − − 函数 gcd 是: − − 1. if ''n'' is 0, '''exit''' loop − − input: integer x, integer y such that x > 0 and y >= 0 − − 输入: 整数 x，整数 y 使得 x > 0和 y > = 0 − − 2. '''set''' ''running_total'' to (''running_total'' × ''n'') − − <br /> − − < br/> − − 3. '''decrement''' ''n'' − − 1. if y is 0, return x − − 1. 如果 y = 0，返回 x − − 4. '''repeat''' loop − − 2. otherwise, return [ gcd( y, (remainder of x/y) ) ] − − 2. 否则，返回[ gcd (y，(x/y 的余数))] − − <br /> − − <br /> − − < br/> − − 3. '''return''' ''running_total'' − − end gcd − − 末端 gcd − − <br /> − − |} − − |} − − '''end''' factorial − − |} − − Recurrence relation for greatest common divisor, where <math>x \% y</math> expresses the remainder of <math>x / y</math>: − − 递回关系式为最大公约数，其中 x% y 表示了《 math > x/y </math > 的剩余部分: − − − − The imperative code above is equivalent to this mathematical definition using an accumulator variable {{math|<var>t</var>}}'': − − <math>\gcd(x,y) = \gcd(y, x \% y)</math> if <math>y \neq 0</math> − − Gcd (x，y) = gcd (y，x% y) </math > if < math > y neq 0 </math > − − − − <math>\gcd(x,0) = x</math> − − < math > gcd (x，0) = x </math > − − :<math> − − \begin{array}{rcl} − − {| class="wikitable" − − { | class = “ wikitable” − − \operatorname{fact}(n) & = & \operatorname{fact_{acc}}(n, 1) \\ − − |- − − |- − − \operatorname{fact_{acc}}(n, t) & = & − − ! Computing the recurrence relation for x = 27 and y = 9: − − !计算 x = 27和 y = 9的递回关系式: − − \begin{cases} − − |- − − |- − − t & \mbox{if } n = 0 \\ − − | − − | − − \operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n > 0 \\ − − gcd(27, 9) = gcd(9, 27% 9) − − Gcd (27,9) = gcd (9,27% 9) − − \end{cases} − − = gcd(9, 0) − − = gcd (9,0) − − \end{array} − − = 9 − − = 9 − − </math> − − |- − − |- − − − − ! Computing the recurrence relation for x = 111 and y = 259: − − !计算 x = 111和 y = 259的递回关系式: − − The definition above translates straightforwardly to [[functional programming language]]s such as [[Scheme (programming language)|Scheme]]; this is an example of iteration implemented recursively. − − |- − − |- − − − − | − − | − − ====Greatest common divisor==== − − gcd(111, 259) = gcd(259, 111% 259) − − Gcd (111,259) = gcd (259,111% 259) − − The [[Euclidean algorithm]], which computes the [[greatest common divisor]] of two integers, can be written recursively. − − = gcd(259, 111) − − = gcd (259,111) − − − − = gcd(111, 259% 111) − − = gcd (111,259% 111) − − '' − − = gcd(111, 37) − − = gcd (111,37) − − Function definition'': − − = gcd(37, 111% 37) − − = gcd (37,111% 37) − − :<math> \gcd(x,y) = − − = gcd(37, 0) − − = gcd (37,0) − − \begin{cases} − − = 37 − − = 37 − − x & \mbox{if } y = 0 \\ − − |} − − |} − − \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\ − − \end{cases} − − 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. − − 上面的递归程序是尾递归的; 它等价于迭代算法，上面显示的计算显示了由消除尾调用的语言执行的计算步骤。下面是使用显式迭代的相同算法的一个版本，适用于不消除尾部调用的语言。通过在变量 x 和 y 中完全保持其状态并使用循环构造，程序避免了进行递归调用和增长调用堆栈。 − − </math> − − − − {| class="wikitable" − − { | class = “ wikitable” − − {| class="wikitable" − − |- − − |- − − |- − − ! Pseudocode (iterative): − − !伪代码(迭代) : − − ! [[Pseudocode]] (recursive): − − |- − − |- − − |- − − | − − | − − | − − function gcd is:<br /> − − 函数 gcd 是: < br/> − − '''function''' gcd is: − − input: integer x, integer y such that x >= y and y >= 0 − − 输入: 整数 x，整数 y 使得 x > = y 和 y > = 0 − − '''input''': integer ''x'', integer ''y'' such that ''x'' > 0 and ''y'' >= 0 − − <br /> − − < br/> − − <br /> − − 1. create new variable called remainder − − 1. 创建名为 remainder 的新变量 − − 1. if ''y'' is 0, '''return''' ''x'' − − <br /> − − < br/> − − 2. otherwise, '''return''' [ gcd( ''y'', (remainder of ''x''/''y'') ) ] − − 2. begin loop − − 2. begin loop − − <br /> − − 1. if y is zero, exit loop − − 1. 如果 y = 0，退出循环 − − '''end''' gcd − − 2. set remainder to the remainder of x/y − − 2. 将余数设为 x/y 的余数 − − |} − − 3. set x to y − − 3. 设置 x 为 y − − − − 4. set y to remainder − − 4. 设 y 为余数 − − [[Recurrence relation]] for greatest common divisor, where <math>x \% y</math> expresses the [[remainder]] of <math>x / y</math>: − − 5. repeat loop − − 5. 重复循环 − − − − <br /> − − < br/> − − :<math>\gcd(x,y) = \gcd(y, x \% y)</math> if <math>y \neq 0</math> − − 3. return x − − 3. return x − − :<math>\gcd(x,0) = x</math> − − <br /> − − < br/> − − − − end gcd − − 末端 gcd − − {| class="wikitable" − − |} − − |} − − |- − − ! Computing the recurrence relation for x = 27 and y = 9: − − 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. − − 迭代算法需要一个临时变量，即使给出了辗转相除法的知识，也很难通过简单的检查来理解这个过程，尽管这两种算法的步骤非常相似。 − − |- − − | − − gcd(27, 9) = gcd(9, 27% 9) − − Towers of Hanoi − − 河内塔 − − = gcd(9, 0) − − = 9 − − |- − − The Towers of Hanoi is a mathematical puzzle whose solution illustrates recursion. 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? − − 河内塔是一个数学谜题，它的解决方案说明了递归。有三个钉子，可以容纳成堆的磁盘不同直径。较大的圆盘永远不可能堆叠在较小的圆盘上。从一个钉子上的 n 个磁盘开始，它们必须一次移动到另一个钉子上。移动堆栈的最小步骤数是多少？ − − ! Computing the recurrence relation for x = 111 and y = 259: − − |- − − Function definition: − − 功能定义: − − | − − <math> \operatorname{hanoi}(n) = − − (n) = − − gcd(111, 259) = gcd(259, 111% 259) − − \begin{cases} − − 开始{ cases } − − = gcd(259, 111) − − 1 & \mbox{if } n = 1 \\ − − 1 & mbox { if } n = 1 − − = gcd(111, 259% 111) − − 2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\ − − 2 cdot operatorname { hanoi }(n-1) + 1 & mbox { if } n > 1 − − = gcd(111, 37) − − \end{cases} − − 结束{ cases } − − = gcd(37, 111% 37) − − </math> − − 数学 − − = gcd(37, 0) − − = 37 − − Recurrence relation for hanoi: − − 河内递回关系式: − − |} − − <math>h_n = 2h_{n-1}+1</math> − − 2h { n-1} + 1 </math > − − − − <math>h_1 = 1</math> − − 1 = 1 </math > − − 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. − − − − {| class="wikitable" − − { | class = “ wikitable” − − {| class="wikitable" − − |- − − |- − − |- − − ! Computing the recurrence relation for n = 4: − − !计算 n = 4的递回关系式: − − ! Pseudocode (iterative): − − |- − − |- − − |- − − | − − | − − | − − hanoi(4) = 2*hanoi(3) + 1 − − 河内(4) = 2 * 河内(3) + 1 − − '''function''' gcd is:<br /> − − = 2*(2*hanoi(2) + 1) + 1 − − = 2 * (2 * 河内(2) + 1) + 1 − − '''input''': integer ''x'', integer ''y'' such that ''x'' >= ''y'' and ''y'' >= 0 − − = 2*(2*(2*hanoi(1) + 1) + 1) + 1 − − = 2 * (2 * (2 * 河内(1) + 1) + 1) + 1 − − <br /> − − = 2*(2*(2*1 + 1) + 1) + 1 − − = 2*(2*(2*1 + 1) + 1) + 1 − − 1. '''create''' new variable called ''remainder'' − − = 2*(2*(3) + 1) + 1 − − = 2*(2*(3) + 1) + 1 − − <br /> − − = 2*(7) + 1 − − = 2*(7) + 1 − − 2. '''begin''' loop − − = 15 − − = 15 − − 1. if ''y'' is zero, '''exit''' loop − − |} − − |} − − 2. '''set''' ''remainder'' to the remainder of x/y − − <br /> − − < br/> − − 3. '''set''' x to y − − 4. '''set''' y to ''remainder'' − − Example implementations: − − 实现示例: − − 5. '''repeat''' loop − − <br /> − − {| class="wikitable" − − { | class = “ wikitable” − − 3. '''return''' ''x'' − − |- − − |- − − <br /> − − ! Pseudocode (recursive): − − !伪代码(递归) : − − '''end''' gcd − − |- − − |- − − |} − − | − − | − − − − function hanoi is:<br /> − − 函数 hanoi 是: < br/> − − 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. − − input: integer n, such that n >= 1 − − 输入: 整数 n，使得 n > = 1 − − − − <br /> − − < br/> − − ====Towers of Hanoi==== − − 1. if n is 1 then return 1 − − 1. 如果 n 是1，那么返回1 − − [[File:Tower of Hanoi.jpeg|thumb|Towers of Hanoi]] − − <br /> − − < br/> − − {{main|Towers of Hanoi}} − − 2. return [2 * [call hanoi(n-1)] + 1] − − 2. return [2 * [致电河内(n-1)] + 1] − − − − <br /> − − < br/> − − 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 − − end hanoi − − end 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? − − − − Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula. − − 虽然不是所有的递归函数都有一个显式的解，汉诺塔序列可以简化为一个黎曼显式公式。 − − ''Function definition'': − − {| class="wikitable" − − { | class = “ wikitable” − − :<math> \operatorname{hanoi}(n) = − − |- − − |- − − \begin{cases} − − ! An explicit formula for Towers of Hanoi: − − !河内塔的黎曼显式公式: − − 1 & \mbox{if } n = 1 \\ − − |- − − |- − − 2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\ − − | − − | − − \end{cases} − − h<sub>1</sub> = 1 = 2<sup>1</sup> - 1 − − H < sub > 1 </sub > = 1 = 2 < sup > 1 </sup >-1 − − </math> − − h<sub>2</sub> = 3 = 2<sup>2</sup> - 1 − − H < sub > 2 </sub > = 3 = 2 < sup > 2 </sup >-1 − − − − h<sub>3</sub> = 7 = 2<sup>3</sup> - 1 − − H < sub > 3 </sub > = 7 = 2 < sup > 3 </sup >-1 − − ''Recurrence relation for hanoi'': − − h<sub>4</sub> = 15 = 2<sup>4</sup> - 1 − − H < sub > 4 </sub > = 15 = 2 < sup > 4 </sup >-1 − − :<math>h_n = 2h_{n-1}+1</math> − − h<sub>5</sub> = 31 = 2<sup>5</sup> - 1 − − H < sub > 5 </sub > = 31 = 2 < sup > 5 </sup >-1 − − :<math>h_1 = 1</math> − − h<sub>6</sub> = 63 = 2<sup>6</sup> - 1 − − H < sub > 6 </sub > = 63 = 2 < sup > 6 </sup >-1 − − − − h<sub>7</sub> = 127 = 2<sup>7</sup> - 1 − − H < sub > 7 </sub > = 127 = 2 < sup > 7 </sup >-1 − − {| class="wikitable" − − |- − − In general: − − 一般而言: − − ! Computing the recurrence relation for n = 4: − − h<sub>n</sub> = 2<sup>n</sup> - 1, for all n >= 1 − − H < sub > n </sub > = 2 < sup > n </sup >-1，对于所有 n > = 1 − − − − |} − − |} − − | − − hanoi(4) = 2*hanoi(3) + 1 − − = 2*(2*hanoi(2) + 1) + 1 − − 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. − − 二进制搜索算法是一种通过在每次递归过程中将数组切成两半来搜索单个元素的排序数组的方法。技巧是在数组中心附近选择一个中点，将该点的数据与正在搜索的数据进行比较，然后对三个可能的条件之一做出响应: 数据在中点处被找到，数据在中点处大于正在搜索的数据，或者中点处的数据小于正在搜索的数据。 − − = 2*(2*(2*hanoi(1) + 1) + 1) + 1 − − = 2*(2*(2*1 + 1) + 1) + 1 − − 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. − − 递归在这个算法中被使用，因为每次传递一个新数组是通过将旧数组切成两半来创建的。然后递归地调用二进制搜索过程，这次是在新的(和更小的)数组上。通常通过操作开始和结束索引来调整数组的大小。该算法显示了一个对数的增长顺序，因为它实际上是在每次通过时将问题域分成两半。 − − = 2*(2*(3) + 1) + 1 − − = 2*(7) + 1 − − Example implementation of binary search in C: − − 用 c 语言实现二进制搜索的示例: − − = 15 − − |} − − <syntaxhighlight lang="C"> − − < syntaxhighlight lang = " c" > − − <br /> − − /* − − /* − − − − Call binary_search with proper initial conditions. − − 用合适的初始条件调用二进制搜索。 − − Example implementations: − − − − INPUT: − − 输入: − − {| class="wikitable" − − data is an array of integers SORTED in ASCENDING order, − − Data 是按 ASCENDING 顺序排序的整数数组, − − |- − − toFind is the integer to search for, − − 是要搜索的整数, − − ! [[Pseudocode]] (recursive): − − count is the total number of elements in the array − − count 是数组中元素的总数 − − |- − − | − − OUTPUT: − − 产出: − − '''function''' hanoi is:<br /> − − result of binary_search − − 二进制搜索的结果 − − '''input''': integer ''n'', such that ''n'' >= ''1'' − − <br /> − − 1. '''if''' n is 1 '''then return''' 1 − − int search(int *data, int toFind, int count) − − Int search (int * data，int toFind，int count) − − <br /> − − { − − { − − 2. '''return''' [2 * ['''call''' hanoi(n-1)] + 1] − − // Start = 0 (beginning index) − − //Start = 0(开始索引) − − <br /> − − // End = count - 1 (top index) − − //End = count-1(top index) − − '''end''' hanoi − − return binary_search(data, toFind, 0, count-1); − − 返回二进制搜索(data，toFind，0，count-1) ; − − |} − − } − − } − − − − Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.<ref>{{harvnb|Epp|1995|pp=447–448: An Explicit Formula for the Tower of Hanoi Sequence − − /* − − /* − − }}</ref> − − Binary Search Algorithm. − − 二进制搜索算法。 − − {| class="wikitable" − − |- − − INPUT: − − 输入: − − ! An explicit formula for Towers of Hanoi: − − data is a array of integers SORTED in ASCENDING order, − − Data 是按 ASCENDING 顺序排序的整数数组, − − |- − − toFind is the integer to search for, − − 是要搜索的整数, − − | − − start is the minimum array index, − − 开始是最小数组索引, − − h<sub>1</sub> = 1 = 2<sup>1</sup> - 1 − − end is the maximum array index − − end 是最大数组索引 − − h<sub>2</sub> = 3 = 2<sup>2</sup> - 1 − − OUTPUT: − − 产出: − − h<sub>3</sub> = 7 = 2<sup>3</sup> - 1 − − position of the integer toFind within array data, − − 整数在数组数据中的位置, − − h<sub>4</sub> = 15 = 2<sup>4</sup> - 1 − − -1 if not found − − - 如未能找到1个 − − h<sub>5</sub> = 31 = 2<sup>5</sup> - 1 − − h<sub>6</sub> = 63 = 2<sup>6</sup> - 1 − − int binary_search(int *data, int toFind, int start, int end) − − Int binary _ search (int * data，int toFind，int start，int end) − − h<sub>7</sub> = 127 = 2<sup>7</sup> - 1 − − { − − { − − − − //Get the midpoint. − − //得到中点。 − − In general: − − int mid = start + (end - start)/2; //Integer division − − Int mid = start + (end-start)/2;//Integer division − − h<sub>n</sub> = 2<sup>n</sup> - 1, for all n >= 1 − − |} − − //Stop condition. − − //停止状态。 − − − − if (start > end) − − 如果(开始 > 结束) − − ====Binary search==== − − return -1; − − 报税表ー1; − − 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. − − else if (data[mid] == toFind) //Found? − − 否则(data [ mid ] = = toFind)//Found？ − − − − return mid; − − 中期回报; − − 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. − − else if (data[mid] > toFind) //Data is greater than toFind, search lower half − − 如果(Data [ mid ] > toFind)//Data 大于 toFind，则搜索下半部分 − − − − return binary_search(data, toFind, start, mid-1); − − 返回二进制搜索(data，toFind，start，mid-1) ; − − Example implementation of binary search in C: − − else //Data is less than toFind, search upper half − − Else//Data 小于 toFind，搜索上半部分 − − − − return binary_search(data, toFind, mid+1, end); − − 返回二进制搜索(data，toFind，mid + 1，end) ; − − <syntaxhighlight lang="C"> − − } − − } − − /* − − </syntaxhighlight> − − </syntaxhighlight > − − Call binary_search with proper initial conditions. − − − − INPUT: − − data is an array of integers SORTED in ASCENDING order, − − toFind is the integer to search for, − − An important application of recursion in computer science is in defining dynamic data structures such as lists and 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. − − 递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。根据运行时需求，递归数据结构可以动态增长到理论上的无限大小; 相反，静态数组的大小必须在编译时设置。 − − count is the total number of elements in the array − − − − <blockquote> − − < 我们的目标是什么 > − − OUTPUT: − − "Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms." − − “当基础问题或要处理的数据以递归方式定义时，递归算法尤其适用。” − − result of binary_search − − </blockquote> − − </blockquote > − − − − */ − − 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. − − 本节中的例子说明了所谓的“结构递归”。这个术语指的是递归过程正在对递归定义的数据执行操作。 − − int search(int *data, int toFind, int count) − − { − − <blockquote> − − < 我们的目标是什么 > − − // Start = 0 (beginning index) − − 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. − − 只要程序员从数据定义中导出模板，函数就使用结构递归。也就是说，函数体中的递归消耗给定复合值的一些直接部分。 − − // End = count - 1 (top index) − − return binary_search(data, toFind, 0, count-1); − − } − − A basic example of short-circuiting is given in depth-first search (DFS) of a binary tree; see binary trees section for standard recursive discussion. − − 短路的一个基本例子是在二叉树的深度优先搜索中给出的; 参见二叉树部分的标准递归讨论。 − − − − /* − − The standard recursive algorithm for a DFS is: − − DFS 的标准递归算法是: − − Binary Search Algorithm. − − − − INPUT: − − data is a array of integers SORTED in ASCENDING order, − − In short-circuiting, this is instead: − − 相反，在短路情况下，这是: − − toFind is the integer to search for, − − start is the minimum array index, − − end is the maximum array index − − OUTPUT: − − In terms of the standard steps, this moves the base case check before the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null). − − 根据标准步骤，这将基本案例检查移动到递归步骤之前。或者，可以分别将它们视为基本用例和递归步骤的不同形式。请注意，当树本身为空(根节点为 Null)时，需要一个包装函式来处理这种情况。 − − position of the integer toFind within array data, − − -1 if not found − − In the case of a perfect binary tree of height h, there are 2<sup>h+1</sup>−1 nodes and 2<sup>h+1</sup> Null pointers as children (2 for each of the 2<sup>h</sup> leaves), so short-circuiting cuts the number of function calls in half in the worst case. − − 对于高度为 h 的完美二叉树，有2个 < sup > h + 1 </sup > & minus; 1个节点和2个 < sup > h + 1 </sup > 空指针作为子节点(2个 < sup > h </sup > 叶子) ，因此在最坏的情况下，短路将函数调用的数量减半。 − − */ − − int binary_search(int *data, int toFind, int start, int end) − − In C, the standard recursive algorithm may be implemented as: − − 在 c 语言中，标准的递归算法可以实现为: − − { − − <syntaxhighlight lang="C"> − − < syntaxhighlight lang = " c" > − − //Get the midpoint. − − bool tree_contains(struct node *tree_node, int i) { − − 包含(struct node * tree _ node，int i){ − − int mid = start + (end - start)/2; //Integer division − − if (tree_node == NULL) − − 如果(tree _ node = = NULL) − − − − return false; // base case − − 返回 false;//base case − − //Stop condition. − − else if (tree_node->data == i) − − Else if (tree _ node-> data = i) − − if (start > end) − − return true; − − 返回真; − − return -1; − − else − − 别的 − − else if (data[mid] == toFind) //Found? − − return tree_contains(tree_node->left, i) || − − Return tree _ contains (tree _ node-> left，i) | | − − return mid; − − tree_contains(tree_node->right, i); − − Tree _ contains (tree _ node-> right，i) ; − − else if (data[mid] > toFind) //Data is greater than toFind, search lower half − − } − − } − − return binary_search(data, toFind, start, mid-1); − − </syntaxhighlight> − − </syntaxhighlight > − − else //Data is less than toFind, search upper half − − return binary_search(data, toFind, mid+1, end); − − The short-circuited algorithm may be implemented as: − − 短路算法的实现方式如下: − − } − − </syntaxhighlight> − − <syntaxhighlight lang="C"> − − < syntaxhighlight lang = " c" > − − − − // Wrapper function to handle empty tree − − //包装函式处理空树 − − ===Recursive data structures (structural recursion)=== − − bool tree_contains(struct node *tree_node, int i) { − − 包含(struct node * tree _ node，int i){ − − {{main|Recursive data type}} − − if (tree_node == NULL) − − 如果(tree _ node = = NULL) − − − − return false; // empty tree − − 返回 false;//空树 − − 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. − − else − − 别的 − − − − return tree_contains_do(tree_node, i); // call auxiliary function − − 返回树 _ contains _ do (tree _ node，i) ;//调用辅助函数 − − <blockquote> − − } − − } − − "Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."<ref>{{harvnb|Wirth|1976|p=127}}</ref> − − </blockquote> − − // Assumes tree_node != NULL − − //假设树 _ 节点! = NULL − − − − bool tree_contains_do(struct node *tree_node, int i) { − − 包含 _ do (struct node * tree _ node，int i){ − − 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. − − if (tree_node->data == i) − − 如果(tree _ node-> data = i) − − − − return true; // found − − 返回 true;//found − − <blockquote> − − else // recurse − − Else/recurse − − 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"/> − − return (tree_node->left && tree_contains_do(tree_node->left, i)) || − − 返回(tree _ node-> left & tree _ contains _ do (tree _ node-> left，i) | | − − </blockquote> − − (tree_node->right && tree_contains_do(tree_node->right, i)); − − (tree _ node-> right & & tree _ contains _ do (tree _ node-> right，i)) ; − − − − } − − } − − ====Linked lists==== − − </syntaxhighlight> − − </syntaxhighlight > − − {{main|Linked list}} − − − − Note the use of short-circuit evaluation of the Boolean && (AND) operators, so that the recursive call is only made if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a bool, so the overall expression evaluates to a bool. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entire control flow of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency. − − 注意布尔 & & (AND)操作符的短路求值，这样只有当节点有效时才进行递归调用(非 null)。注意，虽然 AND 中的第一个项是指向一个节点的指针，但第二个项是 bool，因此整个表达式的计算结果为 bool。这是递归短路中常用的习惯用法。这是在布尔运算符 | | (OR)的短路求值之外的，只有在左子运算符失败时才检查右子运算符。事实上，这些函数的整个控制流可以用 return 语句中的一个布尔表达式替换，但是易读性对效率没有任何好处。 − − 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. − − − − <syntaxhighlight lang="C"> − − Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is merge sort, which is often implemented by switching to the non-recursive insertion sort when the data is sufficiently small, as in the tiled merge sort. Hybrid recursive algorithms can often be further refined, as in Timsort, derived from a hybrid merge sort/insertion sort. − − 由于重复函数调用和返回的开销，递归算法对于小数据通常效率低下。由于这个原因，递归算法的有效实现通常从递归算法开始，但是当输入变小时切换到不同的算法。一个重要的例子是合并排序，当数据足够小时，通常通过切换到非递归插入排序来实现，就像在分片合并排序中那样。混合递归算法通常可以进一步细化，比如在 Timsort，它源自混合合并排序/插入排序。 − − struct node − − { − − int data; // some integer data − − Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit call stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used. In imperative programming, iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in functional languages recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable. − − 递归和迭代具有同样的表达能力: 递归可以用一个显式调用堆栈的迭代代替，而迭代可以用尾递归代替。哪种方法更可取取决于所考虑的问题和所使用的语言。在命令式编程中，迭代是首选的，特别是对于简单的递归，因为它避免了函数调用和调用堆栈管理的开销，但递归通常用于多重递归。相比之下，在函数式语言中，递归是首选的，尾部递归优化的开销很小。使用迭代实现算法可能不容易实现。 − − struct node *next; // pointer to another struct node − − }; − − Compare the templates to compute x<sub>n</sub> defined by x<sub>n</sub> = f(n, x<sub>n-1</sub>) from x<sub>base</sub>: − − 比较由 x < sub > n </sub > 定义的计算 x < sub > n </sub > = f (n，x < sub > n-1 </sub >)和 x < sub > base </sub > : − − </syntaxhighlight> − − {| − − {| − − − − |- − − |- − − 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. − − | − − | − − − − function recursive(n) − − 函数递归(n) − − <syntaxhighlight lang="C"> − − if n == base − − 如果 n = 基 − − void list_print(struct node *list) − − return x<sub>base</sub> − − 返回 x < sub > base </sub > − − { − − else − − 别的 − − if (list != NULL) // base case − − return f(n, recursive(n-1)) − − 返回 f (n，递归(n-1)) − − { − − || − − || − − printf ("%d ", list->data); // print integer data followed by a space − − function iterative(n) − − 函数迭代(n) − − list_print (list->next); // recursive call on the next node − − x = x<sub>base</sub> − − X = x < sub > base </sub > − − } − − for i = base+1 to n − − 对于 i = base + 1 to n − − } − − x = f(i, x) − − X = f (i，x) − − </syntaxhighlight> − − return x − − 返回 x − − − − |} − − |} − − ====Binary trees==== − − {{main|Binary tree}} − − For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x. − − 命令式语言的开销是定义函数，函数式语言的开销是定义累加器变量 x。 − − − − 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). − − For example, a factorial function may be implemented iteratively in C by assigning to an loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion: − − 例如，一个阶乘函数可以在 c 语言中迭代实现，方法是指派一个循环索引变量和一个累加器变量，而不是通过传递参数和递归返回值: − − <syntaxhighlight lang="C"> − − struct node − − <syntaxhighlight lang="C"> − − < syntaxhighlight lang = " c" > − − { − − unsigned int factorial(unsigned int n) { − − Unsigned int factorial (unsigned int n){ − − int data; // some integer data − − unsigned int product = 1; // empty product is 1 − − Unsigned int product = 1;//empty product is 1 − − struct node *left; // pointer to the left subtree − − while (n) { − − 而(n){ − − struct node *right; // point to the right subtree − − product *= n; − − 产品 * = n; − − }; − − --n; − − -- n; − − </syntaxhighlight> − − } − − } − − − − return product; − − 回收产品; − − 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: − − } − − } − − − − </syntaxhighlight> − − </syntaxhighlight > − − <syntaxhighlight lang="C"> − − // Test if tree_node contains i; return 1 if so, 0 if not. − − int tree_contains(struct node *tree_node, int i) { − − Most programming languages in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's runtime environment keeps track of the various instances of the function (often using a call stack, although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with iterative control constructs and simulating the call stack with a stack explicitly managed by the program. − − 目前使用的大多数编程语言都允许直接指定递归函数和过程。当这样一个函数被调用时，程序的执行期函式库会跟踪这个函数的各种实例(通常使用调用堆栈，尽管也可以使用其他方法)。通过用迭代控制结构替换递归调用，并用程序显式管理的堆栈模拟调用堆栈，可以将每个递归函数转换为一个迭代函数。 − − if (tree_node == NULL) − − return 0; // base case − − Conversely, all iterative functions and procedures that can be evaluated by a computer (see Turing completeness) can be expressed in terms of recursive functions; iterative control constructs such as while loops and for loops are routinely rewritten in recursive form in functional languages. However, in practice this rewriting depends on tail call elimination, which is not a feature of all languages. C, Java, and Python are notable mainstream languages in which all function calls, including tail calls, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may overflow the call stack, although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities. − − 反过来，所有可以由计算机计算的迭代函数和过程(见图灵完备性)都可以用递归函数来表示; 迭代控制结构，例如 while 循环和 for 循环，通常用函数式语言以递归形式重写。然而，在实践中，这种重写依赖于尾部调用消除，这并不是所有语言的一个特性。和 Python 是著名的主流语言，在这些语言中，所有函数调用，包括尾部调用，都可能导致堆栈分配，而这种分配不会通过使用循环结构来实现; 在这些语言中，以递归形式重写的工作迭代程序可能会溢出调用堆栈，尽管尾部调用消除可能是一种语言规范没有涵盖的特性，同一语言的不同实现可能会导致尾部调用消除功能的不同。 − − else if (tree_node->data == i) − − return 1; − − else − − In languages (such as C and Java) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in functional languages, a function call (particularly a tail call) is typically a very fast operation, and the difference is usually less noticeable. − − 在支持迭代循环结构的语言(例如 c 和 Java)中，由于管理堆栈所需的开销和函数调用的相对缓慢，通常与递归程序相关的时间和空间开销很大; 在函数式语言中，函数调用(尤其是尾部调用)通常是一种非常快的操作，而且差异通常不那么明显。 − − return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i); − − } − − As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the compiler used. In languages where looping constructs are preferred, the iterative version may be as much as several orders of magnitude faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration. − − 作为一个具体的例子，上面的“ factorial”示例的递归和迭代实现之间的性能差异在很大程度上取决于所使用的编译器。在循环结构更受欢迎的语言中，迭代版本可能比递归版本快几个数量级。在函数式语言中，两个实现的总体时间差可以忽略不计; 事实上，首先乘以较大的数字而不是较小的数字(这里给出的迭代版本恰好就是这样做的)的成本可能会超过选择迭代所节省的任何时间。 − − </syntaxhighlight> − − At most two recursive calls will be made for any given call to ''tree_contains'' as defined above. − − − − In some programming languages, the maximum size of the call stack is much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoid stack overflows; Python is one such language. Note the caveat below regarding the special case of tail recursion. − − 在一些编程语言中，调用堆栈的最大大小远小于堆中可用的空间，递归算法比迭代算法往往需要更多的堆栈空间。因此，这些语言有时会限制递归的深度，以避免堆栈溢出; Python 就是这样一种语言。注意下面关于尾递归的特殊情况的警告。 − − <syntaxhighlight lang="C"> − − // Inorder traversal: − − void tree_print(struct node *tree_node) { − − Because recursive algorithms can be subject to stack overflows, they may be vulnerable to pathological or malicious input. Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature. Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and exception handling logic may not prevent the corresponding process from being terminated. − − 因为递归算法可能会受到堆栈溢出的影响，所以它们可能容易受到病态或恶意输入的攻击。一些恶意软件专门针对程序的调用堆栈，并利用堆栈固有的递归特性。即使在没有恶意软件的情况下，无限制递归造成的堆栈溢出对程序来说也是致命的，异常处理逻辑可能不会阻止相应的进程被终止。 − − if (tree_node != NULL) { // base case − − tree_print(tree_node->left); // go left − − printf("%d ", tree_node->data); // print the integer followed by a space − − Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is tree traversal as in depth-first search; though both recursive and iterative methods are used, they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include divide-and-conquer algorithms such as Quicksort, and functions such as the Ackermann function. All of these algorithms can be implemented iteratively with the help of an explicit stack, but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution. − − 多重递归问题本质上是递归的，因为它们需要跟踪先前的状态。一个例子是深度优先搜索中的树遍历; 尽管使用了递归和迭代方法，但它们与列表中的遍历和线性搜索形成了对比，后者是单一递归的，因此自然而然地具有迭代法。其他例子包括分而治之的算法，比如 Quicksort，以及诸如阿克曼函数的函数。所有这些算法都可以在显式堆栈的帮助下迭代实现，但是程序员在管理堆栈时所付出的努力，以及由此产生的程序的复杂性，可以说超过了迭代解决方案的任何优点。 − − tree_print(tree_node->right); // go right − − } − − } − − Recursive algorithms can be replaced with non-recursive counterparts. One method for replacing recursive algorithms is to simulate them using heap memory in place of stack memory. An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging. For example, recursive algorithms for matching wildcards, such as Rich Salz' wildmat algorithm, were once typical. Non-recursive algorithms for the same purpose, such as the Krauss matching wildcards algorithm, have been developed to avoid the drawbacks of recursion and have improved only gradually based on techniques such as collecting tests and profiling performance. − − 递归算法可以用非递归算法代替。替换递归算法的一种方法是使用堆内存代替堆内存来模拟它们。另一种方法是完全基于非递归方法开发一个替换算法，这可能很有挑战性。例如，匹配通配符的递归算法，如 Rich Salz 的 wildmat 算法，曾经是典型的。为了克服递归的缺点，已经开发了用于同一目的的非递归算法，如 Krauss 匹配通配符算法，并且只是在收集测试和分析性能等技术的基础上逐步改进。 − − </syntaxhighlight> − − − − 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. − − Tail-recursive functions are functions in which all recursive calls are tail calls and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is not tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a compiler or interpreter that treats tail-recursive calls as jumps rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops. − − 尾递归函数是所有递归调用都是尾部调用的函数，因此不构建任何延迟操作。例如，gcd 函数(如下所示)是尾递归的。相比之下，factorial 函数(也在下面)不是尾递归的; 因为它的递归调用不在尾部位置，所以它构建了延迟的乘法操作，这些操作必须在最后一次递归调用完成后执行。使用将尾递归调用视为跳转而不是函数调用的编译器或解释器，像 gcd 这样的尾递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用命令式语言控制结构，如“ for”和“ while”循环。 − − − − ====Filesystem traversal==== − − {| class="wikitable" − − { | class = “ wikitable” − − 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. − − |- − − |- − − − − ! Tail recursion: − − !尾部递归: − − <syntaxhighlight lang="Java"> − − ! Augmenting recursion: − − !增强递归: − − import java.io.*; − − |- − − |- − − − − |<syntaxhighlight lang="c"> − − | < syntaxhighlight lang = " c" > − − public class FileSystem { − − //INPUT: Integers x, y such that x >= y and y >= 0 − − //INPUT: 整数 x，y 使得 x > = y 和 y > = 0 − − − − int gcd(int x, int y) − − Int gcd (int x，int y) − − public static void main (String [] args) { − − { − − { − − traverse (); − − if (y == 0) − − 如果(y = 0) − − } − − return x; − − 返回 x; − − − − else − − 别的 − − /** − − return gcd(y, x % y); − − 返回 gcd (y，x% y) ; − − * Obtains the filesystem roots − − } − − } − − * Proceeds with the recursive filesystem traversal − − </syntaxhighlight> − − </syntaxhighlight > − − */ − − |<syntaxhighlight lang="c"> − − | < syntaxhighlight lang = " c" > − − private static void traverse () { − − //INPUT: n is an Integer such that n >= 0 − − //INPUT: n 是一个整数，使得 n > = 0 − − File [] fs = File.listRoots (); − − int fact(int n) − − Int fact (int n) − − for (int i = 0; i < fs.length; i++) { − − { − − { − − if (fs[i].isDirectory () && fs[i].canRead ()) { − − if (n == 0) − − 如果(n = 0) − − rtraverse (fs[i]); − − return 1; − − 报税表1; − − } − − else − − 别的 − − } − − return n * fact(n - 1); − − 返回 n * fact (n-1) ; − − } − − } − − } − − − − </syntaxhighlight> − − </syntaxhighlight > − − /** − − |} − − |} − − * Recursively traverse a given directory − − * − − The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the call stack; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time. − − 尾部递归的意义在于，当执行尾部递归调用(或任何尾部调用)时，调用者的返回位置不需要保存在调用堆栈中; 当递归调用返回时，它将直接在先前保存的返回位置上进行分支。因此，在能够识别 tail 调用这个属性的语言中，tail 递归既节省了空间又节省了时间。 − − * @param fd indicates the starting point of traversal − − */ − − private static void rtraverse (File fd) { − − In the simple case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached. Consider this example: − − 在函数只调用自身一次的简单情况下，在递归调用之前放置的指令在递归调用之后放置的任何指令之前每次递归执行一次。后者在达到最大递归后重复执行。考虑一下这个例子: − − File [] fss = fd.listFiles (); − − − − for (int i = 0; i < fss.length; i++) { − − <syntaxhighlight lang="c"> − − < syntaxhighlight lang = " c" > − − System.out.println (fss[i]); − − void recursiveFunction(int num) { − − 函数(int num){ − − if (fss[i].isDirectory () && fss[i].canRead ()) { − − printf("%d\n", num); − − Printf (”% d n” ，num) ; − − rtraverse (fss[i]); − − if (num < 4) − − (数目少于4) − − } − − recursiveFunction(num + 1); − − 递归函数(num1) ; − − } − − } − − } − − } − − </syntaxhighlight> − − </syntaxhighlight > − − − − } − − − − 350px − − </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. The method "rtraverse" is purely a direct example; the method "traverse" is the indirect, which calls "rtraverse". 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. − − <syntaxhighlight lang="c"> − − < syntaxhighlight lang = " c" > − − − − void recursiveFunction(int num) { − − 函数(int num){ − − ==Implementation issues== − − if (num < 4) − − (数目少于4) − − In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include: − − recursiveFunction(num + 1); − − 递归函数(num1) ; − − − − printf("%d\n", num); − − Printf (”% d n” ，num) ; − − * Wrapper function (at top) − − } − − } − − * Short-circuiting the base case, aka "Arm's-length recursion" (at bottom) − − </syntaxhighlight> − − </syntaxhighlight > − − * Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough − − − − 350px − − 350px − − 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. − − − − ===Wrapper function=== − − The 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. − − 递归算法的时间效率可以用一个递回关系式的大 o 符号来表示。它们(通常)可以被简化为一个单一的 Big-O 项。 − − 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. − − − − 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]]. − − − − If the time-complexity of the function is in the form − − 如果函数的时间复杂度在形式中 − − ===Short-circuiting the base case=== − − {{anchor|Arm's-length recursion}} − − <Math>T(n) = a \cdot T(n / b) + f(n)</Math> − − < math > t (n) = a cdot t (n/b) + f (n) </math > − − Short-circuiting the base case, also known as '''arm's-length recursion''', consists of checking the base case ''before'' making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function. − − − − Then the Big O of the time-complexity is thus: − − 因此，时间复杂性的大 o 是: − − Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for {{math|''O''(''n'')}} algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only {{math|''O''(1)}} savings. − − − − Conceptually, short-circuiting can be considered to either have the same base case and recursive step, only checking the base case before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.<ref>{{cite book − − | last = Mongan − − | first = John − − | first2 = Eric |last2=Giguère |first3 = Noah |last3=Kindler − − where represents the number of recursive calls at each level of recursion, represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion. − − 其中表示每个递归级别上递归调用的数量，表示下一级递归的输入小于哪个因子(即。你把问题划分成的小块的数量) ，并且表示函数独立于任何递归(例如:。在递归的每个级别上。 − − | title = Programming Interviews Exposed: Secrets to Landing Your Next Job − − | url = https://archive.org/details/programminginter00mong_658 − − | url-access = limited − − | edition=3rd − − | date= 2013 − − | publisher= [[Wiley (publisher)|Wiley]] − − | page = [https://archive.org/details/programminginter00mong_658/page/n148 115] − − | isbn = 978-1-118-26136-1 − − }}</ref> − − − − ====Depth-first search==== − − 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. − − − − The standard recursive algorithm for a DFS is: − − − − * base case: If current node is Null, return false − − * recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children − − In short-circuiting, this is instead: − − * check value of current node, return true if match, − − * otherwise, on children, if not Null, then recurse. − − − − In terms of the standard steps, this moves the base case check ''before'' the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null). − − − − In the case of a [[perfect binary tree]] of height ''h,'' there are 2<sup>''h''+1</sup>−1 nodes and 2<sup>''h''+1</sup> Null pointers as children (2 for each of the 2<sup>''h''</sup> leaves), so short-circuiting cuts the number of function calls in half in the worst case. − − − − In C, the standard recursive algorithm may be implemented as: − − <syntaxhighlight lang="C"> − − bool tree_contains(struct node *tree_node, int i) { − − if (tree_node == NULL) − − return false; // base case − − else if (tree_node->data == i) − − return true; − − else − − return tree_contains(tree_node->left, i) || − − tree_contains(tree_node->right, i); − − Category:Theoretical computer science − − 类别: 理论计算机科学 + + + + + + + − Category:Recursion+ − 类别: 递归+ + + + − </syntaxhighlight>+ + + + − Category:Computability theory+ − 类别: 可计算性理论+ + + + + + − Category:Articles with example pseudocode+ − 类别: 带有伪代码示例的文章+ − − The short-circuited algorithm may be implemented as: − Category:Programming idioms+ − 类别: 编程习惯用法+ + + + + + + + + + + + + + − Category:Subroutines − 分类: 子程序 − <noinclude> − <small>This page was moved from [[wikipedia:en:Recursion (computer science)]]. Its edit history can be viewed at [[递归/edithistory]]</small></noinclude>+
无编辑摘要
此词条由Solitude初步翻译。
{{Short description|Use of functions that call themselves (on smaller inputs)}}
{{Short description|Use of functions that call themselves (on smaller inputs)}}
[[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 language and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.]]
Tree created using the 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.<ref>{{cite book
In [[computer science]], '''recursion''' is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.<ref>{{cite book
|author-last1 = Graham
|author-last1 = Graham
|author-first1 = Ronald
|author-first1 = Ronald
|author-first2 = Donald |author-last2=Knuth |author-first3=Oren |author-last3=Patashnik
|author-first2 = Donald |author-last2=Knuth |author-first3=Oren |author-last3=Patashnik
| title = Concrete Mathematics
| title = Concrete Mathematics
| date= 1990 |isbn=0-201-55802-5
| date= 1990 |isbn=0-201-55802-5
| ref=harv
| ref=harv
| chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html
| chapter-url = http://www-cs-faculty.stanford.edu/~knuth/gkp.html
| chapter=1: Recurrent Problems
| chapter=1: Recurrent Problems
}}</ref> Such problems can generally be solved by [[Iteration#Computing|iteration]], but this needs to identify and index the smaller instances at programming time. Recursion solves such [[recursion|recursive problems]] by using [[function (computer science)|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
}}</ref> Such problems can generally be solved by [[Iteration#Computing|iteration]], but this needs to identify and index the smaller instances at programming time. Recursion solves such [[recursion|recursive problems]] by using [[function (computer science)|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-last = Epp
|author-last = Epp
|author-first = Susanna
|author-first = Susanna
|title = Discrete Mathematics with Applications
|title = Discrete Mathematics with Applications
|date = 1995
|date = 1995
|isbn = 978-0-53494446-9
|isbn = 978-0-53494446-9
|edition = 2nd
|edition = 2nd
|ref=harv
|ref=harv
|page = [https://archive.org/details/discretemathema000epps/page/427 427]
|page = [https://archive.org/details/discretemathema000epps/page/427 427]
|url = https://archive.org/details/discretemathema000epps/page/427
|url = https://archive.org/details/discretemathema000epps/page/427
}}</ref>
}}</ref>
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.
在计算机科学中，递归是一种解决问题的方法，其解决方案取决于同一问题的较小实例的解决方案。这种问题一般可以通过迭代来解决，但这需要在编程时识别和索引较小的实例。递归通过使用从自己的代码中调用自己的函数来解决这种递归问题。这种方法可以应用于许多类型的问题，递归是计算机科学的核心思想之一。
{{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
|first = Niklaus
|first = Niklaus
|author-link= Niklaus Wirth
|author-link= Niklaus Wirth
|title = Algorithms + Data Structures = Programs
|title = Algorithms + Data Structures = Programs
|publisher = [[Prentice-Hall]]
|publisher = [[Prentice-Hall]]
|isbn = 978-0-13022418-7
|isbn = 978-0-13022418-7
|date = 1976
|date = 1976
|ref=harv
|page = [https://archive.org/details/algorithmsdatast00wirt/page/126 126]
|url = https://archive.org/details/algorithmsdatast00wirt/page/126
}}</ref>}}
{{quote|text= 递归的能力显然在于通过一个有限的语句定义无限对象集的可能性。同样，一个有限递归程序可以描述无限多的计算，即使这个程序不包含显式的重复。
- 尼克劳斯-沃思，《算法+数据结构=程序》，1976年。
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}}.
|page = [https://archive.org/details/algorithmsdatast00wirt/page/126 126]
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}} .
大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些函数式编程语言(例如Clojure)不定义任何循环结构，而只依赖递归来重复调用代码。在可计算性理论中证明了这些递归语言是图灵完备的;这意味着它们与基于{{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}}
{{toclimit|3}}
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.
从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的。
==Recursive functions and algorithms==
递归函数和算法
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 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".
递归函数的定义有一个或多个基本情况，即函数对其产生一个简单结果（不循环）的输入(s)以及一个或多个递归情况，表示程序对其进行递归(调用自身)的输入。例如，阶乘函数可以通过等式0！=1，对于所有n>0，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.
递归案例的工作可以看作是将复杂的输入分解为更简单的输入。在一个设计得当的递归函数中，每一次递归调用，都必须以这样的方式简化输入问题，最终必须达到基本情况。(在正常情况下不打算终止的函数（例如，一些系统和服务器进程）是这方面的例外)。忽略编写基本情况，或不正确地测试它，可能会导致无限循环。
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)".
对于一些函数（例如计算e = 1/0! + 1/1! + 1/2! + 1/3! + ...）输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个参数（比如在我们的系列示例中要添加的术语数量）来提供一个 "停止标准"，以建立基本情况。这样的例子更自然地用共递归来处理，其中输出中的连续项是部分和；这可以通过使用索引参数表示“计算第n项(第n部分和)”来转换为递归。
==Recursive data types==
递归数据类型
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.
{{toclimit|3}}
{{further|Algebraic data type}}
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.
许多计算机程序必须处理或生成任意大量的数据。递归是一种表示程序员不知道确切大小的数据的技术:程序员可以用自引用的定义指定这些数据。自引用定义有两种类型: 归纳定义和协归纳定义。
===Inductively defined data===
归纳定义的数据
{{main|Recursive data type}}
An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, [[linked list]]s can be defined inductively (here, using [[Haskell (programming language)|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>
The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.
The code above specifies a list of strings to be either empty, or a structure that contains a string and a list of strings. The self-reference in the definition permits the construction of lists of any (finite) number of strings.
上面的代码指定了一个字符串列表，要么是空的，要么是包含一个字符串和一个字符串列表的结构。定义中的自引用允许构建任意（有限）数量的字符串列表。
Another example of inductive [[definition]] is the [[natural numbers]] (or positive [[integers]]):
Another example of inductive definition is the natural numbers (or positive integers):
归纳定义的另一个例子是自然数（或正整数）：
<pre>A natural number is either 1 or n+1, where n is a natural number.</pre>
一个自然数是1或 n + 1，其中 n 是一个自然数
Similarly recursive [[definition]]s are often used to model the structure of [[expression (programming)|expressions]] and [[statement (programming)|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:
同样递归定义也经常被用来模拟编程语言中表达式和语句的结构。语言设计者经常用Backus-Naur形式这样的语法来表达语法，这里有一种语法，适用于一个简单的有乘法和加法的算术表达式的语言：
<syntaxhighlight lang="bnf">
<expr> ::= <number>
| (<expr> * <expr>)
| (<expr> + <expr>)
</syntaxhighlight>
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression.
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression.
This says that an expression is either a number, a product of two expressions, or a sum of two expressions. By recursively referring to expressions in the second and third lines, the grammar permits arbitrarily complex arithmetic expressions such as <code>(5 * ((3 * 6) + 8))</code>, with more than one product or sum operation in a single expression.
这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 < code > (5 * ((3 * 6) + 8)) </code > ，在一个表达式中有多个乘积或和运算。
===Coinductively defined data and corecursion===
协同定义的数据和共递归
==Recursive data types==
{{main|Coinduction|Corecursion}}
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
协同归纳数据定义是一种规定了可以对一段数据进行操作的定义；; 通常，自引用的协同归纳定义用于无限大小的数据结构。
A coinductive definition of infinite [[stream (computer science)|streams]] of strings, given informally, might look like this:
A coinductive definition of infinite streams of strings, given informally, might look like this:
A coinductive definition of infinite streams of strings, given informally, might look like this:
非正式给出的无限串流的共归纳定义可能是这样的。
A stream of strings is an object s such that:
head(s) is a string, and
tail(s) is a stream of strings.
字符串流是s这样的对象：
头是字符串，而尾是字符串流。
This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the [[accessor]] functions <code>head</code> and <code>tail</code>—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.
这与字符串列表的归纳定义非常相似；不同的是，这个定义指定了如何访问数据结构的内容，即通过访问函数 的头和尾以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及它可能是由什么创建的。
Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of [[lazy evaluation|lazy]] programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n [[prime numbers]] is one that can be solved with a corecursive program (e.g. [[Fold (higher-order function)#Examples|here]]).
Corecursion is related to coinduction, and can be used to compute particular instances of (possibly) infinite objects. As a programming technique, it is used most often in the context of lazy programming languages, and can be preferable to recursion when the desired size or precision of a program's output is unknown. In such cases the program requires both a definition for an infinitely large (or infinitely precise) result, and a mechanism for taking a finite portion of that result. The problem of computing the first n prime numbers is one that can be solved with a corecursive program (e.g. here).
Corecursion与共归纳相关，可以用来计算（可能）无限对象的特定实例。作为一种编程技术，它最常被用于惰性编程语言中，当程序输出的期望大小或精度未知时，它可以优于递归。在这种情况下，程序既需要一个无限大（或无限精确）结果的定义，又需要一个取该结果有限部分的机制。计算前n个质数的问题是一个可以用一个核心递归程序来解决的问题（例如这里）。
==Types of recursion==
递归的类型
===Single recursion and multiple recursion===
单次递归和多次递归
Recursion that only contains a single self-reference is known as '''{{visible anchor|single recursion}}''', while recursion that contains multiple self-references is known as '''{{visible anchor|multiple recursion}}'''. 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.
只包含单个自引用的递归称为单次递归，而包含多个自引用的递归称为多次递归。单次递归的标准例子包括列表遍历，如线性搜索，或计算阶乘函数，而多次递归的标准例子包括树遍历，如深度优先搜索。
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.
单次递归的效率往往比多次递归高得多，一般可以用迭代计算代替，以线性时间运行，需要恒定的空间。而多次递归则可能需要指数级的时间和空间，而且更根本的是递归，在没有明确的堆栈的情况下，不能用迭代来代替。
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see [[Corecursion#Examples|corecursion: examples]]. A more sophisticated example is using a [[threaded binary tree]], which allows iterative tree traversal, rather than multiple recursion.
Multiple recursion can sometimes be converted to single recursion (and, if desired, thence to iteration). For example, while computing the Fibonacci sequence naively is multiple iteration, as each value requires two previous values, it can be computed by single recursion by passing two successive values as parameters. This is more naturally framed as corecursion, building up from the initial values, tracking at each step two successive values – see corecursion: examples. A more sophisticated example is using a threaded binary tree, which allows iterative tree traversal, rather than multiple recursion.
多次递归有时可以转换为单次递归（如果需要，再转换为迭代）。例如，虽然天真地计算斐波那契序列是多次迭代，因为每个值都需要两个前面的值，但可以通过传递两个连续的值作为参数，通过单递归来计算。这更自然地被定义为共递归。从初始值开始建立，在每一步都跟踪两个连续的值—参见：共递归。一个更复杂的例子是使用线程二叉树，它允许迭代树遍历，而不是多次递归。
===Indirect recursion===
间接递归
{{main|Mutual recursion}}
Most basic examples of recursion, and most of the examples presented here, demonstrate {{anchor|direct recursion}}'''''direct'' recursion''', in which a function calls itself. ''Indirect'' recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if ''f'' calls ''f,'' that is direct recursion, but if ''f'' calls ''g'' which calls ''f,'' then that is indirect recursion of ''f.'' Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.
Most basic examples of recursion, and most of the examples presented here, demonstrate direct recursion, in which a function calls itself. Indirect recursion occurs when a function is called not by itself but by another function that it called (either directly or indirectly). For example, if f calls f, that is direct recursion, but if f calls g which calls f, then that is indirect recursion of f. Chains of three or more functions are possible; for example, function 1 calls function 2, function 2 calls function 3, and function 3 calls function 1 again.
大多数递归的基本例子，以及这里介绍的大多数例子，都是直接递归，即一个函数调用自己。间接递归是指一个函数不是被它自己调用，而是被它调用的另一个函数（直接或间接）调用。例如，如果f调用f，那是直接递归，但如果f调用g，而g又调用f，那就是f的间接递归。三个或更多的函数链是可能的，例如，函数1调用函数2，函数2调用函数3，函数3再调用函数1。
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.
间接递归也叫相互递归，这是一个比较对称的术语，不过这只是强调的不同，而不是概念的不同。也就是说，如果f调用g，然后g又调用f，而f又调用g，单从f的角度看，f是间接递归，而单从g的角度看，是间接递归，而从两者的角度看，f和g是相互递归的。同理，三个或三个以上函数相互调用的函数集也可以称为互递归函数集。
===Anonymous recursion===
匿名递归
{{main|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 function]]s, 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.
递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为匿名递归。
===Structural versus generative recursion===
结构递归与生成递归
{{see also|Structural recursion}}
Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:
Some authors classify recursion as either "structural" or "generative". The distinction is related to where a recursive procedure gets the data that it works on, and how it processes that data:
一些作者将递归分为 "结构性 "或 "生成性"。这种区别与递归程序从哪里获得它所处理的数据以及它如何处理这些数据有关。
{{quote|text=[Functions that consume structured data] typically decompose their arguments into their immediate structural components and then process those components. If one of the immediate components belongs to the same class of data as the input, the function is recursive. For that reason, we refer to these functions as (STRUCTURALLY) RECURSIVE FUNCTIONS.|author=Felleisen, Findler, Flatt, and Krishnaurthi|source=''[[How to Design Programs]]'', 2001<ref name="Felleisen HtDP 2001">{{harvnb|Felleisen|Findler|Flatt|Krishnamurthi|2001|loc= [http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-31.html art V "Generative Recursion]}}
</ref>}}
{{quote|text= 消耗结构化数据的函数通常会将其参数分解为其直接的结构组件，然后对这些组件进行处理。如果其中一个直接组件与输入的数据属于同一类数据，那么这个函数就是递归的。出于这个原因，我们将这些函数称为结构递归函数。
— Felleisen，Findler，Flatt和Krishnaurthi，《如何设计程序》，2001年
Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.
Thus, the defining characteristic of a structurally recursive function is that the argument to each recursive call is the content of a field of the original input. Structural recursion includes nearly all tree traversals, including XML processing, binary tree creation and search, etc. By considering the algebraic structure of the natural numbers (that is, a natural number is either zero or the successor of a natural number), functions such as factorial may also be regarded as structural recursion.
因此，结构递归函数的定义特征是，每次递归调用的参数是原始输入的某个字段的内容。结构递归几乎包括所有的树形遍历，包括XML处理、二进制树的创建和搜索等。考虑到自然数的代数结构（即自然数要么是零，要么是自然数的继任者），阶乘等函数也可视为结构递归。
'''{{visible anchor|Generative recursion}}''' is the alternative:
生成递归是替代方法：
{{quote|text=Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. [[How to Design Programs|''HtDP'' (''How to Design Programs'')]] refers to this kind as generative recursion. Examples of generative recursion include: [[Euclidean algorithm|gcd]], [[quicksort]], [[binary search]], [[mergesort]], [[Newton's method]], [[fractal]]s, and [[adaptive quadrature|adaptive integration]].|author=Matthias Felleisen|source=''Advanced Functional Programming'', 2002<ref name="Felleisen 2002 108">{{Cite book
| last = Felleisen
| first = Matthias
| chapter = Developing Interactive Web Programs |chapterurl=https://books.google.com/books?id=Y3GqCAAAQBAJ&pg=PA108
| date = 2002
| title = Advanced Functional Programming: 4th International School
| editor-last = Jeuring
| editor-first = Johan
| volume =
| page = 108
| publisher = Springer
| isbn = 9783540448334
| url = ftp://nozdr.ru/biblio/kolxo3/Cs/CsLn/Advanced%20Functional%20Programming%204%20conf.,%20AFP%202002%20(LNCS2638,%20Springer,%202003)(ISBN%203540401326)(O)(222s).pdf#page=109
}}
</ref>
}}
许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：gcd、quicksort、二进制搜索、mergesort、牛顿法、分形和自适应集成。
- Matthias Felleisen，《高级函数式编程》，2002年。
This distinction is important in [[Termination analysis#Termination proof|proving termination]] of a function.
This distinction is important in proving termination of a function.
这种区别在证明函数的终止性时很重要。
* All structurally recursive functions on finite ([[Recursive data type|inductively defined]]) data structures can easily be shown to terminate, via [[structural induction]]: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.
通过结构归纳，可以很容易地证明所有有限（归纳定义的）数据结构上的结构递归函数的终止：直观地看，每次递归调用都会接收较小的输入数据，直到达到一个基本情况。
* Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding [[infinite loops]] requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed.
相比之下，生成递归函数不一定会向其递归调用提供较小的输入，因此对其终止的证明不一定那么简单，避免无限循环需要更加谨慎。这些产生式递归函数通常可以解释为核心递归函数--每一步都会产生新的数据，比如牛顿方法中的逐次逼近，而终止这种核心递归需要数据最终满足某个条件，而这个条件不一定有保证。
* In terms of [[loop variant]]s, structural recursion is when there is an obvious loop variant, namely size or complexity, which starts off finite and decreases at each recursive step.
就循环变体而言，结构性递归是指存在明显的循环变体，即大小或复杂度，它开始时是有限的，并在每个递归步骤中减少。
* By contrast, generative recursion is when there is not such an obvious loop variant, and termination depends on a function, such as "error of approximation" that does not necessarily decrease to zero, and thus termination is not guaranteed without further analysis.
与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。
===Coinductively defined data and corecursion===
==Recursive programs==
递归程序
===Recursive procedures===
递归程序
====Factorial====
阶乘
A classic example of a recursive procedure is the function used to calculate the [[factorial]] of a [[natural number]]:
A coinductive data definition is one that specifies the operations that may be performed on a piece of data; typically, self-referential coinductive definitions are used for data structures of infinite size.
A classic example of a recursive procedure is the function used to calculate the factorial of a natural number:
递归过程的一个经典例子是用于计算自然数阶乘的函数:
:<math> \operatorname{fact}(n) =
\begin{cases}
1 & \mbox{if } n = 0 \\
n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\
\end{cases}
</math>
{| class="wikitable"
|-
! [[Pseudocode]] (recursive):
|-
|
'''function''' factorial is:<br />
'''input''': integer ''n'' such that ''n'' >= 0<br />
'''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
<br />
1. if ''n'' is 0, '''return''' 1
2. otherwise, '''return''' [ ''n'' × factorial(''n''-1) ]
<br />
'''end''' factorial
|}
'''函数''' 阶乘是:<br />
'''输入''': 整数 ''n'' 即 ''n'' >= 0<br />
'''输出''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
<br />
1. 如果''n'' 是0, '''返回''' 1
2. 否则, '''返回''' [ ''n'' × 阶乘(''n''-1) ]
<br />
'''结束''' 阶乘
|}
The function can also be written as a [[recurrence relation]]:
该函数也可以写成递归关系：
:<math>b_n = nb_{n-1}</math>
:<math>b_0 = 1</math>
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:
这种对递归关系的评价展示了在评价上述伪代码时将进行的计算。
{| class="wikitable"
|-
! Computing the recurrence relation for n = 4:
计算n = 4的递归关系：
|-
|
b<sub>4</sub> = 4 * b<sub>3</sub><br />
= 4 * (3 * b<sub>2</sub>)
= 4 * (3 * (2 * b<sub>1</sub>))
= 4 * (3 * (2 * (1 * b<sub>0</sub>)))
= 4 * (3 * (2 * (1 * 1)))
= 4 * (3 * (2 * 1))
= 4 * (3 * 2)
= 4 * 6
= 24
|}
This is very similar to an inductive definition of lists of strings; the difference is that this definition specifies how to access the contents of the data structure—namely, via the [[accessor]] functions <code>head</code> and <code>tail</code>—and what those contents may be, whereas the inductive definition specifies how to create the structure and what it may be created from.
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:
这个阶乘函数也可以在不使用递归的情况下，通过使用典型的循环结构来描述，这些循环结构在命令式编程语言中可以找到：
{| class="wikitable"
|-
! Pseudocode (iterative):
|-
|
'''function''' factorial is:<br />
'''input''': integer ''n'' such that ''n'' >= 0<br />
'''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
<br />
1. '''create''' new variable called ''running_total'' with a value of 1
<br />
2. '''begin''' loop
1. if ''n'' is 0, '''exit''' loop
2. '''set''' ''running_total'' to (''running_total'' × ''n'')
3. '''decrement''' ''n''
4. '''repeat''' loop
<br />
3. '''return''' ''running_total''
<br />
'''end''' factorial
|}
'''函数''' 阶乘是:<br />
'''输入''': 整数 ''n'' ，使得 ''n'' >= 0<br />
'''输出''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
<br />
1. '''创建''' 一个名为 ''running_total'' 的新变量，其值为 1
<br />
2. '''开始''' 循环
1. 如果 ''n'' 为 0, 则'''退出''' 循环
2. '''将''' ''running_total'' 设置为 (''running_total'' × ''n'')
3. '''递减''' ''n''
4. '''重复''' 循环
<br />
3. '''返回''' ''running_total''
<br />
'''结束''' 阶乘
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>}}'':
上面的命令代码相当于这个使用累加器变量math|<var>t</var>的数学定义:
:<math>
\begin{array}{rcl}
\operatorname{fact}(n) & = & \operatorname{fact_{acc}}(n, 1) \\
\operatorname{fact_{acc}}(n, t) & = &
{{quote|text=Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. HtDP (How to Design Programs) refers to this kind as generative recursion. Examples of generative recursion include: gcd, quicksort, binary search, mergesort, Newton's method, fractals, and adaptive integration.|author=Matthias Felleisen|source=Advanced Functional Programming, 2002
\begin{cases}
t & \mbox{if } n = 0 \\
\operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n > 0 \\
\end{cases}
\end{array}
</math>
The definition above translates straightforwardly to [[functional programming language]]s such as [[Scheme (programming language)|Scheme]]; this is an example of iteration implemented recursively.
上面的定义可以直接翻译成函数式编程语言，比如Scheme；这是一个递归实现迭代的例子。
====Greatest common divisor====
最大公约数
The [[Euclidean algorithm]], which computes the [[greatest common divisor]] of two integers, can be written recursively.
计算两个整数最大公除数的欧氏算法，可以递归写成。
''
Function definition'':
函数定义：
:<math> \gcd(x,y) =
\begin{cases}
x & \mbox{if } y = 0 \\
\gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\
\end{cases}
</math>
{| class="wikitable"
|-
! [[Pseudocode]] (recursive):
|-
|
'''function''' gcd is:
'''input''': integer ''x'', integer ''y'' such that ''x'' > 0 and ''y'' >= 0
<br />
1. if ''y'' is 0, '''return''' ''x''
2. otherwise, '''return''' [ gcd( ''y'', (remainder of ''x''/''y'') ) ]
<br />
'''end''' gcd
|}
'''函数''' gcd 是:
'''输入''': 整数 ''x'', 整数 ''y'' 使得 ''x'' > 0 且 ''y'' >= 0
<br />
1. 如果 ''y'' 为 0, 则'''返回''' ''x''
2. 否则, '''返回''' [ gcd( ''y'', (''x''/''y''的余数) ) ]
<br />
'''结束''' gcd
[[Recurrence relation]] for greatest common divisor, where <math>x \% y</math> expresses the [[remainder]] of <math>x / y</math>:
最大公约数的递归关系，其中<math>x \% y</math>表示余下的 <math>x / y</math>：
:<math>\gcd(x,y) = \gcd(y, x \% y)</math> if <math>y \neq 0</math>
:<math>\gcd(x,0) = x</math>
{| class="wikitable"
|-
! Computing the recurrence relation for x = 27 and y = 9:
计算x = 27和y = 9的递归关系：
|-
|
gcd(27, 9) = gcd(9, 27% 9)
= gcd(9, 0)
= 9
|-
! Computing the recurrence relation for x = 111 and y = 259:
计算x = 111和y = 259的递归关系：
===Indirect recursion===
|-
|
gcd(111, 259) = gcd(259, 111% 259)
= gcd(259, 111)
= gcd(111, 259% 111)
= gcd(111, 37)
= gcd(37, 111% 37)
= gcd(37, 0)
= 37
|}
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.
上面的递归程序是尾部递归；它相当于一个迭代算法，上面显示的计算显示了一个消除尾部调用的语言将执行的评估步骤。 下面是使用显式迭代的相同算法的一个版本，适用于不消除尾部调用的语言。 通过将其状态完全保持在变量''x''和''y''中，并使用循环结构，该程序避免了递归调用和增加调用栈。
{| class="wikitable"
|-
! Pseudocode (iterative):
|-
|
'''function''' gcd is:<br />
'''input''': integer ''x'', integer ''y'' such that ''x'' >= ''y'' and ''y'' >= 0
<br />
1. '''create''' new variable called ''remainder''
<br />
2. '''begin''' loop
1. if ''y'' is zero, '''exit''' loop
2. '''set''' ''remainder'' to the remainder of x/y
3. '''set''' x to y
4. '''set''' y to ''remainder''
5. '''repeat''' loop
<br />
3. '''return''' ''x''
<br />
'''end''' gcd
|}
'''函数''' gcd 是:<br />
'''输入''': 整数 ''x'', 整数 ''y'' 使得 ''x'' >= ''y'' 且 ''y'' >= 0
<br />
1. '''创建''' 一个名为 ''余数''的新变量
<br />
2. '''开始''' 循环
1. 如果 ''y'' 为0, 则'''退出''' 循环
2. 将 剩下部分设置为x / y 的余数
3. 将x'''设置''' 为y
4. 将y'''设置''' 为 ''余数''
5. '''重复''' 循环
<br />
3. '''返回''' ''x''
<br />
'''结束''' gcd
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.
迭代算法需要一个临时变量，即使给定了欧几里得算法的知识，虽然两种算法的步骤非常相似，但要通过简单的检查来理解其过程是比较困难的。
====Towers of Hanoi====
河内塔
[[File:Tower of Hanoi.jpeg|thumb|Towers of Hanoi]]
河内塔
{{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?
河内塔是一个数学难题，它的解法说明了递归的问题。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？
<math> \operatorname{fact}(n) =
''Function definition'':
函数定义：
:<math> \operatorname{hanoi}(n) =
\begin{cases}
1 & \mbox{if } n = 1 \\
2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\
\end{cases}
</math>
{ fact }(n) =
''Recurrence relation for hanoi'':
河内的递归关系：
:<math>h_n = 2h_{n-1}+1</math>
:<math>h_1 = 1</math>
{| class="wikitable"
|-
! Computing the recurrence relation for n = 4:
计算n = 4的递归关系：
|-
|
hanoi(4) = 2*hanoi(3) + 1
= 2*(2*hanoi(2) + 1) + 1
= 2*(2*(2*hanoi(1) + 1) + 1) + 1
= 2*(2*(2*1 + 1) + 1) + 1
= 2*(2*(3) + 1) + 1
= 2*(7) + 1
= 15
|}
<br />
Example implementations:
示例实现：
===Structural versus generative recursion===
{| class="wikitable"
|-
! [[Pseudocode]] (recursive):
|-
|
'''function''' hanoi is:<br />
'''input''': integer ''n'', such that ''n'' >= ''1''
<br />
1. '''if''' n is 1 '''then return''' 1
<br />
2. '''return''' [2 * ['''call''' hanoi(n-1)] + 1]
<br />
'''end''' hanoi
|}
1 & \mbox{if } n = 0 \\
'''函数''' hanoi 是:<br />
'''输入''': 整数 ''n'', 使得''n'' >= ''1''
<br />
1. '''如果''' n 为 1 '''则返回''' 1
<br />
2. '''返回''' [2 * ['''call''' hanoi(n-1)] + 1]
<br />
'''结束''' hanoi
Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.<ref>{{harvnb|Epp|1995|pp=447–448: An Explicit Formula for the Tower of Hanoi Sequence
}}</ref>
虽然不是所有的递归函数都有明确的解，但河内塔序列可以简化为一个明确的公式。
{| class="wikitable"
|-
! An explicit formula for Towers of Hanoi:
河内塔楼的明确公式：
|-
|
h<sub>1</sub> = 1 = 2<sup>1</sup> - 1
h<sub>2</sub> = 3 = 2<sup>2</sup> - 1
h<sub>3</sub> = 7 = 2<sup>3</sup> - 1
h<sub>4</sub> = 15 = 2<sup>4</sup> - 1
h<sub>5</sub> = 31 = 2<sup>5</sup> - 1
h<sub>6</sub> = 63 = 2<sup>6</sup> - 1
h<sub>7</sub> = 127 = 2<sup>7</sup> - 1
In general:
h<sub>n</sub> = 2<sup>n</sup> - 1, for all n >= 1
|}
通常:
h<sub>n</sub> = 2<sup>n</sup> - 1, 所有n >= 1
====Binary search====
二分搜索
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:
C语言中二分搜索的实现实例:
<syntaxhighlight lang="C">
/*
Call binary_search with proper initial conditions.
以适当的初始条件调用二分搜索
INPUT:
输入
data is an array of integers SORTED in ASCENDING order,
data是按升序排列的整数数组，
toFind is the integer to search for,
toFind是要搜索的整数
count is the total number of elements in the array
count是数组中元素的总数
OUTPUT:
输出
result of binary_search
二分搜索的结果
*/
int search(int *data, int toFind, int count)
{
// Start = 0 (beginning index)
// End = count - 1 (top index)
return binary_search(data, toFind, 0, count-1);
}
/*
Binary Search Algorithm.
二分搜索算法
INPUT:
输入：
data is a array of integers SORTED in ASCENDING order,
data是按升序排列的整数数组，
toFind is the integer to search for,
toFind是要搜索的整数，
start is the minimum array index,
start是最小数组索引，
end is the maximum array index
end是最大数组索引
OUTPUT:
输出：
position of the integer toFind within array data,
整数toFind在数组数据中的位置，
-1 if not found
如果未找到则为-1
*/
int binary_search(int *data, int toFind, int start, int end)
{
//Get the midpoint.
int mid = start + (end - start)/2; //Integer division
//Stop condition.
if (start > end)
return -1;
else if (data[mid] == toFind) //Found?
return mid;
else if (data[mid] > toFind) //Data is greater than toFind, search lower half
return binary_search(data, toFind, start, mid-1);
else //Data is less than toFind, search upper half
return binary_search(data, toFind, mid+1, end);
}
</syntaxhighlight>
|-
===Recursive data structures (structural recursion)===
递归数据结构（结构递归）
{{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.
递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大小；相反，静态数组的大小必须在编译时设定。
<blockquote>
"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."<ref>{{harvnb|Wirth|1976|p=127}}</ref>
"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"
</blockquote>
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.
本节的例子说明了所谓的 "结构递归"。这个术语指的是递归程序是作用于递归定义的数据。
<blockquote>
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"/>
只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数主体中的递归会消耗某个给定复值的直接部分。
</blockquote>
====Linked lists====
链表
{{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.
下面是一个链接列表节点结构的C语言定义。特别注意节点是如何从自身出发来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。
{{quote|text=Many well-known recursive algorithms generate an entirely new piece of data from the given data and recur on it. [[How to Design Programs|''HtDP'' (''How to Design Programs'')]] refers to this kind as generative recursion. Examples of generative recursion include: [[Euclidean algorithm|gcd]], [[quicksort]], [[binary search]], [[mergesort]], [[Newton's method]], [[fractal]]s, and [[adaptive quadrature|adaptive integration]].|author=Matthias Felleisen|source=''Advanced Functional Programming'', 2002<ref name="Felleisen 2002 108">{{Cite book
<syntaxhighlight lang="C">
struct node
{
int data; // some integer data
struct node *next; // pointer to another struct node
};
</syntaxhighlight>
<syntaxhighlight lang="C">
结构 节点
{
int 数据; // 一些整数数据
结构 节点 *next; // 指向另一个结构节点的指针
};
</syntaxhighlight>
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.
由于结构节点数据结构是递归定义的，因此对其进行操作的过程可以自然地作为递归过程实现。下面定义的list_print过程沿着列表进行遍历，直到列表为空(即，列表指针的值为NULL)。对于每个节点，它打印数据元素(一个整数)。在C语言的实现中，列表在list_print过程中保持不变。
< br/>
<syntaxhighlight lang="C">
void list_print(struct node *list)
{
if (list != NULL) // base case
{
printf ("%d ", list->data); // print integer data followed by a space
list_print (list->next); // recursive call on the next node
}
}
</syntaxhighlight>
<syntaxhighlight lang="C">
void list_print(struct node *list)
{
if (list != NULL) // base case
{
printf ("%d ", list->data); // print integer data followed by a space
list_print (list->next); // recursive call on the next node
}
}
</syntaxhighlight>
====Binary trees====
二叉树
{{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).
下面是二叉树节点的一个简单定义。与链表的节点一样，它是按照自身递归地定义的。有两个自引用指针:left(指向左边的子树)和right(指向右边的子树)。
<syntaxhighlight lang="C">
struct node
{
int data; // some integer data
struct node *left; // pointer to the left subtree
struct node *right; // point to the right subtree
};
</syntaxhighlight>
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:
对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：
<syntaxhighlight lang="C">
<br />
// Test if tree_node contains i; return 1 if so, 0 if not.
int tree_contains(struct node *tree_node, int i) {
if (tree_node == NULL)
return 0; // base case
else if (tree_node->data == i)
return 1;
else
return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}
</syntaxhighlight>
At most two recursive calls will be made for any given call to ''tree_contains'' as defined above.
对于上面定义的''tree_contains''的任何给定调用，最多会有两次递归调用。
<syntaxhighlight lang="C">
// Inorder traversal:
void tree_print(struct node *tree_node) {
if (tree_node != NULL) { // base case
tree_print(tree_node->left); // go left
printf("%d ", tree_node->data); // print the integer followed by a space
tree_print(tree_node->right); // go right
}
}
</syntaxhighlight>
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.
上面的例子说明了二叉树的按顺序遍历。二分搜索树是二叉树的一种特殊情况，其中每个节点的数据元素是按顺序排列的。
====Filesystem traversal====
文件系统遍历
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.
由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树形遍历非常相似，因此树形遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的预排序遍历的示例。
<syntaxhighlight lang="Java">
import java.io.*;
public class FileSystem {
public static void main (String [] args) {
traverse ();
}
/**
* Obtains the filesystem roots
* Proceeds with the recursive filesystem traversal
*/
private static void traverse () {
File [] fs = File.listRoots ();
for (int i = 0; i < fs.length; i++) {
if (fs[i].isDirectory () && fs[i].canRead ()) {
rtraverse (fs[i]);
}
}
}
/**
* Recursively traverse a given directory
*
* @param fd indicates the starting point of traversal
*/
private static void rtraverse (File fd) {
File [] fss = fd.listFiles ();
for (int i = 0; i < fss.length; i++) {
System.out.println (fss[i]);
if (fss[i].isDirectory () && fss[i].canRead ()) {
rtraverse (fss[i]);
}
}
}
}
</syntaxhighlight>
[ math > b _ n = nb _ n-1}[ math >
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==
执行问题
In actual implementation, rather than a pure recursive function (single check for base case, otherwise recursive step), a number of modifications may be made, for purposes of clarity or efficiency. These include:
在实际执行中，为了清晰或效率，可能会进行大量的修改，而不是纯粹的递归函数(对基本情况进行单一检查，否则递归步骤)。这些修改包括：
* Wrapper function (at top)
包装函数（在顶部）
* Short-circuiting the base case, aka "Arm's-length recursion" (at bottom)
基本情况下的短路，也就是 "正常递归"（在底部）
* Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough
混合算法（在底部）--一旦数据足够小，就切换到不同的算法
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.
在优雅的基础上，包装函数一般都会被认可，而对基本情况的短路则是不屑一顾的，尤其是在学术界。混合算法往往是为了提高效率，减少小情况下递归的开销，正常递归是一种特殊情况。
===Wrapper function===
包装函数
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.
包装函数是指直接调用但本身不递归的函数，而是调用一个单独的辅助函数，它实际上进行递归。
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]].
包装器函数可用于验证参数(这样递归函数就可以跳过这些参数)、执行初始化(分配内存、初始化变量)，特别是对于辅助变量，如“递归级别”或备忘的部分计算，以及处理异常和错误。在支持嵌套函数的语言中，辅助函数可以嵌套在包装器函数内部，并使用共享的作用域。在没有嵌套函数的情况下，辅助函数是一个独立的函数，如果可能的话，辅助函数是私有的(因为它们没有被直接调用) ，通过使用传递引用的方式与包装函数共享信息。
|-
===Short-circuiting the base case===
基本情况下的短路
{{anchor|Arm's-length recursion}}
Short-circuiting the base case, also known as '''arm's-length recursion''', consists of checking the base case ''before'' making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function.
基本情况下的短路，也称为正常递归，包括在进行递归调用之前检查基本情况--即检查下一次调用是否为基本情况，而不是调用后再检查基本情况。特别是出于效率的考虑，为了避免函数调用后立即返回的开销，才进行了短路。需要注意的是，由于基本情况已经被检查过了（紧接在递归步骤之前），所以不需要单独检查基本情况，但是当整体递归从基本情况本身开始时，确实需要使用一个封装函数来处理这种情况。例如，在阶乘函数中，正确的基本情况是0！=1，而对于1！立即返回1是短路，可能会漏掉0；这可以通过包装函数来缓解。
Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for {{math|''O''(''n'')}} algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only {{math|''O''(1)}} savings.
短路主要是在遇到很多基本情况的时候，比如树上的空指针，它在函数调用次数上是可以线性计算的，因此对于O(n)算法来说，可以大大节省成本；下面以深度优先搜索为例进行说明。树上的短路对应于将叶子（没有子节点的非空节点）作为基本情况，而不是将空节点作为基本情况。如果只有一个基本情况，比如在计算阶乘的时候，短路只能节省O(1)。
Conceptually, short-circuiting can be considered to either have the same base case and recursive step, only checking the base case before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.<ref>{{cite book
| last = Mongan
| first = John
| first2 = Eric |last2=Giguère |first3 = Noah |last3=Kindler
| title = Programming Interviews Exposed: Secrets to Landing Your Next Job
| url = https://archive.org/details/programminginter00mong_658
| url-access = limited
| edition=3rd
| date= 2013
| publisher= [[Wiley (publisher)|Wiley]]
| page = [https://archive.org/details/programminginter00mong_658/page/n148 115]
| isbn = 978-1-118-26136-1
}}</ref>
从概念上讲，短路可以认为是具有相同的基本情况和递归步骤，只在递归前检查基本情况，也可以认为是具有不同的基本情况（比标准基本情况去掉一步）和更复杂的递归步骤，即 "先检查有效再递归"，如在树中考虑叶子节点而不是空节点作为基本情况。由于短路的流程比较复杂，相比标准递归中基本情况和递归步骤的清晰分离，短路往往被认为是风格不佳，尤其是在学术界。
|-
====Depth-first search====
深度优先搜索
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.
在二叉树的深度优先搜索（DFS）中给出了一个短路的基本例子；标准递归讨论见二叉树部分。
The standard recursive algorithm for a DFS is:
DFS的标准递归算法是：
* base case: If current node is Null, return false
基本情况： 如果当前节点为Null，返回false。
* All structurally recursive functions on finite ([[Recursive data type|inductively defined]]) data structures can easily be shown to terminate, via [[structural induction]]: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.
* recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children
递归步骤：否则，检查当前节点的值，如果匹配则返回true，否则对子节点进行递归。
In short-circuiting, this is instead:
在短路的情况下，这反而是：
* check value of current node, return true if match,
检查当前节点的值，如果匹配则返回true，
* otherwise, on children, if not Null, then recurse.
否则，在子代上，如果不是Null，则递归。
In terms of the standard steps, this moves the base case check ''before'' the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null).
就标准步骤而言，这将基本情况检查移到了递归步骤之前。或者，这些可以分别被认为是基本情况和递归步骤的不同形式。注意，这需要一个封装函数来处理树本身为空的情况（根节点为Null）。
In the case of a [[perfect binary tree]] of height ''h,'' there are 2<sup>''h''+1</sup>−1 nodes and 2<sup>''h''+1</sup> Null pointers as children (2 for each of the 2<sup>''h''</sup> leaves), so short-circuiting cuts the number of function calls in half in the worst case.
在高度为h的完美二叉树的情况下，有2h+1-1个节点和2h+1个Null指针作为子节点（2h个叶子各2个），所以在最坏的情况下，短路可以将函数调用的次数减少一半。
In C, the standard recursive algorithm may be implemented as:
= 4 * (3 * (2 * b < sub > 1 </sub >))
在C语言中，标准的递归算法可以实现为：
<syntaxhighlight lang="C">
bool tree_contains(struct node *tree_node, int i) {
if (tree_node == NULL)
return false; // base case
else if (tree_node->data == i)
return true;
else
return tree_contains(tree_node->left, i) ||
tree_contains(tree_node->right, i);
}
</syntaxhighlight>
The short-circuited algorithm may be implemented as:
短路算法可以实现为：
<syntaxhighlight lang="C">
// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
if (tree_node == NULL)
return false; // empty tree
else
return tree_contains_do(tree_node, i); // call auxiliary function
}
// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
if (tree_node->data == i)
return true; // found
else // recurse
return (tree_node->left && tree_contains_do(tree_node->left, i)) ||
(tree_node->right && tree_contains_do(tree_node->right, i));
}
</syntaxhighlight>
Note the use of [[short-circuit evaluation]] of the Boolean && (AND) operators, so that the recursive call is only made if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a bool, so the overall expression evaluates to a bool. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entire [[control flow]] of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.
请注意布尔&& (AND)运算符的短路评估的使用，因此只有当节点有效(非Null)时才会进行递归调用。请注意，AND中的第一项是指向节点的指针，第二项是一个布尔，所以整体表达式评价为一个布尔。这是递归短路中常见的一个成语。这是在布尔||（OR）运算符的短路评价之外，只有在左子运算失败时才检查右子运算符。事实上，这些函数的整个控制流程可以用返回语句中的一个布尔表达式来代替，但可读性受到影响，对效率却没有任何好处。
===Hybrid algorithm===
混合算法
Recursive algorithms are often inefficient for small data, due to the overhead of repeated function calls and returns. For this reason efficient implementations of recursive algorithms often start with the recursive algorithm, but then switch to a different algorithm when the input becomes small. An important example is [[merge sort]], which is often implemented by switching to the non-recursive [[insertion sort]] when the data is sufficiently small, as in the [[tiled merge sort]]. Hybrid recursive algorithms can often be further refined, as in [[Timsort]], derived from a hybrid merge sort/insertion sort.
由于重复函数调用和返回的开销，递归算法对于小数据往往效率不高。出于这个原因，递归算法的高效实现往往从递归算法开始，但当输入变小时，再切换到不同的算法。一个重要的例子是合并排序，当数据足够小的时候，常常通过切换到非递归插入排序来实现，如平铺合并排序。混合递归算法往往可以进一步完善，如Timsort中，由混合合并排序/插入排序派生出来。
==Recursion versus iteration==
递归和迭代
Recursion and [[iteration]] are equally expressive: recursion can be replaced by iteration with an explicit [[call stack]], while iteration can be replaced with [[tail call|tail recursion]]. Which approach is preferable depends on the problem under consideration and the language used. In [[imperative programming]], iteration is preferred, particularly for simple recursion, as it avoids the overhead of function calls and call stack management, but recursion is generally used for multiple recursion. By contrast, in [[functional programming|functional languages]] recursion is preferred, with tail recursion optimization leading to little overhead. Implementing an algorithm using iteration may not be easily achievable.
递归和迭代
递归和迭代的表达方式是一样的:递归可以用显式调用堆栈的迭代代替，而迭代可以用尾递归代替。哪种方法更可取取决于所考虑的问题和所使用的语言。在命令式编程中，迭代是首选，特别是对于简单递归，因为它避免了函数调用的开销和调用堆栈管理，但递归通常用于多次递归。相比之下，在函数式语言中，递归是首选的，因为尾部递归优化只带来很少的开销。使用迭代实现算法可能不容易实现。
Compare the templates to compute x<sub>n</sub> defined by x<sub>n</sub> = f(n, x<sub>n-1</sub>) from x<sub>base</sub>:
比较x<sub>base</sub>中x<sub>n</sub> = f(n, x<sub>n-1</sub>)定义的计算x<sub>n</sub>的模板:
{|
|-
|
function recursive(n)
===Recursive procedures===
if n == base
return x<sub>base</sub>
else
return f(n, recursive(n-1))
||
function iterative(n)
x = x<sub>base</sub>
for i = base+1 to n
x = f(i, x)
return x
|}
For imperative language the overhead is to define the function, for functional language the overhead is to define the accumulator variable x.
对于命令式语言，开销是定义函数，对于函数式语言，开销是定义累加器变量x。
For example, a [[factorial]] function may be implemented iteratively in [[C (programming language)|C]] by assigning to an loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:
例如，在C语言中，一个阶乘函数可以通过分配给循环索引变量和累加器变量来反复实现，而不是通过递归传递参数和返回值。
<syntaxhighlight lang="C">
unsigned int factorial(unsigned int n) {
unsigned int product = 1; // empty product is 1
while (n) {
product *= n;
--n;
}
return product;
}
</syntaxhighlight>
===Expressive power===
表现力
Most [[programming language]]s in use today allow the direct specification of recursive functions and procedures. When such a function is called, the program's [[runtime environment]] keeps track of the various [[Instance (computer science)|instance]]s of the function (often using a [[call stack]], although other methods may be used). Every recursive function can be transformed into an iterative function by replacing recursive calls with [[Control flow|iterative control constructs]] and simulating the call stack with a [[stack (data structure)|stack explicitly managed]] by the program.<ref>{{citation|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|first=Magnus Lie|last=Hetland|publisher=Apress|date=2010|isbn=9781430232384|page=79|url=https://books.google.com/books?id=4cytGpIPYsAC&pg=PA79}}.</ref><ref>{{citation|title=Data Structures and Algorithms in C++|first=Adam|last=Drozdek|edition=4th|publisher=Cengage Learning|date=2012|isbn=9781285415017|page=197|url=https://books.google.com/books?id=PRgLAAAAQBAJ&pg=PA197}}.</ref>
今天使用的大多数编程语言都允许直接指定递归函数和程序。当这样的函数被调用时，程序的运行时环境会跟踪该函数的各种实例（通常使用调用堆栈，尽管可能使用其他方法）。每一个递归函数都可以通过用迭代控制构造代替递归调用，并用程序显式管理的堆栈模拟调用堆栈来转化为迭代函数。
|}
Conversely, all iterative functions and procedures that can be evaluated by a computer (see [[Turing completeness]]) can be expressed in terms of recursive functions; iterative control constructs such as [[while loop]]s and [[for loop]]s are routinely rewritten in recursive form in [[functional language]]s.<ref>{{cite web|url=http://www.ccs.neu.edu/home/shivers/papers/loop.pdf |title=The Anatomy of a Loop - A story of scope and control |publisher=Georgia Institute of Technology |first=Olin |last=Shivers |accessdate=2012-09-03}}</ref><ref>{{cite web|author=Lambda the Ultimate |url=http://lambda-the-ultimate.org/node/1014 |title=The Anatomy of a Loop |publisher=Lambda the Ultimate |accessdate=2012-09-03}}</ref> However, in practice this rewriting depends on [[tail call elimination]], which is not a feature of all languages. [[C (programming language)|C]], [[Java (programming language)|Java]], and [[Python (programming language)|Python]] are notable mainstream languages in which all function calls, including [[tail call]]s, may cause stack allocation that would not occur with the use of looping constructs; in these languages, a working iterative program rewritten in recursive form may [[stack overflow|overflow the call stack]], although tail call elimination may be a feature that is not covered by a language's specification, and different implementations of the same language may differ in tail call elimination capabilities.
相反，所有可以被计算机评估的迭代函数和程序(见图灵完备性)都可以用递归函数来表达;在函数式语言中，诸如while循环和for循环等迭代控制构造经常以递归形式重写.然而，在实践中，这种重写依赖于尾部调用的消除，而这并不是所有语言的特征。C语言、Java和Python是值得注意的主流语言，在这些语言中，所有的函数调用（包括尾部调用）都可能会引起堆栈分配，而使用循环构造则不会出现这种情况；在这些语言中，以递归形式重写的工作迭代程序可能会溢出调用堆栈，不过尾部调用消除可能是语言规范中没有涉及的功能，同一语言的不同实现在尾部调用消除能力上可能会有所不同。
===Performance issues===
性能问题
In languages (such as [[C (programming language)|C]] and [[Java (programming language)|Java]]) that favor iterative looping constructs, there is usually significant time and space cost associated with recursive programs, due to the overhead required to manage the stack and the relative slowness of function calls; in [[functional languages]], a function call (particularly a [[tail call]]) is typically a very fast operation, and the difference is usually less noticeable.
在偏重于迭代循环结构的语言（如C语言和Java）中，由于管理堆栈所需的开销和函数调用的相对缓慢，递归程序通常会有显著的时间和空间成本；在函数式语言中，函数调用（尤其是尾部调用）通常是一个非常快的操作，这种差异通常不太明显。
As a concrete example, the difference in performance between recursive and iterative implementations of the "factorial" example above depends highly on the [[compiler]] used. In languages where looping constructs are preferred, the iterative version may be as much as several [[order of magnitude|orders of magnitude]] faster than the recursive one. In functional languages, the overall time difference of the two implementations may be negligible; in fact, the cost of multiplying the larger numbers first rather than the smaller numbers (which the iterative version given here happens to do) may overwhelm any time saved by choosing iteration.
作为一个具体的例子，上述 "函数 "例子的递归和迭代实现之间的性能差异很大程度上取决于所使用的编译器。在偏好循环结构的语言中，迭代版本可能比递归版本快几个数量级。在函数式语言中，两种实现的总体时间差异可能可以忽略不计；事实上，先乘大数而不是先乘小数的成本（这里给出的迭代版本恰好做到了这一点）可能会超过选择迭代所节省的任何时间。
===Stack space===
堆栈空间
In some programming languages, the maximum size of the [[call stack]] is much less than the space available in the [[Heap (programming)|heap]], and recursive algorithms tend to require more stack space than iterative algorithms. Consequently, these languages sometimes place a limit on the depth of recursion to avoid [[stack buffer overflow|stack overflow]]s; [[python (programming language)|Python]] is one such language.<ref>{{cite web|url=https://docs.python.org/library/sys.html |title=27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation |publisher=Docs.python.org |accessdate=2012-09-03}}</ref> Note the caveat below regarding the special case of [[tail recursion]].
在一些编程语言中，调用栈的最大大小远小于堆中的可用空间，递归算法往往比迭代算法需要更多的栈空间。因此，这些语言有时会对递归的深度进行限制，以避免堆栈溢出；Python就是这样一种语言。注意下面关于尾部递归的特殊情况的注意事项。
{| class="wikitable"
===Vulnerability===
漏洞
Because recursive algorithms can be subject to stack overflows, they may be vulnerable to [[pathological (mathematics)|pathological]] or [[malware|malicious]] input.<ref>{{cite magazine| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Empirical Way to Tame an Algorithm| magazine=[[Dr. Dobb's Journal]]| date=2014| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-empirical-way-to-t/240169123}}</ref> Some malware specifically targets a program's call stack and takes advantage of the stack's inherently recursive nature.<ref>{{cite magazine| last=Mueller| first=Oliver| title=Anatomy of a Stack Smashing Attack and How GCC Prevents It| magazine=[[Dr. Dobb's Journal]]| date=2012| url=http://www.drdobbs.com/security/anatomy-of-a-stack-smashing-attack-and-h/240001832}}</ref> Even in the absence of malware, a stack overflow caused by unbounded recursion can be fatal to the program, and [[exception handling]] [[logic]] may not prevent the corresponding [[process (computing)|process]] from being [[process state#Terminated|terminated]].<ref>{{cite web| work=.NET Framework Class Library| title=StackOverflowException Class| publisher=[[Microsoft Developer Network]]| date=2018| url=https://msdn.microsoft.com/en-us/library/system.stackoverflowexception(v=vs.110).aspx}}</ref>
由于递归算法可能会发生堆栈溢出，因此它们可能容易受到病态或恶意输入的影响.一些恶意软件专门针对程序的调用堆栈，并利用堆栈固有的递归特性。即使在没有恶意软件的情况下，由无约束递归引起的堆栈溢出也会对程序造成致命的影响，而异常处理逻辑可能无法阻止相应进程被终止。
===Multiply recursive problems===
多次递归问题
Multiply recursive problems are inherently recursive, because of prior state they need to track. One example is [[tree traversal]] as in [[depth-first search]]; though both recursive and iterative methods are used,<ref>{{cite web| title=Depth First Search (DFS): Iterative and Recursive Implementation| publisher=Techie Delight| date=2018| url=http://www.techiedelight.com/depth-first-search/}}</ref> they contrast with list traversal and linear search in a list, which is a singly recursive and thus naturally iterative method. Other examples include [[divide-and-conquer algorithm]]s such as [[Quicksort]], and functions such as the [[Ackermann function]]. All of these algorithms can be implemented iteratively with the help of an explicit [[stack (data structure)|stack]], but the programmer effort involved in managing the stack, and the complexity of the resulting program, arguably outweigh any advantages of the iterative solution.
多次递归问题本质上是递归的，因为它们需要跟踪之前的状态。一个例子是深度优先搜索中的树形遍历;虽然同时使用了递归和迭代方法，但它们与单次递归的列表遍历和列表中的线性搜索相比，后者是一种自然的迭代方法。其他例子包括分治算法(如快速排序)和函数(如Ackermann函数)。所有这些算法都可以在显式栈的帮助下迭代地实现，但是程序员在管理栈方面所付出的努力，以及结果程序的复杂性，无疑超过了迭代解决方案的任何优势。
|-
===Refactoring recursion===
重构递归
Recursive algorithms can be replaced with non-recursive counterparts.<ref>{{cite web| last=Mitrovic| first=Ivan| title=Replace Recursion with Iteration| publisher=[[ThoughtWorks]]| url=https://www.refactoring.com/catalog/replaceRecursionWithIteration.html}}</ref> One method for replacing recursive algorithms is to simulate them using [[memory management|heap memory]] in place of [[stack-based memory allocation|stack memory]].<ref>{{cite web| last=La| first=Woong Gyu| title=How to replace recursive functions using stack and while-loop to avoid the stack-overflow| publisher=CodeProject| date=2015| url=https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and}}</ref> An alternative is to develop a replacement algorithm entirely based on non-recursive methods, which can be challenging.<ref>{{cite web| last=Moertel| first=Tom| title=Tricks of the trade: Recursion to Iteration, Part 2: Eliminating Recursion with the Time-Traveling Secret Feature Trick| date=2013| url=http://blog.moertel.com/posts/2013-05-14-recursive-to-iterative-2.html}}</ref> For example, recursive algorithms for [[matching wildcards]], such as [[Rich Salz]]' [[wildmat]] algorithm,<ref>{{cite web| last=Salz| first=Rich| title=wildmat.c| publisher=[[GitHub]]| date=1991| url=https://github.com/trevor/transmission/blob/master/libtransmission/wildmat.c}}</ref> were once typical. Non-recursive algorithms for the same purpose, such as the [[Krauss matching wildcards algorithm]], have been developed to avoid the drawbacks of recursion<ref>{{cite magazine| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Algorithm| magazine=[[Dr. Dobb's Journal]]| date=2008| url=http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888}}</ref> and have improved only gradually based on techniques such as collecting [[software testing|tests]] and [[profiling (computer programming)|profiling]] performance.<ref>{{cite web| last=Krauss| first=Kirk J.| title=Matching Wildcards: An Improved Algorithm for Big Data| publisher=Develop for Performance| date=2018| url=http://www.developforperformance.com/MatchingWildcards_AnImprovedAlgorithmForBigData.html}}</ref>
递归算法可以用非递归的对应算法来替换。替换递归算法的一种方法是用堆内存代替栈内存来模拟它们。另一种方法是完全基于非递归方法来开发替换算法，这可能是一个挑战。例如，用于匹配通配符的递归算法，如Rich Salz的wildmat算法，曾经是典型的算法。为了避免递归的缺点，人们开发了用于相同目的的非递归算法，如Krauss匹配通配符算法，并在收集测试和性能分析等技术的基础上逐步改进。
==Tail-recursive functions==
尾部递归函数
Tail-recursive functions are functions in which all recursive calls are [[tail call]]s and hence do not build up any deferred operations. For example, the gcd function (shown again below) is tail-recursive. In contrast, the factorial function (also below) is '''not''' tail-recursive; because its recursive call is not in tail position, it builds up deferred multiplication operations that must be performed after the final recursive call completes. With a [[compiler]] or [[interpreter (computing)|interpreter]] that treats tail-recursive calls as [[goto|jumps]] rather than function calls, a tail-recursive function such as gcd will execute using constant space. Thus the program is essentially iterative, equivalent to using imperative language control structures like the "for" and "while" loops.
尾部递归函数是指所有递归调用都是尾部调用，因此不建立任何递延操作的函数。例如，gcd函数（如下图所示）是尾递归函数。相反，因子函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它建立了递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。
{| class="wikitable"
|-
|-
! [[Tail recursion]]:
! Augmenting recursion:
|-
|-
|<syntaxhighlight lang="c">
//INPUT: Integers x, y such that x >= y and y >= 0
int gcd(int x, int y)
{
if (y == 0)
return x;
else
return gcd(y, x % y);
}
</syntaxhighlight>
|<syntaxhighlight lang="c">
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
if (n == 0)
return 1;
else
return n * fact(n - 1);
}
</syntaxhighlight>
|}
The significance of tail recursion is that when making a tail-recursive call (or any tail call), the caller's return position need not be saved on the [[call stack]]; when the recursive call returns, it will branch directly on the previously saved return position. Therefore, in languages that recognize this property of tail calls, tail recursion saves both space and time.
尾部递归的意义在于，当进行尾部递归调用（或任何尾部调用）时，调用者的返回位置不需要保存在调用栈上，当递归调用返回时，它将直接在先前保存的返回位置上进行分支。因此，在承认尾部调用这一特性的语言中，尾部递归既节省了空间又节省了时间。
==Order of execution==
执行顺序
In the simple case of a function calling itself only once, instructions placed before the recursive call are executed once per recursion before any of the instructions placed after the recursive call. The latter are executed repeatedly after the maximum recursion has been reached. Consider this example:
在一个函数只调用自己一次的简单情况下，在递归调用之前放置的指令在递归调用之后放置的任何指令之前，每次递归都会被执行一次。后者在达到最大递归后会被重复执行。考虑这个例子：
===Function 1===
<syntaxhighlight lang="c">
void recursiveFunction(int num) {
printf("%d\n", num);
if (num < 4)
recursiveFunction(num + 1);
}
</syntaxhighlight>
[[Image:Recursive1.svg|350px]]
|-
350px
===Function 2 with swapped lines===
<syntaxhighlight lang="c">
void recursiveFunction(int num) {
if (num < 4)
recursiveFunction(num + 1);
printf("%d\n", num);
}
}
</syntaxhighlight>
[[Image:Recursive2.svg|350px]]
==Time-efficiency of recursive algorithms==
递归算法的时间效率
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.
递归算法的时间效率可以用大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。
===Shortcut rule (master theorem)===
捷径规则（主定理）
{{Main|Master theorem (analysis of algorithms)}}
If the time-complexity of the function is in the form
如果函数的时间复杂度为以下形式：
<Math>T(n) = a \cdot T(n / b) + f(n)</Math>
Then the Big O of the time-complexity is thus:
那么时间复杂度的大O为：
* If <Math>f(n) = O(n ^ { \log_b a - \epsilon})</Math> for some constant <Math>\epsilon > 0</Math>, then <Math>T(n) = \Theta(n ^ {\log_b a})</Math>
如果<Math>f(n) = O(n ^ { \log_b a - \epsilon})</Math>，对于一些常数<Math>\epsilon > 0</Math>，那么 <Math>T(n) = \Theta(n ^ {\log_b a})</Math>
* If <Math>f(n) = \Theta(n ^ { \log_b a })</Math>, then <Math>T(n) = \Theta(n ^ { \log_b a} \log n)</Math>
如果 <Math>f(n) = \Theta(n ^ { \log_b a })</Math>, 那么 <Math>T(n) = \Theta(n ^ { \log_b a} \log n)</Math>
* If <Math>f(n) = \Omega(n ^ { \log_b a + \epsilon})</Math> for some constant <Math>\epsilon > 0</Math>, and if <Math>a \cdot f(n / b) \leq c \cdot f(n)</Math> for some constant {{mvar|c}} < 1 and all sufficiently large {{mvar|n}}, then <Math>T(n) = \Theta(f(n))</Math>
如果 <Math>f(n) = \Omega(n ^ { \log_b a + \epsilon})</Math> 对于一些常数 <Math>\epsilon > 0</Math>, 且如果<Math>a \cdot f(n / b) \leq c \cdot f(n)</Math> 对于一些常数{{mvar|c}} < 1 和 所有足够大的 {{mvar|n}}, 则 <Math>T(n) = \Theta(f(n))</Math>
where {{mvar|a}} represents the number of recursive calls at each level of recursion, {{mvar|b}} represents by what factor smaller the input is for the next level of recursion (i.e. the number of pieces you divide the problem into), and {{math|''f'' (''n'')}} represents the work the function does independent of any recursion (e.g. partitioning, recombining) at each level of recursion.
其中，a代表每一级递归的递归调用次数，b代表下一级递归的输入小多少系数（即把问题分成多少块），f（n）代表函数在每一级递归中独立于任何递归（如分割、重新组合）的工作。
==See also==
另请参阅
* [[Functional programming]] 功能性方案编制
* [[Hierarchical and recursive queries in SQL]] SQL中的分层和递归查询
* [[Kleene–Rosser paradox]] 洁能-罗瑟Kleene–Rosser悖论
* [[Open recursion]] 开放式递归
* [[Recursion]]递归
* [[Sierpiński curve]] 西尔平斯基曲线
* [[McCarthy 91 function]] McCarthy 91函数
* [[μ-recursive function]]s μ-递归函数
* [[Primitive recursive function]]s原始递归函数
* [[Tak (function)]]Tak（函数）
[[Category:待整理页面]]
[[Category:待整理页面]]