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

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 越大，這段代碼執行效率越低通過測試一下看他的效率如何

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(n)這個方法被調用了很多次，而且其中重復率非常之高，也就是說被重復計算了很多次，如果n稍微大一點這棵樹會非常龐大。這里我們可以看出，每個節點就需要計算一次，總計算的次數就是該二叉樹節點的數量，可見其時間復雜度為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.滾動數組法

盡管上述算法已經很高效了，但我們還是會發現一個問題，其實整個數組中，每次計算時都只需要最新的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值變化逐步重復運算，和循環差不多，時間復雜度和空間復雜度也都一樣,優雅了很多。

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

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

回復?【關閉】學關閉微信朋友圈廣告

回復?【實戰】獲取20套實戰源碼

回復?【福利】獲取最新微信支付有獎勵

回復?【被刪】學查看你哪個好友刪除了你巧

回復?【訪客】學微信查看朋友圈訪客記錄

回復?【卡通】學制作微信卡通頭像

回復?【python】學微獲取全套0基礎Python知識手冊

回復?【2019】獲取2019 .NET 開發者峰會資料PPT

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

VS Code 1.47 發布！官方版 Settings Sync 終于來了！

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

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

總結

以上是生活随笔為你收集整理的递归优化的这三种方式你知道吗？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。