2,367
个编辑
更改
跳到导航
跳到搜索
第851行：
第851行： − {{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 is primarily a concern when many base cases are encountered, such as Null pointers in a tree, which can be linear in the number of function calls, hence significant savings for {{math|''O''(''n'')}} algorithms; this is illustrated below for a depth-first search. Short-circuiting on a tree corresponds to considering a leaf (non-empty node with no children) as the base case, rather than considering an empty node as the base case. If there is only a single base case, such as in computing the factorial, short-circuiting provides only {{math|''O''(1)}} savings. − − Conceptually, short-circuiting can be considered to either have the same base case and recursive step, only checking the base case before the recursion, or it can be considered to have a different base case (one step removed from standard base case) and a more complex recursive step, namely "check valid then recurse", as in considering leaf nodes rather than Null nodes as base cases in a tree. Because short-circuiting has a more complicated flow, compared with the clear separation of base case and recursive step in standard recursion, it is often considered poor style, particularly in academia.<ref>{{cite book − | last = Mongan − | first = John − | first2 = Eric |last2=Giguère |first3 = Noah |last3=Kindler − | title = Programming Interviews Exposed: Secrets to Landing Your Next Job − | url = https://archive.org/details/programminginter00mong_658 − | url-access = limited − | edition=3rd − | date= 2013 − | publisher= [[Wiley (publisher)|Wiley]] − | page = [https://archive.org/details/programminginter00mong_658/page/n148 115] − | isbn = 978-1-118-26136-1 − }}</ref> 第891行：
第873行： − A basic example of short-circuiting is given in [[depth-first search]] (DFS) of a binary tree; see [[#Binary trees|binary trees]] section for standard recursive discussion. − − The standard recursive algorithm for a DFS is: − − * base case: If current node is Null, return false − * recursive step: otherwise, check value of current node, return true if match, otherwise recurse on children 第905行：
第881行： − − In short-circuiting, this is instead: − − * check value of current node, return true if match, − * otherwise, on children, if not Null, then recurse. 第915行：
第886行： − − − − In terms of the standard steps, this moves the base case check ''before'' the recursive step. Alternatively, these can be considered a different form of base case and recursive step, respectively. Note that this requires a wrapper function to handle the case when the tree itself is empty (root node is Null). − In the case of a [[perfect binary tree]] of height ''h,'' there are 2<sup>''h''+1</sup>−1 nodes and 2<sup>''h''+1</sup> Null pointers as children (2 for each of the 2<sup>''h''</sup> leaves), so short-circuiting cuts the number of function calls in half in the worst case. − In C, the standard recursive algorithm may be implemented as: 第942行：
第907行： − The short-circuited algorithm may be implemented as: 第964行：
第928行： − − 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.
→基本情况下的短路
===基本情况下的短路===
===基本情况下的短路===
基本情况下的短路，也称为'''远程递归（arm's-length recursion）'''，包括在进行递归调用之前检查基本情况——即检查下一次调用是否为基本情况，而不是调用后再检查基本情况。特别是出于效率的考虑，为了避免函数调用后立即返回的开销，才进行了短路。需要注意的是，由于基本情况已经被检查过了（紧接在递归步骤之前），所以不需要再单独检查基本情况，但是当整体递归从基本情况本身开始时，确实需要使用一个封装函数来处理这种情况。例如，在阶乘函数中，正确的基本情况是0！=1，而对于1！立即返回1时短路，可能会漏掉0；这个问题可以通过包装器函数来缓解。
基本情况下的短路，也称为'''远程递归（arm's-length recursion）'''，包括在进行递归调用之前检查基本情况——即检查下一次调用是否为基本情况，而不是调用后再检查基本情况。特别是出于效率的考虑，为了避免函数调用后立即返回的开销，才进行了短路。需要注意的是，由于基本情况已经被检查过了（紧接在递归步骤之前），所以不需要再单独检查基本情况，但是当整体递归从基本情况本身开始时，确实需要使用一个封装函数来处理这种情况。例如，在阶乘函数中，正确的基本情况是0！=1，而对于1！立即返回1时短路，可能会漏掉0；这个问题可以通过包装器函数来缓解。
短路主要是在遇到很多基本情况的时候考虑使用，比如树的空指针，它随着函数调用次数呈线性增长，因此对于{{math|''O''(''n'')}}算法来说，可以大大节省成本。以深度优先搜索为例，树的短路对应于将叶子节点（没有子节点的非空节点）作为基本情况，而不是将空节点作为基本情况。如果只有一个基本情况，比如在计算阶乘的时候，短路只能节省O(1)级别的时间。
短路主要是在遇到很多基本情况的时候考虑使用，比如树的空指针，它随着函数调用次数呈线性增长，因此对于{{math|''O''(''n'')}}算法来说，可以大大节省成本。以深度优先搜索为例，树的短路对应于将叶子节点（没有子节点的非空节点）作为基本情况，而不是将空节点作为基本情况。如果只有一个基本情况，比如在计算阶乘的时候，短路只能节省O(1)级别的时间。
从概念上讲，短路递归可以认为和标准递归具有相同的基本情况和递归步骤，只是对基本情况的剪岔放在了递归前；也可以认为是具有不同的基本情况（比标准基本情况去掉一步）和更复杂的递归步骤，即 "先检查，若有效再递归"，如在树中考虑叶子节点而不是空节点作为基本情况。由于短路的流程比较复杂，相比标准递归中基本情况和递归步骤的清晰分离，短路往往被认为是糟糕的风格，尤其是在学术界。<ref>{{cite book
从概念上讲，短路递归可以认为和标准递归具有相同的基本情况和递归步骤，只是对基本情况的剪岔放在了递归前；也可以认为是具有不同的基本情况（比标准基本情况去掉一步）和更复杂的递归步骤，即 "先检查，若有效再递归"，如在树中考虑叶子节点而不是空节点作为基本情况。由于短路的流程比较复杂，相比标准递归中基本情况和递归步骤的清晰分离，短路往往被认为是糟糕的风格，尤其是在学术界。<ref>{{cite book
====深度优先搜索====
====深度优先搜索====
在二叉树的'''<font color="#ff8000"> 深度优先搜索 depth-first search</font>'''（DFS）中给出了一个短路的基本例子。
在二叉树的'''<font color="#ff8000"> 深度优先搜索 depth-first search</font>'''（DFS）中给出了一个短路的基本例子。
DFS的标准递归算法是：
DFS的标准递归算法是：
* 递归步骤：否则，检查当前节点的值，如果匹配则返回true，否则对子节点进行递归。
* 递归步骤：否则，检查当前节点的值，如果匹配则返回true，否则对子节点进行递归。
在短路的情况下，这反而是：
在短路的情况下，这反而是：
* 检查当前节点的值，如果匹配则返回true，
* 检查当前节点的值，如果匹配则返回true，
* 否则，在子代上，如果不是Null，则递归。
* 否则，在子代上，如果不是Null，则递归。
就标准步骤而言，这将基本情况的检查移到了递归步骤之前。或者，这些可以分别被认为是基例和递归步骤的不同形式。注意，这需要一个封装函数来处理树本身为空的情况（根节点为Null）。
就标准步骤而言，这将基本情况的检查移到了递归步骤之前。或者，这些可以分别被认为是基例和递归步骤的不同形式。注意，这需要一个封装函数来处理树本身为空的情况（根节点为Null）。
对于高度为''h''的完美全二叉树，有2<sup>''h''+1</sup>−1个节点和 2<sup>''h''+1</sup>个Null指针作为子节点（2h个叶子各2个），所以在最坏的情况下，短路可以将函数调用的次数减少一半。
对于高度为''h''的完美全二叉树，有2<sup>''h''+1</sup>−1个节点和 2<sup>''h''+1</sup>个Null指针作为子节点（2h个叶子各2个），所以在最坏的情况下，短路可以将函数调用的次数减少一半。
在C语言中，标准的递归算法可以实现为：
在C语言中，标准的递归算法可以实现为：
</syntaxhighlight>
</syntaxhighlight>
短路算法可以实现为：
短路算法可以实现为：
}
}
</syntaxhighlight>
</syntaxhighlight>
请注意布尔运算符<code>&&</code> (AND)在短路计算的使用，因此只有当节点有效(非Null)时才会进行递归调用。请注意，AND中的第一项是指向节点的指针，第二项是一个布尔表达式，所以整个表达式也是一个布尔表达式。这是递归短路中常见用法。布尔运算符<code>||</code>（OR）在短路计算时，只有在左子树的运算返回''false''时，才会执行右子树的运算。事实上，这些函数的整个控制流程可以用返回语句中的一个布尔表达式来代替，但可读性受到影响，而对效率却没有任何好处。
请注意布尔运算符<code>&&</code> (AND)在短路计算的使用，因此只有当节点有效(非Null)时才会进行递归调用。请注意，AND中的第一项是指向节点的指针，第二项是一个布尔表达式，所以整个表达式也是一个布尔表达式。这是递归短路中常见用法。布尔运算符<code>||</code>（OR）在短路计算时，只有在左子树的运算返回''false''时，才会执行右子树的运算。事实上，这些函数的整个控制流程可以用返回语句中的一个布尔表达式来代替，但可读性受到影响，而对效率却没有任何好处。