记忆化递归算法

递归常用来解决一些可拆分的，并且拆分到一定程度自然得到解的问题，最经典的就是斐波那契数列（1，1，2，3，5......），从第三个数开始，每个数的值都为前面两个数的和，如第五个数字等于第三个数字加上第四个数字的和，第N个等于第N-1个数字加上第N-2数字的和

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

代码看起来很简单，实际上效率很低，当我们计算的数据很大的时候，比如第五十位数，会进行非常多次的分解，如果将运行的顺序抽象为一张类似二叉树的图的话，就能清晰的看到这种直接递归的缺点

图片.png

计算数列第五位数字的时候，运行的步骤是这样的，可以看到重复了两次第三位的结果，随着位数的增加，重复的计算也会急剧上升，我们可以通过一个数组或者集合来保存我们计算过的数据，遇到重复的计算的时候直接从集合中获取

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 (memo[n]>0){
        return memo[n];
    }
    if (n==1){
        return 1;
    }
    else if (n==2){
        return 1;
    }else {
        memo[n]=Fibonacci(n-1,memo)+Fibonacci(n-2,memo);
    }
    return memo[n];
}

这样的话，我们的计算效率就会提高很多了