遞歸優(yōu)化的這三種方式你知道嗎？

估計找工作的，都會碰到面試官老是問道“遞歸算法”，感同身受，前段時間面試的時候，就有一家問道這個問題，是非常典型的問題。在前面一篇世界上有哪些代碼量很少，但很牛逼很經(jīng)典的算法或項目案例？，遞歸應(yīng)該算是比較“經(jīng)典”的算法。

1.從 斐波那契數(shù)列開始說起

波那契數(shù)列指的是這樣一個數(shù)列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144，是指這樣一個數(shù)列

遞推公式如圖：

有沒有直接計算的公式？當然有

public int Fibo(int n)
{
    double c = Math.Sqrt(5);
    return (int)((Math.Pow((1 + c) / 2, n) - Math.Pow((1 - c) / 2, n)) / c);
}

1.最常見的遞歸

第一項和第二項的值均為1，后面每項的值都是前兩項值之和，所以我們很多人基本上都會使用遞歸來實現(xiàn)，常見的算法如下：

        public int Fibo(int n)
        {
           if (n == 1 || n == 2)
           {
                return 1;
           }
           return Fibo(n - 2) + Fibo(n - 1);
        }

但這種做法并不能完全解決問題，因為最大允許的遞歸深度跟當前線程剩余的?？臻g大小有關(guān)，事先無法計算。如果實時計算，代碼過于復(fù)雜，就會影響代碼的可讀性。所以，如果最大深度比較小，比如 10、50，就可以用這種方法，否則這種方法并不是很實用。

ps：遞歸代碼要警惕重復(fù)計算

除此之外，使用遞歸時還會出現(xiàn)重復(fù)計算的問題。剛才我講的第二個遞歸代碼的例子，如果我們把剛才我講的第二個遞歸代碼的例子，如果我們把整個遞歸過程分解一下的話，那就是這樣的：n 越大，這段代碼執(zhí)行效率越低通過測試一下看他的效率如何

            Stopwatch sw = new Stopwatch();
            sw.Start();
            var result = Fibo(40);
            sw.Stop();
            Debug.WriteLine("n=100；result="+result+"；耗時："+sw.ElapsedMilliseconds);

n=10；result=55；耗時：2715
n=40；result=102334155；耗時：4673

如果n再稍微大一點，所消耗的時間是成指數(shù)級增長的，比如n=64的時候，所消耗的時間可能是兩三年！不信的話，你可以試試！

我們會發(fā)現(xiàn)f(n)這個方法被調(diào)用了很多次，而且其中重復(fù)率非常之高，也就是說被重復(fù)計算了很多次，如果n稍微大一點這棵樹會非常龐大。這里我們可以看出，每個節(jié)點就需要計算一次，總計算的次數(shù)就是該二叉樹節(jié)點的數(shù)量，可見其時間復(fù)雜度為O(2n)，是指數(shù)級的，其空間復(fù)雜度也就是該二叉樹的高度，為O(n)。這樣來看，我們應(yīng)該就清楚了，為什么這段代碼效率如此低下了吧。

2.數(shù)組保存法

我們應(yīng)該避免無數(shù)次重復(fù)的計算

為了避免無數(shù)次重復(fù)，可以從n=1開始往上計算，并把每一個計算出來的數(shù)據(jù)，用一個數(shù)組保存，需要最終值時直接從數(shù)組中取即可，算法如下：

public int fib(int n) {
    int[] fib = new int[n];
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < n; i++) {
        fib[i] = fib[i - 2] + fib[i - 1];
    }
    return fib[n - 1];
}

測試一下結(jié)果

n=10；result=55；耗時：0
n=40；result=102334155；耗時：0
n=1000000；result=1884755131；耗時：5

毫秒級，幾乎忽略不計的，當計算100萬時，也就5毫秒

3.滾動數(shù)組法

盡管上述算法已經(jīng)很高效了，但我們還是會發(fā)現(xiàn)一個問題，其實整個數(shù)組中，每次計算時都只需要最新的3個值，前面的值計算完后就不再需要了。比如，計算到第10次時，需要的數(shù)組空間只有第8和第9兩個空間，前面第1到第7個空間其實就不再需要了。所以我們還可以改進，通過3個變量來存儲數(shù)據(jù)，算法如下：

        public int Fibo3(int n)
        {
            int first = 1;
            int second = 1;
            int third = 2;
            for (int i = 3; i <= n; i++)
            {
                third = first + second;
                first = second;
                second = third;
            }
            return third;
        }

時間復(fù)雜度仍然為O(n)，而空間復(fù)雜度為常量級別3，即空間復(fù)雜度為0，所以這種方法是非常高效的。

3.尾遞歸法

首先我們來了解一下什么是尾調(diào)用。

在計算機科學(xué)里，尾調(diào)用是指一個函數(shù)里的最后一個動作是一個函數(shù)調(diào)用的情形：即這個調(diào)用的返回值直接被當前函數(shù)返回的情形。這種情形下該調(diào)用位置為尾位置。

 /// n 第n個數(shù)
 /// first 第n個數(shù)
 /// second 第n與第n+1個數(shù)的和
 /// @return 返回斐波那契數(shù)列值
public int Fib5(int n, int first, int second) {
    if (n <= 1) {
        return first;
    } else {
        return fib5(n-1,second,first+second);
    }
}

，也都是通過兩個變量保存計算值，傳遞給下一次進行計算，遞歸的過程中也是根據(jù)n值變化逐步重復(fù)運算，和循環(huán)差不多，時間復(fù)雜度和空間復(fù)雜度也都一樣,優(yōu)雅了很多。

我們知道遞歸調(diào)用是通過棧來實現(xiàn)的，每調(diào)用一次函數(shù)，系統(tǒng)都將函數(shù)當前的變量、返回地址等信息保存為一個棧幀壓入到棧中，那么一旦要處理的運算很大或者數(shù)據(jù)很多，有可能會導(dǎo)致很多函數(shù)調(diào)用或者很大的棧幀，這樣不斷的壓棧，很容易導(dǎo)致棧的溢出。

還有一種優(yōu)化思路就是矩陣快速冪法，可參考鏈接 https://blog.csdn.net/computer_user/article/details/86927209