遞歸常用來解決一些可拆分的，并且拆分到一定程度自然得到解的問題，最經(jīng)典的就是斐波那契數(shù)列（1，1，2，3，5......），從第三個數(shù)開始，每個數(shù)的值都為前面兩個數(shù)的和，如第五個數(shù)字等于第三個數(shù)字加上第四個數(shù)字的和，第N個等于第N-1個數(shù)字加上第N-2數(shù)字的和

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

代碼看起來很簡單，實際上效率很低，當(dāng)我們計算的數(shù)據(jù)很大的時候，比如第五十位數(shù)，會進(jìn)行非常多次的分解，如果將運(yùn)行的順序抽象為一張類似二叉樹的圖的話，就能清晰的看到這種直接遞歸的缺點

圖片.png

計算數(shù)列第五位數(shù)字的時候，運(yùn)行的步驟是這樣的，可以看到重復(fù)了兩次第三位的結(jié)果，隨著位數(shù)的增加，重復(fù)的計算也會急劇上升，我們可以通過一個數(shù)組或者集合來保存我們計算過的數(shù)據(jù)，遇到重復(fù)的計算的時候直接從集合中獲取

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];
}

這樣的話，我們的計算效率就會提高很多了