更改

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.

{{Programming paradigms}}

{{Programming paradigms}}

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

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

{{quote|text=The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement.  In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.|author=[[Niklaus Wirth]]|source=''Algorithms + Data Structures = Programs'', 1976<ref>{{cite book |last      = Wirth

{{quote|text=The power of recursion evidently lies in the possibility of defining an infinite set of objects by a finite statement.  In the same manner, an infinite number of computations can be described by a finite recursive program, even if this program contains no explicit repetitions.|author=[[Niklaus Wirth]]|source=''Algorithms + Data Structures = Programs'', 1976<ref>{{cite book |last      = Wirth

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

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

大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些’’’<font color=’’#ff8000’’> 函数式编程语言functional programming language</font>’’’(例如Clojure)不定义任何循环结构，而只依赖递归来重复调用代码。在’’’<font color=’’#ff8000’’>可计算性理论 computability theory</font>’’’中证明了这些递归语言是’’’<font color=’’#ff8000’’>图灵完备Turing complete </font>’’’图灵完备的;这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(它们可以用于解决相同的问题)。

大多数计算机编程语言通过允许函数在其自己的代码中调用自己来支持递归。一些函数式编程语言(例如Clojure)不定义任何循环结构，而只依赖递归来重复调用代码。在可计算性理论中证明了这些递归语言是图灵完备的;这意味着它们与基于{{code|while}} 和{{code|for}}等控制结构的命令式语言一样强大(它们可以用于解决相同的问题)。

Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for large problems, it is fundamental to use optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}}

Repeatedly calling a function from within itself may cause the [[call stack]] to have a size equal to the sum of the input sizes of all involved calls. It follows that, for problems that can be solved easily by iteration, recursion is generally less [[algorithmic efficiency|efficient]], and, for large problems, it is fundamental to use optimization techniques such as [[tail call]] optimization.{{CN|date=November 2019}}

从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的。

从自身内部反复调用一个函数可能会导致调用堆栈的大小等于所有参与调用的输入大小的总和。由此可见，对于可以通过迭代轻松解决的问题，递归的效率一般较低，而对于大型问题，使用诸如尾部调用优化之类的优化技术才是基本的。

  ==Recursive functions and algorithms==

==Recursive functions and algorithms==

递归函数和算法

递归函数和算法

A common [[computer programming]] tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the [[divide-and-conquer method]]; when combined with a [[lookup table]] that stores the results of solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as [[dynamic programming]] or [[memoization]].

A common [[computer programming]] tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the [[divide-and-conquer method]]; when combined with a [[lookup table]] that stores the results of solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as [[dynamic programming]] or [[memoization]].

A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method; when combined with a lookup table that stores the results of solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as dynamic programming or memoization.

A common computer programming tactic is to divide a problem into sub-problems of the same type as the original, solve those sub-problems, and combine the results. This is often referred to as the divide-and-conquer method; when combined with a lookup table that stores the results of solving sub-problems (to avoid solving them repeatedly and incurring extra computation time), it can be referred to as dynamic programming or memoization.

A recursive function definition has one or more ''base cases'', meaning input(s) for which the function produces a result [[Trivial (mathematics)|trivial]]ly (without recurring), and one or more ''recursive cases'', meaning input(s) for which the program recurs (calls itself).  For example, the [[factorial]] function can be defined recursively by the equations {{math|1=0! = 1}} and, for all {{math|''n'' > 0}}, {{math|1=''n''! = ''n''(''n'' − 1)!}}. Neither equation by itself constitutes a complete definition; the first is the base case, and the second is the recursive case. Because the base case breaks the chain of recursion, it is sometimes also called the "terminating case".

A recursive function definition has one or more ''base cases'', meaning input(s) for which the function produces a result [[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".

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones.  In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached.  (Functions that are not intended to terminate under normal circumstances—for example, some system and server processes—are an exception to this.)  Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.

The job of the recursive cases can be seen as breaking down complex inputs into simpler ones.  In a properly designed recursive function, with each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached.  (Functions that are not intended to terminate under normal circumstances—for example, some system and server processes—are an exception to this.)  Neglecting to write a base case, or testing for it incorrectly, can cause an infinite loop.

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

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

For some functions (such as one that computes the [[series (mathematics)|series]] for {{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}}) there is not an obvious base case implied by the input data; for these one may add a [[parameter]] (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by [[corecursion]],{{how?|date=September 2020}} where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the ''n''th term (''n''th partial sum)".

For some functions (such as one that computes the [[series (mathematics)|series]] for {{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}}) there is not an obvious base case implied by the input data; for these one may add a [[parameter]] (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by [[corecursion]],{{how?|date=September 2020}} where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the ''n''th term (''n''th partial sum)".

For some functions (such as one that computes the series for  {{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}} )there is not an obvious base case implied by the input data; for these one may add a parameter (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by corecursion, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".

For some functions (such as one that computes the series for  {{math|1=''[[e (mathematical constant)|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...}} )there is not an obvious base case implied by the input data; for these one may add a parameter (such as the number of terms to be added, in our series example) to provide a 'stopping criterion' that establishes the base case. Such an example is more naturally treated by corecursion, where successive terms in the output are the partial sums; this can be converted to a recursion by using the indexing parameter to say "compute the nth term (nth partial sum)".

对于一些函数（例如计算e = 1/0! + 1/1! + 1/2! + 1/3! + ...）输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个’’’<font color=’’#ff8000’’>参数 parameter</font>’’’（比如在我们的系列示例中要添加的术语数量）来提供一个 "停止标准"，以建立基本情况。这样的例子更自然地用’’’<font color=’’#ff8000’’> 共递归corecursion</font>’’’来处理，其中输出中的连续项是部分和；这可以通过使用索引参数表示“计算第n项(第n部分和)”来转换为递归。

对于一些函数（例如计算e = 1/0! + 1/1! + 1/2! + 1/3! + ...）输入数据并没有明显的基本情况；对于这些函数，我们可以添加一个参数（比如在我们的系列示例中要添加的术语数量）来提供一个 "停止标准"，以建立基本情况。这样的例子更自然地用共递归来处理，其中输出中的连续项是部分和；这可以通过使用索引参数表示“计算第n项(第n部分和)”来转换为递归。

==Recursive data types==

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

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

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

===Inductively defined data===

===Inductively defined data===

Another example of inductive definition is the natural numbers (or positive integers):

Another example of inductive definition is the natural numbers (or positive integers):

Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages.  Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:

Similarly recursive definitions are often used to model the structure of expressions and statements in programming languages.  Language designers often express grammars in a syntax such as Backus–Naur form; here is such a grammar, for a simple language of arithmetic expressions with multiplication and addition:

同样递归定义也经常被用来模拟编程语言中表达式和语句的结构。语言设计者经常用’’’<font color=’’#ff8000’’> Backus-Naur形式Backus–Naur form</font>’’’ 这样的语法来表达语法，这里有一种语法，适用于一个简单的有乘法和加法的算术表达式的语言：

同样递归定义也经常被用来模拟编程语言中表达式和语句的结构。语言设计者经常用Backus-Naur形式这样的语法来表达语法，这里有一种语法，适用于一个简单的有乘法和加法的算术表达式的语言：

<syntaxhighlight lang="bnf">

<syntaxhighlight lang="bnf">

Recursion that only contains a single self-reference is known as , while recursion that contains multiple self-references is known as . Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.

Recursion that only contains a single self-reference is known as , while recursion that contains multiple self-references is known as . Standard examples of single recursion include list traversal, such as in a linear search, or computing the factorial function, while standard examples of multiple recursion include tree traversal, such as in a depth-first search.

Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.

Single recursion is often much more efficient than multiple recursion, and can generally be replaced by an iterative computation, running in linear time and requiring constant space. Multiple recursion, by contrast, may require exponential time and space, and is more fundamentally recursive, not being able to be replaced by iteration without an explicit stack.

Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.

Indirect recursion is also called mutual recursion, which is a more symmetric term, though this is simply a difference of emphasis, not a different notion. That is, if f calls g and then g calls f, which in turn calls g again, from the point of view of f alone, f is indirectly recursing, while from the point of view of g alone, it is indirectly recursing, while from the point of view of both, f and g are mutually recursing on each other. Similarly a set of three or more functions that call each other can be called a set of mutually recursive functions.

===Anonymous recursion===

===Anonymous recursion===

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

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

===Structural versus generative recursion===

===Structural versus generative recursion===

* All structurally recursive functions on finite ([[Recursive data type|inductively defined]]) data structures can easily be shown to terminate, via [[structural induction]]: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.  

* All structurally recursive functions on finite ([[Recursive data type|inductively defined]]) data structures can easily be shown to terminate, via [[structural induction]]: intuitively, each recursive call receives a smaller piece of input data, until a base case is reached.  

* Generatively recursive functions, in contrast, do not necessarily feed smaller input to their recursive calls, so proof of their termination is not necessarily as simple, and avoiding [[infinite loops]] requires greater care. These generatively recursive functions can often be interpreted as corecursive functions – each step generates the new data, such as successive approximation in Newton's method – and terminating this corecursion requires that the data eventually satisfy some condition, which is not necessarily guaranteed.

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

===Recursive procedures===

===Recursive procedures===

====Factorial====

====Factorial====

阶乘

阶乘

}}</ref> There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with ''n'' disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?

}}</ref> There are three pegs which can hold stacks of disks of different diameters. A larger disk may never be stacked on top of a smaller. Starting with ''n'' disks on one peg, they must be moved to another peg one at a time. What is the smallest number of steps to move the stack?

''Function definition'':

''Function definition'':

The [[binary search]] algorithm is a method of searching a [[sorted array]] for a single element by cutting the array in half with each recursive pass.  The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.

The [[binary search]] algorithm is a method of searching a [[sorted array]] for a single element by cutting the array in half with each recursive pass.  The trick is to pick a midpoint near the center of the array, compare the data at that point with the data being searched and then responding to one of three possible conditions: the data is found at the midpoint, the data at the midpoint is greater than the data being searched for, or the data at the midpoint is less than the data being searched for.

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half.  The binary search procedure is then called recursively, this time on the new (and smaller) array.  Typically the array's size is adjusted by manipulating a beginning and ending index.  The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half.  The binary search procedure is then called recursively, this time on the new (and smaller) array.  Typically the array's size is adjusted by manipulating a beginning and ending index.  The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

A [[wrapper function]] is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.

A [[wrapper function]] is a function that is directly called but does not recurse itself, instead calling a separate auxiliary function which actually does the recursion.

Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for [[memoization]], and handle exceptions and errors. In languages that support [[nested function]]s, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using [[pass-by-reference]].

Wrapper functions can be used to validate parameters (so the recursive function can skip these), perform initialization (allocate memory, initialize variables), particularly for auxiliary variables such as "level of recursion" or partial computations for [[memoization]], and handle exceptions and errors. In languages that support [[nested function]]s, the auxiliary function can be nested inside the wrapper function and use a shared scope. In the absence of nested functions, auxiliary functions are instead a separate function, if possible private (as they are not called directly), and information is shared with the wrapper function by using [[pass-by-reference]].

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.

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；这可以通过包装函数来缓解。

基本情况下的短路，也称为正常递归，包括在进行递归调用之前检查基本情况--即检查下一次调用是否为基本情况，而不是调用后再检查基本情况。特别是出于效率的考虑，为了避免函数调用后立即返回的开销，才进行了短路。需要注意的是，由于基本情况已经被检查过了（紧接在递归步骤之前），所以不需要单独检查基本情况，但是当整体递归从基本情况本身开始时，确实需要使用一个封装函数来处理这种情况。例如，在阶乘函数中，正确的基本情况是0！=1，而对于1！立即返回1是短路，可能会漏掉0；这可以通过包装函数来缓解。

Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for {{math|''O''(''n'')}} algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only {{math|''O''(1)}} savings.

Short-circuiting is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for {{math|''O''(''n'')}} algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only {{math|''O''(1)}} savings.

}}</ref>

}}</ref>

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

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

====Depth-first search====

====Depth-first search====

A basic example of short-circuiting is given in [[depth-first search]] (DFS) of a binary tree; see [[#Binary trees|binary trees]] section for standard recursive discussion.

A basic example of short-circuiting is given in [[depth-first search]] (DFS) of a binary tree; see [[#Binary trees|binary trees]] section for standard recursive discussion.

The standard recursive algorithm for a DFS is:

The standard recursive algorithm for a DFS is:

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 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&minus;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 the case of a [[perfect binary tree]] of height ''h,'' there are 2^''h''+1&minus;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.

递归算法的时间效率

递归算法的时间效率

The [[time complexity|time efficiency]] of recursive algorithms can be expressed in a [[recurrence relation]] of [[Big O notation]].  They can (usually) then be simplified into a single Big-O term.

The [[time complexity|time efficiency]] of recursive algorithms can be expressed in a [[recurrence relation]] of [[Big O notation]].  They can (usually) then be simplified into a single Big-O term.

===Shortcut rule (master theorem)===

===Shortcut rule (master theorem)===