跳到主要内容

Java 递归

提示
  1. 递归方法的定义：在Java中，递归是指一个方法调用自己的过程，用于执行重复或共享任务。
  2. 递归的工作原理和结束条件：递归通过在方法内部再次调用同一个方法来工作，需要一个终止条件（如if语句）来防止无限循环。
  3. 递归的优缺点：递归通常比非递归解决方案更简单和直观，但可能会消耗更多内存并导致性能降低，因为每次方法调用都要在栈上分配新的变量和参数。

附图展示了递归调用的过程，其中一个函数（例如factorial）不断地调用自己，直到达到一个基本条件（如n == 0），然后开始解开递归堆栈，返回结果。

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

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

递归是如何工作的？​

一个函数正在调用自己

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

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

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

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

class Factorial {

    static int factorial( int n ) {
        if (n != 0)  // 终止条件
            return n * factorial(n-1); // 递归调用
        else
            return 1;
    }

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

输出:

4 的阶乘 = 24

在上面的示例中，我们有一个名为 factorial() 的方法。factorial() 从 main() 方法中被调用，将 number 变量作为参数传递。

这里，注意这个语句，

return n * factorial(n-1);

factorial() 方法正在调用它自己。最初，factorial() 内的 n 值为 4。在下一个递归调用中，3 被传递给 factorial() 方法。这个过程一直持续到 n 等于 0 为止。

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

阶乘程序的工作原理​

下面的图片将更好地帮助你理解使用递归执行阶乘程序的过程。

使用递归计算数字的阶乘

递归的优点和缺点​

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

另一方面，递归解决方案通常更简单，编写、调试和维护所需的时间更少。

推荐阅读：递归的优点和缺点是什么？

最后于 更新