如何进一步优化带记忆化的递归斐波那契算法以提升运行速度？

嘿，我来帮你搞定这个斐波那契程序的效率问题！先瞅了眼你的代码，递归加数组缓存的思路没问题，但递归本身的栈帧开销在n到45左右时就开始拖后腿了——毕竟每一次递归调用都要创建栈帧、保存上下文，次数多了积少成多。下面给你几个实用的优化方案，按易实现到进阶的顺序来：

递归的最大问题就是栈开销和函数调用的额外消耗，换成从底往上的循环迭代，完全可以规避这些问题，而且还能优化空间。你甚至不需要整个缓存数组，只需要保存前两个值就行，空间复杂度直接降到O(1)。

给你改好的代码：

import java.util.Scanner;

public class Fibo {
    public static long fibo(int n) {
        // 对应你原来的n==0和n<2返回1的逻辑
        if (n <= 1) return 1;
        long prevPrev = 1; // 存储F(n-2)的值
        long prev = 1;     // 存储F(n-1)的值
        long current = 0;
        // 从第2项开始循环计算到第n项
        for (int i = 2; i <= n; i++) {
            current = prev + prevPrev;
            prevPrev = prev;
            prev = current;
        }
        return current;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = scanner.nextInt();
        System.out.println(fibo(n));
        scanner.close();
    }
}

这个版本跑45项完全是瞬间的事，就算n到几百上千也毫无压力，没有递归栈的拖累，每一步都是简单的算术操作，效率拉满。

你的递归代码里缓存的使用有小问题：比如你是先递归计算再存缓存，而不是先检查缓存是否已有值再计算，这会导致某些子问题被重复计算；另外缓存的索引用n-1容易搞混，比如n=0的时候根本没用到缓存。

改后的递归缓存版本：

import java.util.Scanner;

public class Fibo {
    static long[] cache;

    public static long fibo(int n) {
        // 先查缓存，有值直接返回，避免重复计算
        if (cache[n] != 0) {
            return cache[n];
        }
        // 基础情况直接赋值缓存并返回
        if (n == 0 || n == 1) {
            cache[n] = 1;
            return 1;
        }
        // 递归计算后存入缓存
        long result = fibo(n - 1) + fibo(n - 2);
        cache[n] = result;
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = scanner.nextInt();
        // 初始化缓存数组为n+1大小，刚好覆盖0到n的所有索引
        cache = new long[n + 1];
        System.out.println(fibo(n));
        scanner.close();
    }
}

这个版本修复了缓存的逻辑问题，重复计算的情况会减少，但递归的栈开销还是存在，n太大（比如超过1000）会出现栈溢出错误，所以只适合小范围的n。

如果你的场景需要计算非常大的n（比如几万甚至几十万），迭代循环的效率也会下降，这时候可以用矩阵快速幂，把时间复杂度降到O(logn)。原理是利用斐波那契数的矩阵表达，通过快速幂算法减少计算次数。

实现代码示例：

import java.util.Scanner;

public class FiboMatrix {
    // 矩阵乘法
    static long[][] multiply(long[][] a, long[][] b) {
        long[][] res = new long[2][2];
        res[0][0] = a[0][0] * b[0][0] + a[0][1] * b[1][0];
        res[0][1] = a[0][0] * b[0][1] + a[0][1] * b[1][1];
        res[1][0] = a[1][0] * b[0][0] + a[1][1] * b[1][0];
        res[1][1] = a[1][0] * b[0][1] + a[1][1] * b[1][1];
        return res;
    }

    // 矩阵快速幂
    static long[][] power(long[][] mat, int n) {
        // 初始化单位矩阵
        long[][] res = {{1, 0}, {0, 1}};
        while (n > 0) {
            // 如果n是奇数，先乘一次当前矩阵
            if (n % 2 == 1) {
                res = multiply(res, mat);
            }
            // 矩阵平方，n折半
            mat = multiply(mat, mat);
            n /= 2;
        }
        return res;
    }

    public static long fibo(int n) {
        if (n <= 1) return 1;
        // 斐波那契对应的变换矩阵
        long[][] mat = {{1, 1}, {1, 0}};
        long[][] powered = power(mat, n);
        // 对应你的F(n) = 标准斐波那契的F(n+1)，这里直接取矩阵幂的[0][0]即可
        return powered[0][0];
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("Enter n: ");
        int n = scanner.nextInt();
        System.out.println(fibo(n));
        scanner.close();
    }
}

这个版本就算计算n=1e6也只需要几十次矩阵乘法，速度非常快，但实现相对复杂，适合有超大n需求的场景。

内容的提问来源于stack exchange，提问作者Alex