递归通过方法调用自身解决自相似问题，需包含基准条件和递归调用，常用于阶乘、斐波那契、GCD等计算；为避免性能问题，可采用记忆化、尾递归优化或迭代替代。
递归是一种方法调用自身的技术，在处理具有自相似结构的数学问题时非常有效。Java中的递归方法常用于求解阶乘、斐波那契数列、汉诺塔等问题。掌握正确的使用方式和优化技巧，能帮助你写出更清晰且高效的代码。
理解递归的基本结构
每个有效的递归方法都必须包含两个核心部分：基准条件（终止条件）和递归调用。
-
基准条件：防止无限递归，是问题可以直接求解的情况。例如，0的阶乘
是1。
-
递归调用：将问题分解为更小的子问题，并调用自身来解决。
以计算阶乘为例：
public static int factorial(int n) {
if (n == 0 || n == 1) {
return 1; // 基准条件
}
return n * factorial(n - 1); // 递归调用
}
经典数学问题的递归实现
以下是一些常见数学问题的递归解法：
-
斐波那契数列：F(n) = F(n-1) + F(n-2)，其中 F(0)=0，F(1)=1。
-
最大公约数（GCD）：利用欧几里得算法，gcd(a, b) = gcd(b, a % b)。
-
幂运算：快速幂可以通过递归实现，如 pow(x, n) = pow(x, n/2) * pow(x, n/2)（n为偶数时）。
示例：计算两个数的最大公约数
public static int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
递归优化与注意事项
虽然递归代码简洁，但容易引发性能问题或栈溢出。以下是几个实用技巧：
-
避免重复计算：像斐波那契递归中，同一子问题会被多次调用。可使用“记忆化”技术缓存结果。
-
考虑尾递归优化：如果递归调用是方法的最后一行操作，某些语言会优化为循环。Java不自动支持，但可手动改写为循环提升效率。
-
控制递归深度：输入过大可能导致 StackOverflowError。必要时改用迭代或增加JVM栈大小。
记忆化斐波那契示例：
private static Map memo = new HashMap();
public static int fib(int n) {
if (n
if (memo.containsKey(n)) return memo.get(n);
int result = fib(n - 1) + fib(n - 2);
memo.put(n, result);
return result;
}
何时使用递归
递归适合结构天然分治的问题，比如树遍历、组合枚举、分形计算等。对于简单线性问题（如累加），通常迭代更高效。
- 优点：逻辑清晰，贴近数学定义。
- 缺点：空间开销大，可能重复计算。
建议先用递归理清思路，再根据性能需求决定是否优化为迭代。
基本上就这些。写递归时先想清楚终止条件，再设计如何缩小问题规模。多练习典型题目，自然就能掌握这种思维方式。不复杂但容易忽略细节。
