Java - 递归：初学者指南

嘿，未来的Java巫师们！今天，我们将深入探讨神奇的递归世界。如果它听起来像是《哈利·波特》中的一个咒语，别担心——在本教程结束时，你将能够像一个专业人士一样施展递归咒语！

Java - Recursion

什么是递归？

想象一下，你在一个乱糟糟的房间里寻找你丢失的袜子。你打开一个抽屉，里面还有一个更小的抽屉。你打开那个，惊喜！里面还有一个更小的抽屉。这种打开抽屉里的抽屉的过程很像编程中的递归。

在Java中，递归是一个方法调用自身来解决问题的方式。这就像方法在说：“我知道部分解决方案，但是其余的，我会再次问我自己！”

Java中的递归如何工作？

让我们一步步来分解：

一个方法调用它自己
有一个条件来停止递归（基本情况）
问题被分解成更小、类似的子问题

以下是一个简单的例子：

public class RecursiveCountdown {
public static void countdown(int n) {
if (n == 0) {
System.out.println("发射！");
} else {
System.out.println(n);
countdown(n - 1);
}
}

public static void main(String[] args) {
countdown(5);
}
}

在这个例子中，countdown 是我们的递归方法。它不断地用更小的数字调用自己，直到它达到零。让我们看看发生了什么：

countdown(5) 打印5，然后调用 countdown(4)
countdown(4) 打印4，然后调用 countdown(3)
这一直持续到...
countdown(0) 打印 "发射！" 并停止

魔法发生的原因是每次调用 countdown 都在等待下一个调用完成之后才完成。这就像是一堆煎饼——我们不断地添加（调用），直到我们完成，然后我们从上往下吃（返回）。

Java递归示例

让我们看一些更多的例子，真正了解递归有多么强大。

示例1：阶乘计算

一个数的阶乘是所有到该数的正整数的乘积。例如，5!（5的阶乘）是 5 4 3 2 1 = 120。

public class Factorial {
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}

public static void main(String[] args) {
System.out.println("5的阶乘是: " + factorial(5));
}
}

以下是它的工作原理：

factorial(5) 返回 5 * factorial(4)
factorial(4) 返回 4 * factorial(3)
这一直持续到我们达到 factorial(1)，它返回 1
然后我们乘回去：1 2 3 4 5 = 120

示例2：斐波那契数列

斐波那契数列是一个数列，每个数字是前两个数字的和。它从0和1开始，然后是1，2，3，5，8，13，等等。

public class Fibonacci {
public static int fibonacci(int n) {
if (n <= 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}

public static void main(String[] args) {
for (int i = 0; i < 10; i++) {
System.out.print(fibonacci(i) + " ");
}
}
}

这个例子有点棘手：

对于 fibonacci(5)，我们计算 fibonacci(4) + fibonacci(3)
每次调用都会产生两个更多的调用，以此类推
它形成了一棵调用树，一直到 fibonacci(0) 和 fibonacci(1)
然后它在回来的路上添加所有的结果

在Java中使用递归的优点

简单性：对于某些问题，递归解决方案更容易理解。
减少代码大小：递归代码可以更紧凑。
解决复杂问题：有些问题，如图的遍历，本质上是递归的。

在Java中使用递归的缺点

内存使用：每次递归调用都会增加调用堆栈，这可能导致深度递归时的堆栈溢出。
性能：递归解决方案可能由于多次函数调用的开销而变慢。
调试困难：跟踪递归调用可能具有挑战性。

何时使用递归

当处理可以分解为类似子问题的问题时，递归会发挥出色。它非常适合：

树的遍历
图算法
分而治之算法
回溯问题

递归与迭代

有时，你可以使用递归或迭代（循环）来解决一个问题。以下是一个快速比较：

方面	递归	迭代
代码简单性	对于复杂问题通常更简单	对于简单任务更简单
性能	可能因为函数调用开销而变慢	通常更快
内存使用	可能使用更多内存（调用堆栈）	使用较少内存
问题适用性	更适合具有递归性质的问题	更适合简单重复性任务

编写递归函数的技巧

始终有一个基本情况：这是你的退出条件。没有它，你会永远递归！
确保朝着基本情况进步：每次递归调用都应该使你更接近基本情况。
相信递归：不要试图在脑海中追踪所有的调用。相信你的函数会在更小的输入上工作。

结论

递归在编程中就像一种超能力。可能需要一些练习来掌握，但是一旦你做到了，你将用全新的视角看待问题。记住，每次你使用递归时，你基本上都在代码中创建了一个小的时间机器，向你函数的过去和未来的版本发送消息。这有多酷？

继续练习，很快你就能在复杂问题周围施展递归的圆圈了！记住，如果你陷入了无限递归，只需按一下ctrl+C就能摆脱——不需要时间机器！编程愉快，未来的递归大师们！

Credits: Image by storyset