Java 递归

在 Java 中，一个调用自身的方法被称为递归方法。而这个过程被称为递归。

一个物理世界的例子就是放置两面平行相对的镜子。它们之间的任何物体都会被递归地反射。

递归如何工作？

在上面的例子中，我们从 `main` 方法（普通方法调用）内部调用了 `recurse()` 方法。并且，在 `recurse()` 方法内部，我们再次调用了同一个 `recurse` 方法。这就是递归调用。

为了停止递归调用，我们需要在方法内提供一些条件。否则，该方法将被无限次调用。

因此，我们使用if...else 语句（或类似方法）来终止方法内的递归调用。

示例：使用递归计算数字的阶乘

class Factorial {

    static int factorial( int n ) {
        if (n != 0)  // termination condition
            return n * factorial(n-1); // recursive call
        else
            return 1;
    }

    public static void main(String[] args) {
        int number = 4, result;
        result = factorial(number);
        System.out.println(number + " factorial = " + result);
    }
}

输出:

4 factorial = 24

在上面的例子中，我们有一个名为 `factorial()` 的方法。`factorial()` 方法通过 `number` 变量作为参数从 `main()` 方法中调用。

这里，请注意这条语句：

return n * factorial(n-1);

`factorial()` 方法正在调用自身。最初，`factorial()` 内部 `n` 的值为 4。在下一次递归调用期间，将 3 传递给 `factorial()` 方法。这个过程一直持续到 `n` 等于 0。

当 `n` 等于 0 时，`if` 语句返回 false，因此返回 1。最后，累积的结果被传递给 `main()` 方法。

阶乘程序的工作原理

下图将更清楚地说明使用递归如何执行阶乘程序。

递归的优点和缺点

当进行递归调用时，变量的新存储位置会被分配到堆栈上。当每个递归调用返回时，旧的变量和参数会从堆栈中移除。因此，递归通常使用更多的内存，并且通常速度较慢。

另一方面，递归解决方案要简单得多，并且在编写、调试和维护方面花费的时间更少。