更改

* Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough

* Hybrid algorithm (at bottom) – switching to a different algorithm once data is small enough

* 包装函数（在顶部）

* 包装器函数（在顶部）

* 基本情况下的短路，也就是 "正常递归"（在底部）

* 短路到基本情况，也就是 '''<font color="#f668800">远程递归 Arm's-length recursion</font>'''（在底部）

* 混合算法（在底部）——一旦数据足够小，就切换到另一个的算法

* 混合算法（在底部）——一旦数据足够小，就切换到另一个的算法

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.

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.

 

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

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

'''<font color="#ff8000"> 包装函数wrapper function</font>'''是指直接调用但本身不递归的函数，而是调用一个单独的辅助函数，它实际上进行递归。

'''<font color="#ff8000"> 包装器函数 wrapper function</font>'''是指被直接调用但本身不递归的函数，而是调用一个单独的辅助函数，由这个辅助函数实际上进行递归。

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

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

包装器函数可用于验证参数(这样递归函数就可以跳过这些参数)、执行初始化(分配内存、初始化变量)，特别是对于辅助变量，如“递归级别”或备忘的部分计算，以及处理异常和错误。在支持嵌套函数的语言中，辅助函数可以嵌套在包装器函数内部，并使用共享的作用域。在没有嵌套函数的情况下，辅助函数是一个独立的函数，如果可能的话，辅助函数是私有的(因为它们没有被直接调用) ，通过使用传递引用的方式与包装函数共享信息。

包装器函数可用于验证参数(这样递归函数就可以跳过这些参数)、执行初始化(分配内存、初始化变量)，特别是对于辅助变量，如“递归级别”或记忆的部分计算，以及处理异常和错误。在支持嵌套函数的语言中，辅助函数可以嵌套在包装器函数内部，并使用共享的作用域。在没有嵌套函数的情况下，辅助函数是一个独立的函数，如果可能的话，辅助函数会被定义为私有的(因为它们没有被直接调用) ，通过使用引用传递的方式与包装器函数共享信息。

 

{{anchor|Arm's-length recursion}}

{{anchor|Arm's-length recursion}}

Short-circuiting the base case, also known as '''arm's-length recursion''', consists of checking the base case ''before'' making a recursive call – i.e., checking if the next call will be the base case, instead of calling and then checking for the base case. Short-circuiting is particularly done for efficiency reasons, to avoid the overhead of a function call that immediately returns. Note that since the base case has already been checked for (immediately before the recursive step), it does not need to be checked for separately, but one does need to use a wrapper function for the case when the overall recursion starts with the base case itself. For example, in the factorial function, properly the base case is 0! = 1, while immediately returning 1 for 1! is a short circuit, and may miss 0; this can be mitigated by a wrapper function.

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

基本情况下的短路，也称为'''远程递归（arm's-length recursion）'''，包括在进行递归调用之前检查基本情况——即检查下一次调用是否为基本情况，而不是调用后再检查基本情况。特别是出于效率的考虑，为了避免函数调用后立即返回的开销，才进行了短路。需要注意的是，由于基本情况已经被检查过了（紧接在递归步骤之前），所以不需要再单独检查基本情况，但是当整体递归从基本情况本身开始时，确实需要使用一个封装函数来处理这种情况。例如，在阶乘函数中，正确的基本情况是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.

短路主要是在遇到很多基本情况的时候，比如树上的空指针，它在函数调用次数上是可以线性计算的，因此对于O(n)算法来说，可以大大节省成本；下面以深度优先搜索为例进行说明。树上的短路对应于将叶子（没有子节点的非空节点）作为基本情况，而不是将空节点作为基本情况。如果只有一个基本情况，比如在计算阶乘的时候，短路只能节省O(1)。

短路主要是在遇到很多基本情况的时候考虑使用，比如树的空指针，它随着函数调用次数呈线性增长，因此对于{{math|''O''(''n'')}}算法来说，可以大大节省成本。以深度优先搜索为例，树的短路对应于将叶子节点（没有子节点的非空节点）作为基本情况，而不是将空节点作为基本情况。如果只有一个基本情况，比如在计算阶乘的时候，短路只能节省O(1)级别的时间。

Conceptually, short-circuiting can be considered to either have the same base case and recursive step, only checking the base case before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.<ref>{{cite book

Conceptually, short-circuiting can be considered to either have the same base case and recursive step, only checking the base case before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.<ref>{{cite book

}}</ref>

}}</ref>

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

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

 

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

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

在二叉树的'''<font color="#ff8000"> 深度优先搜索depth-first search</font>'''（DFS）中给出了一个短路的基本例子；标准递归讨论见二叉树部分。

在二叉树的'''<font color="#ff8000"> 深度优先搜索 depth-first search</font>'''（DFS）中给出了一个短路的基本例子。

The standard recursive algorithm for a DFS is:

The standard recursive algorithm for a DFS is:

DFS的标准递归算法是：

DFS的标准递归算法是：

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

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

 

In short-circuiting, this is instead:

In short-circuiting, this is instead:

 

* check value of current node, return true if match,

* check value of current node, return true if match,

* otherwise, on children, if not Null, then recurse.

* otherwise, on children, if not Null, then recurse.

否则，在子代上，如果不是Null，则递归。

 

* 否则，在子代上，如果不是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 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.

在高度为h的完美二叉树的情况下，有2h+1-1个节点和2h+1个Null指针作为子节点（2h个叶子各2个），所以在最坏的情况下，短路可以将函数调用的次数减少一半。

对于高度为''h''的完美全二叉树，有2^''h''+1&minus;1个节点和 2^''h''+1个Null指针作为子节点（2h个叶子各2个），所以在最坏的情况下，短路可以将函数调用的次数减少一半。

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

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

在C语言中，标准的递归算法可以实现为：

在C语言中，标准的递归算法可以实现为：

<syntaxhighlight lang="C">

<syntaxhighlight lang="C">

bool tree_contains(struct node *tree_node, int i) {

bool tree_contains(struct node *tree_node, int i) {

     if (tree_node == NULL)

     if (tree_node == NULL)

         return false;  // base case

         return false;  // base case 基本情况

     else if (tree_node->data == i)

     else if (tree_node->data == i)

         return true;

         return true;

短路算法可以实现为：

短路算法可以实现为：

<syntaxhighlight lang="C">

<syntaxhighlight lang="C">

// Wrapper function to handle empty tree

// Wrapper function to handle empty tree 处理树为空的包装器函数

bool tree_contains(struct node *tree_node, int i) {

bool tree_contains(struct node *tree_node, int i) {

     if (tree_node == NULL)

     if (tree_node == NULL)

         return false;  // empty tree

         return false;  // empty tree 空树

     else

     else

         return tree_contains_do(tree_node, i);  // call auxiliary function

         return tree_contains_do(tree_node, i);  // call auxiliary function 调用辅助函数

}

}

// Assumes tree_node != NULL

// Assumes tree_node != NULL 假设树不为空

bool tree_contains_do(struct node *tree_node, int i) {

bool tree_contains_do(struct node *tree_node, int i) {

     if (tree_node->data == i)

     if (tree_node->data == i)

         return true;  // found

         return true;  // found 找到节点

     else  // recurse

     else  // recurse 递归

         return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||

         return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||

               (tree_node->right && tree_contains_do(tree_node->right, i));

               (tree_node->right && tree_contains_do(tree_node->right, i));

Note the use of [[short-circuit evaluation]] of the Boolean &amp;&amp; (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.

Note the use of [[short-circuit evaluation]] of the Boolean &amp;&amp; (AND) operators, so that the recursive call is only made if the node is valid (non-Null). Note that while the first term in the AND is a pointer to a node, the second term is a bool, so the overall expression evaluates to a bool. This is a common idiom in recursive short-circuiting. This is in addition to the short-circuit evaluation of the Boolean || (OR) operator, to only check the right child if the left child fails. In fact, the entire [[control flow]] of these functions can be replaced with a single Boolean expression in a return statement, but legibility suffers at no benefit to efficiency.

请注意布尔&& (AND)运算符的短路评估的使用，因此只有当节点有效(非Null)时才会进行递归调用。请注意，AND中的第一项是指向节点的指针，第二项是一个布尔，所以整体表达式评价为一个布尔。这是递归短路中常见的一个成语。这是在布尔||（OR）运算符的短路评价之外，只有在左子运算失败时才检查右子运算符。事实上，这些函数的整个控制流程可以用返回语句中的一个布尔表达式来代替，但可读性受到影响，对效率却没有任何好处。

请注意布尔运算符<code>&&</code> (AND)在短路计算的使用，因此只有当节点有效(非Null)时才会进行递归调用。请注意，AND中的第一项是指向节点的指针，第二项是一个布尔表达式，所以整个表达式也是一个布尔表达式。这是递归短路中常见用法。布尔运算符<code>||</code>（OR）在短路计算时，只有在左子树的运算返回''false''时，才会执行右子树的运算。事实上，这些函数的整个控制流程可以用返回语句中的一个布尔表达式来代替，但可读性受到影响，而对效率却没有任何好处。

 

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.

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中，由混合合并排序/插入排序派生出来。

由于重复的函数调用和返回，递归算法对于小规模数据往往效率不高。出于这个原因，递归算法的高效实现往往是先实现一个标准递归算法，但当输入变小时，再切换到不同的算法。一个重要的例子是归并排序，当数据足够小的时候，常常通过切换到非递归的插入排序来实现，如'''<font color="#ff8000">平铺合并排序 tiled merge sort</font>'''。混合递归算法往往可以进一步完善，如Timsort中，就是由混合归并排序/插入排序派生出来的。

==Recursion versus iteration==

==Recursion versus iteration==