使用Memoization优化递归算法

空闲时在LeetCode上练练算法题，一般来说，很多题目最容易想到的就是递归算法。递归算法不仅容易想到和实现，而且写出来也是形式简单、容易理解的。

比如著名的“斐波那契数列”：

1,1,2,3,5,8...

数列的前两项都是1，后面的每一项都等于前两项之和，如何计算第n项？

用递归算法只需要如下两行代码

    public static int fibonacci(int n){
        if(n <= 2) return 1;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

调用这个方法，传入一个数字比如6，计算结果是8，看起来没问题。然而有一个很严重的缺陷，就是计算很慢，传入一个稍大的数字比如45，计算结果如下：

1134903170
time 2624

在我的CPU i7的电脑上需要耗时2624毫秒！
为什么这么简单的计算需要这么久？
因为递归中包含了大量的重复计算。
分析一下：计算n=45时，会计算n=44和n=43；计算n=44时，会计算n=43和n=42；计算n=43时，会计算n=42和n=41。可以看到，n<44时都会重复计算，n越小，重复计算的次数越多，最终导致计算次数指数级增长。

那么有什么方法优化吗？不能因为一个缺点就将递归算法否定啊。当然是有的，上面不是分析到n<44时都会重复计算吗？那么第一次计算完后将值记下来，下次要算的时候直接取不就行了？

    public static int fibonacci(int n){
        int[] memo = new int[n + 1];
        return fibonacci(n, memo);
    }
    
    public static int fibonacci(int n, int[] memo){
        if(n <= 2) return 1;
        if(memo[n] > 0) return memo[n];
        memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
        return memo[n];
    }

int[] memo数组就是用来保存计算结果的。这样优化后计算结果如下：

1134903170
time 0

可以看到，几乎不花时间了。因为原来的几百万次计算已经减少为几十次了，性能提升了几万倍。

这就是使用Memoization优化递归算法，通俗地说就是给递归增加记忆，本质上是用空间换时间。这么做是十分有必要的，大部分题用递归算法解都很容易遇到TLE(Time Limit Exceeded)，即超出时间限制。而经过Memoization优化后，一般都会AC(Accepted)通过，甚至达到与DP(Dynamic Programming)等优秀的算法相同的性能。