6.7　再谈递归

6.7　再谈递归

学习完返回值的方法后，你掌握的 Java 编程知识就是图灵完备的（Turing complete）了。这意味着你能用 Java 来计算任何可计算的东西，只要“可计算”的定义是合理的。这个概念是由阿隆佐 · 邱奇（Alonzo Church）和阿兰 · 图灵（Alan Turing）提出的，因此被称为邱奇—图灵论题。

为了让你了解学过的工具能做哪些事情，我们来看一些方法，这些方法可用于计算以递归方式定义的函数。递归定义引用了当前定义的东西，从这种意义上说，它类似于循环定义。

当然，真正意义上的循环定义用处不大，请看以下定义。

递归（recursive）

用于描述递归的方法。

如果在字典中看到这个定义，你可能非常恼火。但如果用 Google 搜索 recursion，它将显示 Did you mean: recursion，这是一个只有知道内情的人才懂的玩笑。

很多数学函数都是以递归的方式定义的，因为这常常是最简单的方式。例如，整数 n 的阶乘（factorial，表示为 n!）的定义类似于以下这样：

$\begin{aligned}&0!=1\\&n!=n\cdot(n-1)!\end{aligned}$

请不要将数学符号 ! 同 Java 运算符 ! 混为一谈，前者表示阶乘，后者表示逻辑非。上述定义指出，factorial(0) 为 1，而 factorial(n) 为 n*factorial(n - 1)。

因此，factorial(3) 为 3*factorial(2)；factorial(2) 为 2*factorial(1)；factorial(1) 为 1*factorial(0)；factorial(0) 为 1。通过整合，可以得到 factorial(3) 为 3*2*1*1，即 6。

如果能用公式表示递归定义，那么就可以轻松地编写有关的计算方法。为此，首先需要确定形参和返回类型。因为阶乘是针对整数定义的，所以计算阶乘的方法接受一个 int 形参，并返回一个 int 值。以下代码很好地表示了这一点：

public static int factorial(int n) {
    return 0;
}

接下来需要考虑基线条件。如果提供的实参为 0，则返回 1。

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    return 0;
}

否则，就需要执行递归调用来计算 n-1 的阶乘，并将结果乘以 n（这是比较有趣的部分）：

public static int factorial(int n) {
    if (n == 0) {
        return 1;
    }
    int recurse = factorial(n - 1);
    int result = n * recurse;
    return result;
}

这个程序的执行流程与 5.8 节中的 countdown 类似。如果我们用 3 来调用 factorial，执行流程将如下所示。

因为 n 为 3，所以执行第二个分支——计算 n-1 的阶乘……

　　因为 n 为 2，所以执行第二个分支——计算 n-1 的阶乘……

　　　　因为 n 为 1，所以执行第二个分支——计算 n-1 的阶乘……

　　　　　　因为 n 为 0，所以执行第一个分支——立即返回 1。

　　　　将返回值（1）乘以 n（1），并将结果返回。

　　将返回值（1）乘以 n（2），并将结果返回。

将返回值（2）乘以 n（3），并将结果（6）返回给 factorial(3) 的调用者。

图 6-2 显示了这个调用序列的栈图，其中的返回值沿栈向上传递。注意，最后一个栈帧中没有 recurse 和 result，这是因为当 n == 0 时，声明了这些变量的代码不会被执行。

图 6-2：方法 factorial 的栈图

6.7 再谈递归

6.7 再谈递归

6.7　再谈递归

6.7　再谈递归