遞歸在解決某些問題的時候使得我們思考的方式得以簡化，代碼也更加精煉，容易閱讀。那么既然遞歸有這么多的優(yōu)點，我們是不是什么問題都要用遞歸來解決呢？難道遞歸就沒有缺點嗎？今天我們就來討論一下遞歸的不足之處。談到遞歸就不得不面對它的效率問題。
為什么遞歸是低效的
還是拿斐波那契（Fibonacci）數(shù)列來做例子。在很多教科書或文章中涉及到遞歸或計算復雜性的地方都會將計算斐波那契數(shù)列的程序作為經(jīng)典示例。如果現(xiàn)在讓你以最快的速度用C#寫出一個計算斐波那契數(shù)列第n個數(shù)的函數(shù)（不考慮參數(shù)小于1或結果溢出等異常情況），我不知你的程序是否會和下列代碼類似：
1 | public static ulong Fib(ulong n) |
3 | return (n == 1 || n == 2) ? 1 : Fib(n - 1) + Fib(n - 2); |
這段代碼應該算是短小精悍（執(zhí)行代碼只有一行），直觀清晰，而且非常符合許多程序員的代碼美學，許多人在面試時寫出這樣的代碼可能心里還會暗爽。但是如果用這段代碼試試計算Fib(1000)我想就再也爽不起來了，它的運行時間也許會讓你抓狂。
看來好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮云了。如果簡單分析一下程序的執(zhí)行流，就會發(fā)現(xiàn)問題在哪，以計算Fibonacci(5)為例：
從上圖可以看出，在計算Fib(5)的過程中，F(xiàn)ib(1)計算了兩次、Fib(2)計算了3次，F(xiàn)ib(3)計算了兩次，本來只需要5次計算就可以完成的任務卻計算了9次。這個問題隨著規(guī)模的增加會愈發(fā)凸顯，以至于Fib(1000)已經(jīng)無法再可接受的時間內(nèi)算出。
我們當時使用的是簡單的用定義來求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。這樣的想法是很容易想到的，可是仔細分析一下我們發(fā)現(xiàn)，當調(diào)用fib(n-1)的時候，還要調(diào)用fib(n-2)，也就是說fib(n-2)調(diào)用了兩次，同樣的道理，調(diào)用f(n-2)時f(n-3)也調(diào)用了兩次，而這些冗余的調(diào)用是完全沒有必要的?？梢杂嬎氵@個算法的復雜度是指數(shù)級的。
改進的斐波那契遞歸算法
那么計算斐波那契數(shù)列是否有更好的遞歸算法呢？ 當然有。讓我們來觀察一下斐波那契數(shù)列的前幾項：
1 | 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 … |
注意到?jīng)]有，如果我們?nèi)サ羟懊嬉豁?，得到的?shù)列依然滿足f(n) = f(n-1) – f(n-2), (n>2)，而我們得到的數(shù)列是以1，2開頭的。很容易發(fā)現(xiàn)這個數(shù)列的第n-1項就是原數(shù)列的第n項。怎么樣，知道我們該怎么設計算法了吧？我們可以寫這樣的一個函數(shù)，它接受三個參數(shù)，前兩個是數(shù)列的開頭兩項，第三個是我們想求的以前兩個參數(shù)開頭的數(shù)列的第幾項。
1 | int fib_i(int a, int b, int n); |
在函數(shù)內(nèi)部我們先檢查n的值，如果n為3則我們只需返回a+b即可，這是簡單情境。如果n>3，那么我們就調(diào)用f(b, a+b, n-1)，這樣我們就縮小了問題的規(guī)模（從求第n項變成求第n-1項）。好了，最終代碼如下：
1 | int fib_i(int a, int b , int n) |
6 | return fib_i(b, a+b, n-1); |
這樣得到的算法復雜度是O(n)的。已經(jīng)是線性的了。它的效率已經(jīng)可以與迭代算法的效率相比了，但由于還是要反復的進行函數(shù)調(diào)用，還是不夠經(jīng)濟。
遞歸與迭代的效率比較
我們知道，遞歸調(diào)用實際上是函數(shù)自己在調(diào)用自己，而函數(shù)的調(diào)用開銷是很大的，系統(tǒng)要為每次函數(shù)調(diào)用分配存儲空間，并將調(diào)用點壓棧予以記錄。而在函數(shù)調(diào)用結束后，還要釋放空間，彈?；謴蛿帱c。所以說，函數(shù)調(diào)用不僅浪費空間，還浪費時間。
這樣，我們發(fā)現(xiàn)，同一個問題，如果遞歸解決方案的復雜度不明顯優(yōu)于其它解決方案的話，那么使用遞歸是不劃算的。因為它的很多時間浪費在對函數(shù)調(diào)用的處理上。在C++中引入了內(nèi)聯(lián)函數(shù)的概念，其實就是為了避免簡單函數(shù)內(nèi)部語句的執(zhí)行時間小于函數(shù)調(diào)用的時間而造成效率降低的情況出現(xiàn)。在這里也是一個道理，如果過多的時間用于了函數(shù)調(diào)用的處理，那么效率顯然高不起來。
舉例來說，對于求階乘的函數(shù)來說，其迭代算法的時間復雜度為O(n)：
05 | for(i = 1; i < = n; i++) |
而其遞歸函數(shù)的時間復雜度也是O(n)：
但是遞歸算法要進行n次函數(shù)調(diào)用，而迭代算法則只需要進行n次迭代而已。其效率上的差異是很顯著的。
小結
由以上分析我們可以看到，遞歸在處理問題時要反復調(diào)用函數(shù)，這增大了它的空間和時間開銷，所以在使用迭代可以很容易解決的問題中，使用遞歸雖然可以簡化思維過程，但效率上并不合算。效率和開銷問題是遞歸最大的缺點。
雖然有這樣的缺點，但是遞歸的力量仍然是巨大而不可忽視的，因為有些問題使用迭代算法是很難甚至無法解決的（比如漢諾塔問題）。這時遞歸的作用就顯示出來了。
遞歸的效率問題暫時討論到這里。后面會介紹到遞歸計算過程與迭代計算過程，講解得更詳細點。
