什么是递归？
在编程中，递归（Recursion）是指一个方法直接或间接调用自身的过程。理解递归的核心在于两个关键点：终止条件（何时停止递归）和递归关系（如何分解问题）。
想象一下生活中的例子：你想知道一个盒子里有多少颗糖，盒子是嵌套的，你只能从最外面的盒子开始，每次打开一个盒子看里面的糖，直到最里面的盒子。这里，“打开盒子”就是递归操作，而“盒子为空”就是终止条件。
递归的核心原理¶
递归的执行过程可以类比为“剥洋葱”：每一层调用都是在解决“更小的问题”，直到遇到无法再分解的最小问题（终止条件），然后逐层返回结果。
从计算机执行角度来看，每次递归调用都会在内存中创建一个“方法调用栈”的新帧，用于存储当前方法的参数、局部变量和返回地址。当遇到终止条件时，最内层的方法会先返回结果，然后外层的方法依次计算并返回。
实例1：阶乘（Factorial）¶
阶乘是递归的经典例子，数学定义为：
- \( n! = n \times (n-1) \times (n-2) \times \dots \times 1 \)
- 特殊情况：\( 0! = 1 \)，\( 1! = 1 \)
递归实现思路：
1. 终止条件：当 \( n = 0 \) 或 \( n = 1 \) 时，返回 1。
2. 递归关系：当 \( n > 1 \) 时，返回 \( n \times \text{factorial}(n-1) \)。
Java代码实现：
public class RecursionExample {
// 阶乘递归方法
public static long factorial(int n) {
// 终止条件：n为负数时抛出异常（非法参数）
if (n < 0) {
throw new IllegalArgumentException("阶乘参数不能为负数");
}
// 终止条件：n=0或n=1时返回1
if (n == 0 || n == 1) {
return 1;
}
// 递归关系：n * (n-1)!
return n * factorial(n - 1);
}
public static void main(String[] args) {
int num = 5;
long result = factorial(num);
System.out.println(num + "的阶乘是：" + result); // 输出：5的阶乘是：120
}
}
执行过程分析：
- 调用 factorial(5) → 进入递归，需计算 \( 5 \times factorial(4) \)
- factorial(4) → \( 4 \times factorial(3) \)
- factorial(3) → \( 3 \times factorial(2) \)
- factorial(2) → \( 2 \times factorial(1) \)
- factorial(1) → 满足终止条件，返回 1
- 逐层返回：\( 2 \times 1 = 2 \) → \( 3 \times 2 = 6 \) → \( 4 \times 6 = 24 \) → \( 5 \times 24 = 120 \)
实例2：斐波那契数列（Fibonacci）¶
斐波那契数列定义为：
- \( F(0) = 0 \)，\( F(1) = 1 \)
- 当 \( n > 1 \) 时，\( F(n) = F(n-1) + F(n-2) \)
递归实现思路：
1. 终止条件：当 \( n = 0 \) 时返回 0，当 \( n = 1 \) 时返回 1。
2. 递归关系：当 \( n > 1 \) 时，返回 \( F(n-1) + F(n-2) \)。
Java代码实现：
public class RecursionExample {
// 斐波那契递归方法
public static long fibonacci(int n) {
// 终止条件：n为负数时抛出异常
if (n < 0) {
throw new IllegalArgumentException("斐波那契参数不能为负数");
}
// 终止条件：n=0返回0，n=1返回1
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
// 递归关系：F(n) = F(n-1) + F(n-2)
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 5;
long result = fibonacci(n);
System.out.println("斐波那契数列第" + n + "项是：" + result); // 输出：5
}
}
执行过程分析：
- 计算 \( F(5) \) 时，会递归调用 \( F(4) + F(3) \)
- \( F(4) = F(3) + F(2) \)，\( F(3) = F(2) + F(1) \)，以此类推，直到 \( F(1) = 1 \) 和 \( F(0) = 0 \)
- 最终结果：\( F(5) = 5 \)
递归的优缺点与注意事项¶
优点：¶
- 逻辑清晰：适合描述有递归关系的数学问题（如阶乘、斐波那契、汉诺塔）。
- 代码简洁：无需复杂循环，直接按数学定义转化为代码。
缺点：¶
- 栈溢出风险：递归深度过大时（如计算 \( 1000! \)），会导致
StackOverflowError（调用栈耗尽）。 - 效率问题：部分递归存在重复计算（如斐波那契递归会重复计算 \( F(3) \) 等），可通过记忆化搜索优化。
注意事项：¶
- 必须有终止条件：否则会无限递归（如忘记
n == 0的终止条件，阶乘会一直调用factorial(-1)直到崩溃）。 - 参数范围：递归调用时参数需逐步减小，避免无限循环（如传递
n+1而非n-1会导致参数增大）。 - 数据类型：阶乘结果增长快，需用
long而非int（如 \( 13! = 6227020800 \) 超过int范围）。
总结¶
递归是解决“自相似问题”的利器，核心是分解问题为更小的子问题并终止于最小问题。初学者建议从简单场景（如阶乘）入手，理解调用栈和终止条件，再逐步应用到复杂场景（如斐波那契、树的遍历）。实际开发中，若递归深度较大或重复计算严重，可改用循环或动态规划优化，但递归的思想仍值得掌握。