Java里的递归算法怎么写_阶乘计算与斐峰那切数列实战-java教程-PHP中文网

递归函数必须有明确终止条件，如阶乘需处理n==0和n==1，负数要提前拦截；斐波那契直接递归时间复杂度为o(2^n)，应改用记忆化或迭代。

java里的递归算法怎么写_阶乘计算与斐峰那切数列实战

递归函数必须有明确的终止条件

写错递归最常见的情况，就是忘了 return 或者终止条件写成 n == 1 却没处理 n == 0。比如阶乘：如果只写 if (n == 1) return 1;，那传入 0 就会无限调用 factorial(-1)、factorial(-2)…直到栈溢出报 StackOverflowError。

实际写法要覆盖边界值：

public static int factorial(int n) {
    if (n

负数输入必须提前拦截，否则递归无法收敛
n == 0 和 n == 1 建议合并判断，避免逻辑缝隙
Java 没有尾递归优化，深度太大（比如 n > 10000）仍会爆栈

斐波那契递归别直接照公式硬搬

看到 F(n) = F(n-1) + F(n-2) 就写两行递归？那算 fibonacci(40) 会卡住——因为重复计算爆炸式增长，时间复杂度是 O(2^n)，不是线性。

原始写法（不推荐）：

Java Maven Common

Java Maven 项目审查工作流的通用输入处理。当 Java Maven 项目以 ZIP压缩包或 GitLab 仓库 URL 形式提供且需要...时使用。

下载

public static int fibonacci(int n) {
    if (n

算 fibonacci(5) 时，fibonacci(3) 被算 2 次，fibonacci(2) 被算 3 次
到 n == 45 左右，耗时就明显可感知；n == 50 可能要几秒
这不是“递归写错了”，而是没考虑子问题重叠——该上记忆化或换迭代

用 HashMap 做记忆化递归要小心 key 类型和并发

加个缓存就能把斐波那契从指数级拉回 O(n)，但 Java 里用 HashMap 存 Integer 键要注意自动装箱陷阱。

正确写法示例：

private static final Map<integer integer> cache = new HashMap();
static {
    cache.put(0, 0);
    cache.put(1, 1);
}
public static int fibonacci(int n) {
    if (n  fibonacci(k - 1) + fibonacci(k - 2));
}</integer>