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

1.從 斐波那契數列開始說起

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

遞推公式如圖：

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

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，后面每項的值都是前兩項值之和，所以我們很多人基本上都會使用遞歸來實現，常見的算法如下：

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

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

ps：遞歸代碼要警惕重復計算

除此之外，使用遞歸時還會出現重復計算的問題。剛才我講的第二個遞歸代碼的例子，如果我們把剛才我講的第二個遞歸代碼的例子，如果我們把整個遞歸過程分解一下的話，那就是這樣的：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再稍微大一點，所消耗的時間是成指數級增長的，比如n=64的時候，所消耗的時間可能是兩三年！不信的話，你可以試試！

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

2.數組保存法

我們應該避免無數次重復的計算

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

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

測試一下結果

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

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

3.滾動數組法

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

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

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

3.尾遞歸法

首先我們來了解一下什么是尾調用。

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

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

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

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

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

winform已死？這8個Winform開源項目還有多少人在用？

VS Code 1.47 發(fā)布！官方版 Settings Sync 終于來了！

張善友：最新.NET程序員省份分布排名

Pandownload關閉了，百度網盤真的提速高達10Mb/s?