在Java中,一个方法自己调用自己的行为被称为递归。
递归就是“自己调用自己”，它是一种解决问题的方法，通常将一个大问题分解成一个或多个与原问题相似但规模更小的子问题，直到子问题小到可以直接解决为止。
递归的两个核心要素
一个正确的递归方法必须包含以下两个关键部分：
- 基本情况：也称为终止条件，这是递归的“出口”，它定义了递归何时应该停止，如果没有基本情况，递归就会无限进行下去，最终导致栈溢出错误。
- 递归情况：方法在满足特定条件时，调用一个更小规模的、与自己相同的版本，从而向基本情况迈进。
一个经典的例子：计算阶乘
我们来用计算阶乘这个经典例子来理解递归。
数学定义：
n! = n * (n-1) * (n-2) * ... * 1- 也可以定义为：
n! = n * (n-1)! - 基本情况：
0! = 1或1! = 1
Java代码实现：
public class RecursionExample {
// 一个递归方法，用于计算数字的阶乘
public static long factorial(int n) {
// 1. 基本情况 (终止条件)
// n 是 0 或 1，阶乘的结果就是 1。
if (n == 0 || n == 1) {
return 1;
}
// 2. 递归情况
// 否则，返回 n * (n-1) 的阶乘。
// 这一步就是方法在调用自己。
else {
return n * factorial(n - 1);
}
}
public static void main(String[] args) {
int number = 5;
long result = factorial(number);
System.out.println(number + " 的阶乘是: " + result); // 输出: 5 的阶乘是: 120
}
}
执行过程分析（以 factorial(5) 为例）：
factorial(5)被调用，它不满足基本情况，所以执行return 5 * factorial(4);，现在需要等待factorial(4)的结果。factorial(4)被调用，它不满足基本情况，所以执行return 4 * factorial(3);，现在需要等待factorial(3)的结果。factorial(3)被调用，它不满足基本情况，所以执行return 3 * factorial(2);，现在需要等待factorial(2)的结果。factorial(2)被调用，它不满足基本情况，所以执行return 2 * factorial(1);，现在需要等待factorial(1)的结果。factorial(1)被调用。它满足了基本情况！ 直接返回1。- 现在调用栈开始“回溯”，把结果一层层返回：
factorial(2)得到了factorial(1)的结果1，所以它返回2 * 1 = 2。factorial(3)得到了factorial(2)的结果2，所以它返回3 * 2 = 6。factorial(4)得到了factorial(3)的结果6，所以它返回4 * 6 = 24。factorial(5)得到了factorial(4)的结果24，所以它返回5 * 24 = 120。
main方法中result的值就是120。
另一个例子：打印数字的倒序
public class ReverseNumber {
public static void printReverse(int number) {
// 基本情况：如果数字小于10，直接打印并返回
if (number < 10) {
System.out.print(number);
} else {
// 递归情况：
// 1. 打印除了最后一位以外的所有数字（通过递归实现）
System.out.print(number % 10); // 打印最后一位
printReverse(number / 10); // 将数字去掉最后一位，再次调用自己
}
}
public static void main(String[] args) {
int number = 12345;
System.out.print(number + " 的倒序是: ");
printReverse(number); // 输出: 54321
System.out.println();
}
}
递归的优缺点
优点：
- 代码简洁优雅：对于某些问题（如树的遍历、分治算法），递归的实现方式比循环更直观、更容易理解。
- 逻辑清晰：将问题分解为更小的子问题，符合人类的思维方式。
缺点：
- 性能开销：每次方法调用都会在调用栈上创建一个新的栈帧，这会消耗内存和时间，如果递归层次太深，很容易导致栈溢出错误。
- 难以调试：递归的调用流程比较复杂，当出现问题时，追踪错误可能比较困难。
- 重复计算：在简单的递归实现中，可能会存在大量的重复计算（例如斐波那契数列的朴素递归解法）。
何时使用递归？
递归并非万能药,它最适合解决那些 inherently recursive （天生具有递归性质）的问题，
- 数据结构操作：树的遍历（前序、中序、后序）、图的搜索（深度优先搜索DFS）。
- 分治算法：归并排序、快速排序。
- 数学问题：阶乘、斐波那契数列、汉诺塔问题。
对于其他可以用简单循环解决的问题,通常使用循环是更高效、更安全的选择。
