递归

此词条由Solitude初步翻译。

25px  此article介紹的是recursive approaches to solving problems。For proofs by recursion, see Mathematical induction. For recursion in computer science acronyms, see Recursive acronym § Computer-related examples.

文件:RecursiveTree.JPG

Tree created using the 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 language ’’’创建的树，主要依靠递归。每一个分支都可以看作是一棵树的缩小版。

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

In computer science, recursion is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. Recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

在’’’ 计算机科学computer science’’’中，递归是一种解决问题的方法，其解决方案取决于同一问题的较小实例的解决方案。这种问题一般可以通过’’’ 迭代iteration’’’来解决，但这需要在编程时识别和索引较小的实例。递归通过使用从自己的代码中调用自己的函数来解决这种’’’ 递归问题recursive problem’’’。这种方法可以应用于许多类型的问题，递归是计算机科学的核心思想之一。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

{{quote|text= 递归的能力显然在于通过一个有限的语句定义无限对象集的可能性。同样，一个有限递归程序可以描述无限多的计算，即使这个程序不包含显式的重复。

- 尼克劳斯-沃思，《算法+数据结构=程序》，1976年。

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 while and for.

Most computer programming languages support recursion by allowing a function to call itself from within its own code. Some functional programming languages (for instance, Clojure) do not define any looping constructs but rely solely on recursion to repeatedly call code. It is proved in computability theory that these recursive-only languages are Turing complete; this means that they are as powerful (they can be used to solve the same problems) as imperative languages based on control structures such as while and for .

大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些’’’ 函数式编程语言functional programming language’’’(例如Clojure)不定义任何循环结构，而只依赖递归来重复调用代码。在’’’可计算性理论 computability theory’’’中证明了这些递归语言是’’’图灵完备Turing complete ’’’图灵完备的;这意味着它们与基于while 和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 efficient, and, for large problems, it is fundamental to use optimization techniques such as tail call optimization.模板:CN

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.

一种常用的’’’ 计算机编程computer programming’’’策略是将一个问题划分为与原问题相同类型的子问题，解决这些子问题，并将结果合并。这通常被称为分而治之法；当与存储解子问题结果的查找表结合起来时（以避免重复解子问题而产生额外的计算时间），可称为’’’ 动态编程dynamic programming ’’’或’’’ 备忘录化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 0! = 1 and, for all n > 0, 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 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.

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

For some functions (such as one that computes the series for 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? where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".

For some functions (such as one that computes the series for 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! + ...）输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个’’’参数 parameter’’’（比如在我们的系列示例中要添加的术语数量）来提供一个 "停止标准"，以建立基本情况。这样的例子更自然地用’’’ 共递归corecursion’’’来处理，其中输出中的连续项是部分和；这可以通过使用索引参数表示“计算第n项(第n部分和)”来转换为递归。

Recursive data types

递归数据类型 Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is a technique for representing data whose exact size is unknown to the programmer: the programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions.

Many computer programs must process or generate an arbitrarily large quantity of data. Recursion is a technique for representing data whose exact size is unknown to the programmer: the programmer can specify this data with a self-referential definition. There are two types of self-referential definitions: inductive and coinductive definitions.

许多’’’计算机程序computer program ’’’必须处理或生成任意大量的数据。递归是一种表示程序员不知道确切大小的数据的技术:程序员可以用自引用的定义指定这些数据。’’’ 自引用self-referential’’’定义有两种类型: 归纳定义和协归纳定义。

Inductively defined data

归纳定义的数据

Main article: Recursive data type

An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax):

An inductively defined recursive data definition is one that specifies how to construct instances of the data. For example, linked lists can be defined inductively (here, using Haskell syntax):

归纳定义的递归数据定义是指定如何构造数据实例的定义。例如，链接列表可以被归纳定义（在这里，使用Haskell语法）：

data ListOfStrings = EmptyList | Cons String ListOfStrings

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):

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

A natural number is either 1 or n+1, where n is a natural number.

一个自然数是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:

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形式Backus–Naur form’’’ 这样的语法来表达语法，这里有一种语法，适用于一个简单的有乘法和加法的算术表达式的语言：

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

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 (5 * ((3 * 6) + 8)), 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 (5 * ((3 * 6) + 8)), with more than one product or sum operation in a single expression.

这意味着一个表达式要么是一个数字，要么是两个表达式的乘积，要么是两个表达式的和。通过在第二行和第三行中递归引用表达式，该语法允许任意复杂的算术表达式，如 < code > (5 * ((3 * 6) + 8)) ，在一个表达式中有多个乘积或和运算。

Coinductively defined data and corecursion

协同定义的数据和共递归

Main articles: Coinduction and 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 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 head and tail—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 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 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, while recursion that contains multiple self-references is known as 模板:Visible anchor. 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.

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

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. 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 article: Mutual recursion

Most basic examples of recursion, and most of the examples presented here, demonstrate 模板:Anchordirect 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.

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

Anonymous recursion

匿名递归

Main article: Anonymous recursion

Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.

Recursion is usually done by explicitly calling a function by name. However, recursion can also be done via implicitly calling a function based on the current context, which is particularly useful for anonymous functions, and is known as anonymous recursion.

递归通常是通过显式调用一个函数的名字来实现的。但是，递归也可以通过根据当前上下文隐式调用函数来完成，这对于匿名函数特别有用，被称为’’’ 匿名递归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:

一些作者将递归分为 "结构性 "或 "生成性"。这种区别与递归程序从哪里获得它所处理的数据以及它如何处理这些数据有关。

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

{{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 is the alternative:

生成递归是替代方法：

/* Styling for Template:Quote */ .templatequote { overflow: hidden; margin: 1em 0; padding: 0 40px; } .templatequote .templatequotecite {

   line-height: 1.5em;
   /* @noflip */
   text-align: left;
   /* @noflip */
   padding-left: 1.6em;
   margin-top: 0;

}

许多著名的递归算法都是从给定的数据中生成一个全新的数据，并对其进行递归。HtDP（How to Design Programs）把这种称为生成式递归。生成递归的例子包括：gcd、quicksort、二进制搜索、mergesort、牛顿法、分形和自适应集成。

- Matthias Felleisen，《高级函数式编程》，2002年。

This distinction is important in proving termination of a function.

This distinction is important in proving termination of a function.

这种区别在证明函数的终止性时很重要。

• All structurally recursive functions on finite (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 variants, 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.

与此相反，生成递归是指没有这样明显的循环变体，终止取决于一个函数，如 "近似误差"，而这个函数不一定会降为零，因此，如果不作进一步的分析，就不能保证终止。

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 classic example of a recursive procedure is the function used to calculate the factorial of a natural number:

递归过程的一个经典例子是用于计算自然数阶乘的函数:

[math]\displaystyle{ \operatorname{fact}(n) = \begin{cases} 1 & \mbox{if } n = 0 \\ n \cdot \operatorname{fact}(n-1) & \mbox{if } n \gt 0 \\ \end{cases} }[/math]

Pseudocode (recursive):
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. if n is 0, return 1 2. otherwise, return [ n × factorial(n-1) ] end factorial

函数 阶乘是:

输入: 整数 n 即 n >= 0

输出: [n × (n-1) × (n-2) × … × 1]


    1. 如果n 是0, 返回 1
    2. 否则, 返回 [ n × 阶乘(n-1) ]


结束 阶乘

|}

The function can also be written as a recurrence relation:

该函数也可以写成递归关系：

[math]\displaystyle{ b_n = nb_{n-1} }[/math]

[math]\displaystyle{ 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:

这种对递归关系的评价展示了在评价上述伪代码时将进行的计算。

Computing the recurrence relation for n = 4: 计算n = 4的递归关系：
b4 = 4 * b3 = 4 * (3 * b2) = 4 * (3 * (2 * b1)) = 4 * (3 * (2 * (1 * b0))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

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:

这个阶乘函数也可以在不使用递归的情况下，通过使用典型的循环结构来描述，这些循环结构在命令式编程语言中可以找到：

Pseudocode (iterative):
function factorial is: input: integer n such that n >= 0 output: [n × (n-1) × (n-2) × … × 1] 1. create new variable called running_total with a value of 1 2. begin loop 1. if n is 0, exit loop 2. set running_total to (running_total × n) 3. decrement n 4. repeat loop 3. return running_total end factorial

函数 阶乘是:

输入: 整数 n ，使得 n >= 0

输出: [n × (n-1) × (n-2) × … × 1]


    1. 创建 一个名为 running_total 的新变量，其值为 1


    2. 开始 循环
          1. 如果 n 为 0, 则退出 循环
          2. 将 running_total 设置为 (running_total × n)
          3. 递减 n
          4. 重复 循环


    3. 返回 running_total


结束 阶乘

The imperative code above is equivalent to this mathematical definition using an accumulator variable t:

The imperative code above is equivalent to this mathematical definition using an accumulator variable t:

上面的命令代码相当于这个使用累加器变量math|t的数学定义:

[math]\displaystyle{ \begin{array}{rcl} \operatorname{fact}(n) & = & \operatorname{fact_{acc}}(n, 1) \\ \operatorname{fact_{acc}}(n, t) & = & \begin{cases} t & \mbox{if } n = 0 \\ \operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n \gt 0 \\ \end{cases} \end{array} }[/math]

The definition above translates straightforwardly to functional programming languages such as 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]\displaystyle{ \gcd(x,y) = \begin{cases} x & \mbox{if } y = 0 \\ \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y \gt 0 \\ \end{cases} }[/math]

Pseudocode (recursive):
function gcd is: input: integer x, integer y such that x > 0 and y >= 0 1. if y is 0, return x 2. otherwise, return [ gcd( y, (remainder of x/y) ) ] end gcd

函数 gcd 是:
输入: 整数 x, 整数 y 使得 x > 0 且 y >= 0


    1. 如果 y 为 0, 则返回 x
    2. 否则, 返回 [ gcd( y, (x/y的余数) ) ]


结束 gcd

Recurrence relation for greatest common divisor, where [math]\displaystyle{ x \% y }[/math] expresses the remainder of [math]\displaystyle{ x / y }[/math]: 最大公约数的递归关系，其中[math]\displaystyle{ x \% y }[/math]表示余下的 [math]\displaystyle{ x / y }[/math]：

[math]\displaystyle{ \gcd(x,y) = \gcd(y, x \% y) }[/math] if [math]\displaystyle{ y \neq 0 }[/math]

[math]\displaystyle{ \gcd(x,0) = x }[/math]

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的递归关系：
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中，并使用循环结构，该程序避免了递归调用和增加调用栈。

Pseudocode (iterative):
function gcd is: input: integer x, integer y such that x >= y and y >= 0 1. create new variable called remainder 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 3. return x end gcd

函数 gcd 是:

输入: 整数 x, 整数 y 使得 x >= y 且 y >= 0


    1. 创建 一个名为 余数的新变量


    2. 开始 循环
          1. 如果 y 为0, 则退出 循环
          2. 将 剩下部分设置为x / y 的余数
          3. 将x设置 为y
          4. 将y设置 为 余数
          5. 重复 循环


    3. 返回 x


结束 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

河内塔

Towers of Hanoi

河内塔

Main article: Towers of Hanoi

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?

’’’ 河内塔Towers of Hanoi ’’’是一个数学难题，它的解法说明了递归的问题。有三个钉子可以固定不同直径的磁盘堆叠。一个较大的圆盘永远不能堆叠在一个较小的圆盘之上。从一个钉子上的n个磁盘开始，它们必须一次一个地移动到另一个钉子上。移动堆栈的最小步数是多少？

Function definition: 函数定义：

[math]\displaystyle{ \operatorname{hanoi}(n) = \begin{cases} 1 & \mbox{if } n = 1 \\ 2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n \gt 1\\ \end{cases} }[/math]

Recurrence relation for hanoi: 河内的递归关系：

[math]\displaystyle{ h_n = 2h_{n-1}+1 }[/math]

[math]\displaystyle{ h_1 = 1 }[/math]

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

Example implementations: 示例实现：

Pseudocode (recursive):
function hanoi is: input: integer n, such that n >= 1 1. if n is 1 then return 1 2. return [2 * [call hanoi(n-1)] + 1] end hanoi

函数 hanoi 是:

输入: 整数 n, 使得n >= 1


    1. 如果 n 为 1 则返回 1


    2. 返回 [2 * [call hanoi(n-1)] + 1]


结束 hanoi

Although not all recursive functions have an explicit solution, the Tower of Hanoi sequence can be reduced to an explicit formula.

虽然不是所有的递归函数都有明确的解，但河内塔序列可以简化为一个明确的公式。

An explicit formula for Towers of Hanoi: 河内塔楼的明确公式：
h1 = 1 = 21 - 1 h2 = 3 = 22 - 1 h3 = 7 = 23 - 1 h4 = 15 = 24 - 1 h5 = 31 = 25 - 1 h6 = 63 = 26 - 1 h7 = 127 = 27 - 1 In general: hn = 2n - 1, for all n >= 1

通常:

hn = 2n - 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.

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

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语言中二分搜索的实现实例:

 /*
  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);
 }

Recursive data structures (structural recursion)

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

Main article: Recursive data type

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.

递归在计算机科学中的一个重要应用是定义动态数据结构，如列表和树。递归数据结构可以根据运行时的要求动态地增长到理论上的无限大小；相反，静态数组的大小必须在编译时设定。

"Recursive algorithms are particularly appropriate when the underlying problem or the data to be treated are defined in recursive terms."

"当底层问题或要处理的数据以递归方式定义时，递归算法特别合适。"

The examples in this section illustrate what is known as "structural recursion". This term refers to the fact that the recursive procedures are acting on data that is defined recursively.

本节的例子说明了所谓的 "结构递归"。这个术语指的是递归程序是作用于递归定义的数据。

As long as a programmer derives the template from a data definition, functions employ structural recursion. That is, the recursions in a function's body consume some immediate piece of a given compound value.

只要程序员从数据定义中导出模板，函数就会采用结构递归。也就是说，函数主体中的递归会消耗某个给定复值的直接部分。

Linked lists

链表

Main article: 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语言定义。特别注意节点是如何从自身出发来定义的。结构节点的 "下一个 "元素是指向另一个结构节点的指针，实际上是创建了一个列表类型。

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

结构 节点
{
  int 数据;           // 一些整数数据
  结构 节点 *next;  // 指向另一个结构节点的指针
};

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过程中保持不变。

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
    }
}

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
    }
}

Binary trees

二叉树

Main article: 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(指向右边的子树)。

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

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:

对二叉树的操作可以使用递归来实现。注意，由于有两个自引用指针（左和右），对二叉树的操作可能需要两次递归调用：

// 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);
}

At most two recursive calls will be made for any given call to tree_contains as defined above.

对于上面定义的tree_contains的任何给定调用，最多会有两次递归调用。

// 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
        }
}

The above example illustrates an 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.

由于文件系统中的文件数量可能会发生变化，所以递归是遍历并枚举其内容的唯一实用方法。遍历文件系统与树形遍历非常相似，因此树形遍历背后的概念也适用于遍历文件系统。更具体地说，下面的代码将是一个文件系统的预排序遍历的示例。

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]);
			}
		}
	}

}

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.

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

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 function’’’是指直接调用但本身不递归的函数，而是调用一个单独的辅助函数，它实际上进行递归。

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 functions, 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 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 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 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.

从概念上讲，短路可以认为是具有相同的基本情况和递归步骤，只在递归前检查基例，也可以认为是具有不同的基本情况（比标准基本情况去掉一步）和更复杂的递归步骤，即 "先检查有效再递归"，如在树中考虑叶子节点而不是空节点作为基本情况。由于短路的流程比较复杂，相比标准递归中基本情况和递归步骤的清晰分离，短路往往被认为是风格不佳，尤其是在学术界。

Depth-first search

深度优先搜索 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.

在二叉树的’’’ 深度优先搜索depth-first search’’’（DFS）中给出了一个短路的基本例子；标准递归讨论见二叉树部分。

The standard recursive algorithm for a DFS is:

DFS的标准递归算法是：

• base case: If current node is Null, return false

基本情况： 如果当前节点为Null，返回false。

• 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^h+1−1 nodes and 2^h+1 Null pointers as children (2 for each of the 2^h 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:

在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);
}

The short-circuited algorithm may be implemented as:

短路算法可以实现为：

// 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));
}

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 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.

递归和迭代

递归和迭代的表达方式是一样的:递归可以用显式调用堆栈的迭代代替，而迭代可以用尾递归代替。哪种方法更可取取决于所考虑的问题和所使用的语言。在命令式编程中，迭代是首选，特别是对于简单递归，因为它避免了函数调用的开销和调用堆栈管理，但递归通常用于多次递归。相比之下，在函数式语言中，递归是首选的，因为尾部递归优化只带来很少的开销。使用迭代实现算法可能不容易实现。

Compare the templates to compute x_n defined by x_n = f(n, x_n-1) from x_base: 比较x_base中x_n = f(n, x_n-1)定义的计算x_n的模板:

function recursive(n) if n == base return xbase else return f(n, recursive(n-1))

function iterative(n) x = xbase 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 by assigning to an loop index variable and accumulator variable, rather than by passing arguments and returning values by recursion:

例如，在C语言中，一个阶乘函数可以通过分配给循环索引变量和累加器变量来反复实现，而不是通过递归传递参数和返回值。

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Expressive power

表现力 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.

今天使用的大多数编程语言都允许直接指定递归函数和程序。当这样的函数被调用时，程序的运行时环境会跟踪该函数的各种实例（通常使用调用堆栈，尽管可能使用其他方法）。每一个递归函数都可以通过用迭代控制构造代替递归调用，并用程序显式管理的堆栈模拟调用堆栈来转化为迭代函数。

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循环等迭代控制构造经常以递归形式重写.然而，在实践中，这种重写依赖于尾部调用的消除，而这并不是所有语言的特征。C语言、Java和Python是值得注意的主流语言，在这些语言中，所有的函数调用（包括尾部调用）都可能会引起堆栈分配，而使用循环构造则不会出现这种情况；在这些语言中，以递归形式重写的工作迭代程序可能会溢出调用堆栈，不过尾部调用消除可能是语言规范中没有涉及的功能，同一语言的不同实现在尾部调用消除能力上可能会有所不同。

Performance issues

性能问题 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）中，由于管理堆栈所需的开销和函数调用的相对缓慢，递归程序通常会有显著的时间和空间成本；在函数式语言中，函数调用（尤其是尾部调用）通常是一个非常快的操作，这种差异通常不太明显。

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.

作为一个具体的例子，上述 "函数 "例子的递归和迭代实现之间的性能差异很大程度上取决于所使用的编译器。在偏好循环结构的语言中，迭代版本可能比递归版本快几个数量级。在函数式语言中，两种实现的总体时间差异可能可以忽略不计；事实上，先乘大数而不是先乘小数的成本（这里给出的迭代版本恰好做到了这一点）可能会超过选择迭代所节省的任何时间。

Stack space

堆栈空间 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就是这样一种语言。注意下面关于尾部递归的特殊情况的注意事项。

Vulnerability

漏洞 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.

由于递归算法可能会发生堆栈溢出，因此它们可能容易受到病态或恶意输入的影响.一些恶意软件专门针对程序的调用堆栈，并利用堆栈固有的递归特性。即使在没有恶意软件的情况下，由无约束递归引起的堆栈溢出也会对程序造成致命的影响，而异常处理逻辑可能无法阻止相应进程被终止。

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, 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.

多次递归问题本质上是递归的，因为它们需要跟踪之前的状态。一个例子是深度优先搜索中的树形遍历;虽然同时使用了递归和迭代方法，但它们与单次递归的列表遍历和列表中的线性搜索相比，后者是一种自然的迭代方法。其他例子包括分治算法(如快速排序)和函数(如Ackermann函数)。所有这些算法都可以在显式栈的帮助下迭代地实现，但是程序员在管理栈方面所付出的努力，以及结果程序的复杂性，无疑超过了迭代解决方案的任何优势。

Refactoring recursion

重构递归 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匹配通配符算法，并在收集测试和性能分析等技术的基础上逐步改进。

Tail-recursive functions

尾部递归函数 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函数（如下图所示）是尾递归函数。相反，因子函数（也在下面）不是尾递归的；因为它的递归调用不在尾部位置，所以它建立了递延的乘法运算，这些运算必须在最后的递归调用完成后才能执行。如果编译器或解释器将尾部递归调用视为跳转而非函数调用，那么像gcd这样的尾部递归函数将使用常量空间执行。因此，程序本质上是迭代的，相当于使用 "for "和 "while "循环等命令式语言控制结构。

Tail recursion:	Augmenting recursion:
//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); }	//INPUT: n is an Integer such that n >= 0 int fact(int n) { if (n == 0) return 1; else return n * fact(n - 1); }

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

void recursiveFunction(int num) {
    printf("%d\n", num);
    if (num < 4)
        recursiveFunction(num + 1);
}

350px

Function 2 with swapped lines

void recursiveFunction(int num) {
    if (num < 4)
        recursiveFunction(num + 1);
    printf("%d\n", num);
}

350px

Time-efficiency of recursive algorithms

递归算法的时间效率 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. 递归算法的’’’ 时间效率time efficiency ’’’可以用大O符号的递归关系来表示。然后，它们（通常）可以被简化为一个大O项。

Shortcut rule (master theorem)

捷径规则（主定理）

Main article: Master theorem (analysis of algorithms)

If the time-complexity of the function is in the form

如果函数的时间复杂度为以下形式：

[math]\displaystyle{ T(n) = a \cdot T(n / b) + f(n) }[/math]

Then the Big O of the time-complexity is thus:

那么时间复杂度的大O为：

• If [math]\displaystyle{ f(n) = O(n ^ { \log_b a - \epsilon}) }[/math] for some constant [math]\displaystyle{ \epsilon \gt 0 }[/math], then [math]\displaystyle{ T(n) = \Theta(n ^ {\log_b a}) }[/math]

如果[math]\displaystyle{ f(n) = O(n ^ { \log_b a - \epsilon}) }[/math]，对于一些常数[math]\displaystyle{ \epsilon \gt 0 }[/math]，那么 [math]\displaystyle{ T(n) = \Theta(n ^ {\log_b a}) }[/math]

• If [math]\displaystyle{ f(n) = \Theta(n ^ { \log_b a }) }[/math], then [math]\displaystyle{ T(n) = \Theta(n ^ { \log_b a} \log n) }[/math]

如果 [math]\displaystyle{ f(n) = \Theta(n ^ { \log_b a }) }[/math], 那么 [math]\displaystyle{ T(n) = \Theta(n ^ { \log_b a} \log n) }[/math]

• If [math]\displaystyle{ f(n) = \Omega(n ^ { \log_b a + \epsilon}) }[/math] for some constant [math]\displaystyle{ \epsilon \gt 0 }[/math], and if [math]\displaystyle{ a \cdot f(n / b) \leq c \cdot f(n) }[/math] for some constant c < 1 and all sufficiently large n, then [math]\displaystyle{ T(n) = \Theta(f(n)) }[/math]

如果 [math]\displaystyle{ f(n) = \Omega(n ^ { \log_b a + \epsilon}) }[/math] 对于一些常数 [math]\displaystyle{ \epsilon \gt 0 }[/math], 且如果[math]\displaystyle{ a \cdot f(n / b) \leq c \cdot f(n) }[/math] 对于一些常数c < 1 和 所有足够大的 n, 则 [math]\displaystyle{ T(n) = \Theta(f(n)) }[/math]

where a represents the number of recursive calls at each level of recursion, 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 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 functions μ-递归函数
• Primitive recursive functions原始递归函数
• Tak (function)Tak（函数）