递归

此词条暂由彩云小译翻译，翻译字数共5094，未经人工整理和审校，带来阅读不便，请见谅。

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.

Logo programming language and relying heavily on recursion. Each branch can be seen as a smaller version of a tree.]]

标志编程语言和严重依赖递归。每个树枝都可以看作是一棵树的缩小版。]

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.

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.

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

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

}

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

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 efficient, and, for large problems, it is fundamental to use optimization techniques such as tail call optimization.模板:CN

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:

类似地，递归定义通常用于为编程语言中的表达式和语句的结构建模。语言设计者经常用诸如 Backus-Naur 形式这样的句法来表达语法，这里有一种语法，用于一种简单的带有乘法和加法的算术表达式语言:

Recursive functions and algorithms

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

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.

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)) ，在一个表达式中有多个乘积或和运算。

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

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.

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:

非正式给出的无限弦流的共归纳定义可能是这样的:

Inductively defined data

A stream of strings is an object s such that:

字符串流是这样的对象:

Main article: 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 lists can be defined inductively (here, using 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 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.

这非常类似于字符串列表的归纳定义; 区别在于这个定义指定了如何访问数据结构的内容ー即通过访问器函数 < code > head 和 < code > tail 以及这些内容可能是什么，而归纳定义则指定了如何创建结构以及可以从哪些内容创建结构。

data ListOfStrings = EmptyList | Cons String ListOfStrings

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

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

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

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 和空间，而且更基本上是递归的，没有明确的堆栈就不能被迭代替代。

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

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 (5 * ((3 * 6) + 8)), 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 是相互递归的。同样，一组三个或三个以上相互调用的函数也可以称为一组相互递归的函数。

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 definition of infinite 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:

有些作者将递归归类为“结构性”或“生成性”。这个区别与递归过程从哪里获得它所处理的数据以及它如何处理这些数据有关:

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

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

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

}

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

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 article: 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 functions, and is known as anonymous recursion.

[math]\displaystyle{ \operatorname{fact}(n) = { fact }(n) = \begin{cases} 开始{ cases } ===Structural versus generative recursion=== 1 & \mbox{if } n = 0 \\ 1 & mbox { if } n = 0 {{see also|Structural recursion}} n \cdot \operatorname{fact}(n-1) & \mbox{if } n \gt 0 \\ N cdot 操作符/名称{ fact }(n-1) & mbox { if } n \gt 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]

数学

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

}

|-

|-

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

function factorial is:

函数阶乘是: < br/>

input: integer n such that n >= 0

输入: 整数 n 使得 n > = 0 < br/>

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

}

|-

|-

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.

b4           = 4 * b3

B < sub > 4 = 4 * b < sub > 3 < 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 * b2)

= 4 * (3 * b < sub > 2 )

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

             = 4 * (3 * (2 * b1))

= 4 * (3 * (2 * b < sub > 1 ))

• 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 * b0)))

= 4 * (3 * (2 * (1 * b < sub > 0 ))

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

Recursive procedures

             = 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]\displaystyle{ \operatorname{fact}(n) = \begin{cases} {| class="wikitable" { | class = “ wikitable” 1 & \mbox{if } n = 0 \\ |- |- n \cdot \operatorname{fact}(n-1) & \mbox{if } n \gt 0 \\ ! Pseudocode (iterative): !伪代码(迭代) : \end{cases} |- |- }[/math]

|

|

function factorial is:

函数阶乘是: < br/>

input: integer n such that n >= 0
输入: 整数 n 使得 n > = 0 < br/> output: [n × (n-1) × (n-2) × … × 1] output: [n × (n-1) × (n-2) × … × 1] 1. create new variable called running_total with a value of 1 1. 创建名为 running _ total 的新变量，其值为1

Pseudocode (recursive): < br/>

< br/> function factorial is: 2. begin loop 2. begin loop input: integer n such that n >= 0 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) 3. decrement n 3. 减少 1. if n is 0, return 1 4. repeat loop 4. 重复循环 2. otherwise, return [ n × factorial(n-1) ] < br/> 3. return running_total 3. return running total end factorial < br/>

end factorial

终止阶乘

|}

|}

The function can also be written as a recurrence relation:

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

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

上面的命令代码使用累加器变量等价于这个数学定义:

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

This evaluation of the recurrence relation demonstrates the computation that would be performed in evaluating the pseudocode above:

[math]\displaystyle{ 《数学》 {| 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\lt sub\gt 4\lt /sub\gt = 4 * b\lt sub\gt 3\lt /sub\gt \lt br /\gt \operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n \gt 0 \\ 操作符名称{ fact _ { acc }(n-1，nt) & mbox { if } n \gt 0 = 4 * (3 * b\lt sub\gt 2\lt /sub\gt ) \end{cases} 结束{ cases } = 4 * (3 * (2 * b\lt sub\gt 1\lt /sub\gt )) \end{array} 结束{数组} = 4 * (3 * (2 * (1 * b\lt sub\gt 0\lt /sub\gt ))) }[/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]\displaystyle{ \gcd(x,y) = \lt math \gt 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 \gt 0 \\ Gcd (y，operatorname { remainder }(x，y)) & mbox { if } y \gt 0 |- \end{cases} 结束{ cases } | }[/math]

数学

function factorial is:

input: integer n such that n >= 0

{ | class = “ wikitable” output: [n × (n-1) × (n-2) × … × 1]

Pseudocode (recursive):

伪代码(递归) : 1. create new variable called running_total with a value of 1

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/> 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/> 3. return running_total end gcd 末端 gcd

|}

end factorial

|}

Recurrence relation for greatest common divisor, where [math]\displaystyle{ x \% y }[/math] expresses the remainder of [math]\displaystyle{ x / y }[/math]:

递回关系式为最大公约数，其中 x% y 表示了《 math > x/y </math > 的剩余部分:

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

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

Gcd (x，y) = gcd (y，x% y) </math > if < math > y neq 0 </math >

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

< math > gcd (x，0) = x </math >

[math]\displaystyle{ \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 \gt 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 languages such as 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]\displaystyle{ \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 \gt 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”

Pseudocode (iterative):	伪代码(迭代) :	Pseudocode (recursive):
		function gcd is: 函数 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/> 1. create new variable called remainder 1. 创建名为 remainder 的新变量 1. if y is 0, return x < br/> 2. otherwise, return [ gcd( y, (remainder of x/y) ) ] 2. begin loop 2. begin loop 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]\displaystyle{ x \% y }[/math] expresses the remainder of [math]\displaystyle{ x / y }[/math]:

          5. repeat loop

5. 重复循环

< br/>

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

    3. return x

3. return x

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

< br/>

end gcd

末端 gcd

|-

! 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]\displaystyle{ \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 \gt 1\\ 2 cdot operatorname { hanoi }(n-1) + 1 & mbox { if } n \gt 1 = gcd(111, 37) \end{cases} 结束{ cases } = gcd(37, 111% 37) }[/math]

数学

                = gcd(37, 0)

                = 37

Recurrence relation for hanoi:

河内递回关系式:

|}

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

2h { n-1} + 1 </math >

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

Computing the recurrence relation for n = 4:	计算 n = 4的递回关系式:	Pseudocode (iterative):
		hanoi(4) = 2*hanoi(3) + 1 河内(4) = 2 * 河内(3) + 1 function gcd is: = 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 = 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 = 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/>

          3. set x to y

          4. set y to remainder

Example implementations:

实现示例:

          5. repeat loop

{ | class = “ wikitable” 3. returnx

Pseudocode (recursive):	伪代码(递归) : end gcd

|

|

function hanoi is:

函数 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/>

Towers of Hanoi

    1. if n is 1 then return 1

1. 如果 n 是1，那么返回1

Towers of Hanoi

< br/>

Main article: Towers of Hanoi

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

2. return [2 * [致电河内(n-1)] + 1]

< br/>

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?

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”

[math]\displaystyle{ \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 \gt 1\\ | | \end{cases} h\lt sub\gt 1\lt /sub\gt = 1 = 2\lt sup\gt 1\lt /sup\gt - 1 H \lt sub \gt 1 \lt /sub \gt = 1 = 2 \lt sup \gt 1 \lt /sup \gt -1 }[/math]

h₂ = 3 = 2² - 1 H < sub > 2 = 3 = 2 < sup > 2 -1 h₃ = 7 = 2³ - 1 H < sub > 3 = 7 = 2 < sup > 3 -1 Recurrence relation for hanoi: h₄ = 15 = 2⁴ - 1 H < sub > 4 = 15 = 2 < sup > 4 -1

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

h₅ = 31 = 2⁵ - 1 H < sub > 5 = 31 = 2 < sup > 5 -1

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

h₆ = 63 = 2⁶ - 1 H < sub > 6 = 63 = 2 < sup > 6 -1 h₇ = 127 = 2⁷ - 1 H < sub > 7 = 127 = 2 < sup > 7 -1 In general: 一般而言:

Computing the recurrence relation for n = 4: hn = 2n - 1, for all n >= 1 H < sub > n = 2 < sup > n -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" > 

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

 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

< 我们的目标是什么 >

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

*/

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)

{

< 我们的目标是什么 >

// 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^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 的完美二叉树，有2个 < sup > h + 1 & minus; 1个节点和2个 < sup > h + 1 空指针作为子节点(2个 < sup > h 叶子) ，因此在最坏的情况下，短路将函数调用的数量减半。

*/

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

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

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



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

Main article: 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.

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

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) 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) return x 返回 x

Binary trees

Main article: 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 语言中迭代实现，方法是指派一个循环索引变量和一个累加器变量，而不是通过传递参数和递归返回值:

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;

}

}

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 >

// 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”示例的递归和迭代实现之间的性能差异在很大程度上取决于所使用的编译器。在循环结构更受欢迎的语言中，迭代版本可能比递归版本快几个数量级。在函数式语言中，两个实现的总体时间差可以忽略不计; 事实上，首先乘以较大的数字而不是较小的数字(这里给出的迭代版本恰好就是这样做的)的成本可能会超过选择迭代所节省的任何时间。

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 就是这样一种语言。注意下面关于尾递归的特殊情况的警告。

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

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.

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” 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:	尾部递归: ! 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 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 > /**

|}

* 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" > 

			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 >

}

350px

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



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 >

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

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

如果函数的时间复杂度在形式中

Short-circuiting the base case

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

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.

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

In C, the standard recursive algorithm may be implemented as:

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

类别: 递归

Category:Computability theory

类别: 可计算性理论

Category:Articles with example pseudocode

类别: 带有伪代码示例的文章

The short-circuited algorithm may be implemented as:

Category:Programming idioms

类别: 编程习惯用法

Category:Subroutines

分类: 子程序

This page was moved from wikipedia:en:Recursion (computer science). Its edit history can be viewed at 递归/edithistory