Java 递归
提示
- 递归方法的定义:在Java中,递归是指一个方法调用自己的过程,用于执行重复或共享任务。
- 递归的工作原理和结束条件:递归通过在方法内部再次调用同一个方法来工作,需要一个终止条件(如
if
语句)来防止无限循环。 - 递归的优缺点:递归通常比非递归解决方案更简单和直观,但可能会消耗更多内存并导致性能降低,因为每次方法调用都要在栈上分配新的变量和参数。
附图展示了递归调用的过程,其中一个函数(例如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()
方法。
阶乘程序的工作原理
下面的图片将更好地帮助你理解使用递归执行阶乘程序的过程。
递归的优点和缺点
当进行递归调用时,变量的新存储位置会在栈上分配。当每次递归调用返回时,旧的变量和参数会从栈中移除。因此,递归通常会使用更多的内存,并且通常比较慢。
另一方面,递归解决方案通常更简单,编写、调试和维护所需的时间更少。
推荐阅读:递归的优点和缺点是什么?