Induction and Recursion
Induction and Recursion
复制标题
归纳与递归
DOI：
10.1007/978-1-4612-0075-8_3
复制
发表时间：
2002
影响因子：
1.1
通讯作者：
J. Storer
中科院分区：
文献类型：
--
作者：
J. Storer
再次考虑功能n！。我们已经看到了如何用循环计算数字1到n的循环。计算n的另一种方法！与递归程序一起称为：
$$ \ begin {catched}函数fact（n）\ hfill \\如果n \ leqslant 1 \ hfill \\，然后返回1 \ hfill \\ else return n * fact \ left \ left（{n -1} \ right）\ hfill \\ end \ hfill \\ \ end {catched} $$
因为\（n！= n * \ left（{n -1} \ right）！\）可以通过求解相同问题的较小版本然后乘以n来计算它。在这个非常简单的示例中，递归程序直接对应于循环。如果递归是“解开的”，则计算n！，我们计算\（\ left（{n -1} \ right）！\），以计算\（\ left（{n -1} \ right）！\）！我们计算\（\ left（{n -2} \ right）！\），依此类推，直到我们降至1;然后，我们向后计算\（2 * 1 = 2 \），然后\（3 * 2 = 6 \），然后\（4 * 6 = 24 \），依此类推。这种形式的递归形式，通常称为尾部递归，将自己称为问题的“尾巴”，然后进行一些简单的计算（在这种情况下，是乘法）以结合问题的“头”。实际上，这是一种简单的递归形式，以至于“智能”编译器可以检测到它并将其转换为使用O（1）空间的循环。
Consider again the function n!. We have already seen how to compute it with a loop that multiplies the numbers 1 through n. Another way to compute n! is with a recursive program that calls itself:
$$ \begin{gathered} function FACT(n) \hfill \\ if n \leqslant 1 \hfill \\ then return 1 \hfill \\ else return n * FACT\left( {n - 1} \right) \hfill \\ end \hfill \\ \end{gathered} $$
Because\( n! = n * \left( {n - 1} \right)! \), it can be computed by solving a smaller version of the same problem and then multiplying by n. In this very simple example, the recursive program corresponds directly to a loop. If the recursion is "unwound", to compute n!, we compute \( \left( {n - 1} \right)! \), to compute \( \left( {n - 1} \right)! \) we compute \( \left( {n - 2} \right)! \), and so on until we get down to 1; then we work backwards computing \( 2 * 1 = 2 \), then \( 3 * 2 = 6 \), then \( 4 * 6 = 24 \), and so on. This form of recursion, often called tail recursion, calls itself on the "tail" of the problem and then does some simple computation (in this case, a multiplication) to incorporate the "head" of the problem. In fact, it is such a simple form of recursion that a "smart" compiler can detect it and translate it to a loop that uses O(1) space.