估計找工作的，都會碰到面試官老是問道“遞歸算法”，感同身受，前段時間面試的時候，就有一家問道這個問題，是非常典型的問題。在前面一篇世界上有哪些代碼量很少，但很牛逼很經典的算法或項目案例？，遞歸應該算是比較“經典”的算法。
波那契數列指的是這樣一個數列 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，后面每項的值都是前兩項值之和，所以我們很多人基本上都會使用遞歸來實現(xiàn)，常見的算法如下：
public int Fibo(int n)
{
if (n == 1 || n == 2)
{
return 1;
}
return Fibo(n - 2) + Fibo(n - 1);
}
但這種做法并不能完全解決問題，因為最大允許的遞歸深度跟當前線程剩余的?？臻g大小有關，事先無法計算。如果實時計算，代碼過于復雜，就會影響代碼的可讀性。所以，如果最大深度比較小，比如 10、50，就可以用這種方法，否則這種方法并不是很實用。
ps：遞歸代碼要警惕重復計算
除此之外，使用遞歸時還會出現(xiàn)重復計算的問題。剛才我講的第二個遞歸代碼的例子，如果我們把剛才我講的第二個遞歸代碼的例子，如果我們把整個遞歸過程分解一下的話，那就是這樣的：
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ā)現(xiàn)f(n)這個方法被調用了很多次，而且其中重復率非常之高，也就是說被重復計算了很多次，如果n稍微大一點這棵樹會非常龐大。這里我們可以看出，每個節(jié)點就需要計算一次，總計算的次數就是該二叉樹節(jié)點的數量，可見其時間復雜度為O(2n)，是指數級的，其空間復雜度也就是該二叉樹的高度，為O(n)。這樣來看，我們應該就清楚了，為什么這段代碼效率如此低下了吧。
我們應該避免無數次重復的計算
為了避免無數次重復，可以從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毫秒
盡管上述算法已經很高效了，但我們還是會發(fā)現(xiàn)一個問題，其實整個數組中，每次計算時都只需要最新的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，所以這種方法是非常高效的。
首先我們來了解一下什么是尾調用。
在計算機科學里，尾調用是指一個函數里的最后一個動作是一個函數調用的情形：即這個調用的返回值直接被當前函數返回的情形。這種情形下該調用位置為尾位置。
/// 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)雅了很多。
我們知道遞歸調用是通過棧來實現(xiàn)的，每調用一次函數，系統(tǒng)都將函數當前的變量、返回地址等信息保存為一個棧幀壓入到棧中，那么一旦要處理的運算很大或者數據很多，有可能會導致很多函數調用或者很大的棧幀，這樣不斷的壓棧，很容易導致棧的溢出。
還有一種優(yōu)化思路就是矩陣快速冪法，可參考鏈接https://blog.csdn.net/computer_user/article/details/86927209
