递归实现斐波那契数列效率极低，如何优化？求问题排查与提速方法

问题根源：指数级的重复计算 #

你的Fib方法用了朴素递归实现，这会导致大量的重复计算，是性能爆炸的核心原因。举个简单例子：

• 计算Fib(5)时，需要先算Fib(4)和Fib(3)
• 计算Fib(4)时，又要算Fib(3)和Fib(2)
• 这里Fib(3)就被重复计算了两次，随着n增大，重复计算的次数会呈指数级增长（时间复杂度为O(2ⁿ)）。当n>55时，需要计算的子问题数量会多到让程序几乎停滞，完全无法在合理时间内给出结果。

另外提个小细节：你代码里的n == 1 | n == 2用了按位或|，逻辑上应该改成逻辑或||——虽然这里结果没错，但逻辑或更符合语义，还能短路优化（比如n=1时就不会再判断n=2了）。

解决方案：避免重复计算 #

下面是几种优化方案，按实现成本和实用性排序：

1. 迭代法（最推荐，简单高效） #

用循环迭代的方式，只保留前两个斐波那契值，逐步计算到第n项。时间复杂度O(n)，空间复杂度O(1)，完全解决重复计算问题：

private static long Fib(long n) {
    if (n <= 0) {
        System.out.println("Error");
        return 0;
    } else if (n == 1 || n == 2) {
        return 1;
    }
    long prevPrev = 1; // 代表Fib(1)
    long prev = 1;     // 代表Fib(2)
    long current = 0;
    for (long i = 3; i <= n; i++) {
        current = prevPrev + prev;
        prevPrev = prev;
        prev = current;
    }
    return current;
}

2. 记忆化递归（缓存已计算结果） #

通过一个缓存容器（数组或HashMap）存储已经算出的斐波那契值，遇到重复子问题直接取缓存，避免重复计算。时间复杂度O(n)，空间复杂度O(n)：

// 用数组缓存结果，可根据实际需求调整数组大小
private static long[] memo = new long[1001];

private static long Fib(long n) {
    if (n <= 0) {
        System.out.println("Error");
        return 0;
    } else if (n == 1 || n == 2) {
        return 1;
    }
    // 缓存已有结果，直接返回
    if (memo[(int)n] != 0) {
        return memo[(int)n];
    }
    // 计算并缓存结果
    memo[(int)n] = Fib(n-1) + Fib(n-2);
    return memo[(int)n];
}

3. 矩阵快速幂（适合超大n场景） #

如果需要计算非常大的n（比如n>10000），可以用矩阵快速幂将时间复杂度降到O(logn)，但实现稍复杂：

private static long Fib(long n) {
    if (n <= 0) {
        System.out.println("Error");
        return 0;
    } else if (n == 1 || n == 2) {
        return 1;
    }
    // 矩阵乘法工具方法
    long[][] multiply(long[][] m1, long[][] m2) {
        return new long[][]{
            {m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0], m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1]},
            {m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0], m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1]}
        };
    }
    // 矩阵快速幂方法
    long[][] matrixPower(long[][] m, long power) {
        long[][] result = {{1,0},{0,1}}; // 单位矩阵
        while (power > 0) {
            if (power % 2 == 1) {
                result = multiply(result, m);
            }
            m = multiply(m, m);
            power /= 2;
        }
        return result;
    }
    long[][] base = {{1,1},{1,0}};
    long[][] powered = matrixPower(base, n-2);
    return powered[0][0] * 1 + powered[0][1] * 1; // Fib(n) = 1*Fib(2) + 1*Fib(1)
}

额外小优化 #

你的主循环是无限循环，可以加个退出条件，比如输入0时结束程序，提升体验：

for (; ; ) { 
    System.out.println("Enter n to get Fibonacci value (input 0 to exit): "); 
    Scanner numer = new Scanner(System.in); 
    long n = numer.nextLong();
    if (n == 0) {
        System.out.println("Exiting...");
        break;
    }
    long result = Fib(n); 
    System.out.println("Result: " + result); 
} 

内容的提问来源于stack exchange，提问作者Bartek Węgrzyn