遞歸在解決某些問(wèn)題的時(shí)候使得我們思考的方式得以簡(jiǎn)化，代碼也更加精煉，容易閱讀。那么既然遞歸有這么多的優(yōu)點(diǎn)，我們是不是什么問(wèn)題都要用遞歸來(lái)解決呢？難道遞歸就沒(méi)有缺點(diǎn)嗎？今天我們就來(lái)討論一下遞歸的不足之處。談到遞歸就不得不面對(duì)它的效率問(wèn)題。

為什么遞歸是低效的

還是拿斐波那契（Fibonacci）數(shù)列來(lái)做例子。在很多教科書(shū)或文章中涉及到遞歸或計(jì)算復(fù)雜性的地方都會(huì)將計(jì)算斐波那契數(shù)列的程序作為經(jīng)典示例。如果現(xiàn)在讓你以最快的速度用C#寫(xiě)出一個(gè)計(jì)算斐波那契數(shù)列第n個(gè)數(shù)的函數(shù)（不考慮參數(shù)小于1或結(jié)果溢出等異常情況），我不知你的程序是否會(huì)和下列代碼類似：

這段代碼應(yīng)該算是短小精悍（執(zhí)行代碼只有一行），直觀清晰，而且非常符合許多程序員的代碼美學(xué)，許多人在面試時(shí)寫(xiě)出這樣的代碼可能心里還會(huì)暗爽。但是如果用這段代碼試試計(jì)算Fib(1000)我想就再也爽不起來(lái)了，它的運(yùn)行時(shí)間也許會(huì)讓你抓狂。

看來(lái)好看的代碼未必中用，如果程序在效率不能接受那美觀神馬的就都是浮云了。如果簡(jiǎn)單分析一下程序的執(zhí)行流，就會(huì)發(fā)現(xiàn)問(wèn)題在哪，以計(jì)算Fibonacci(5)為例：

從上圖可以看出，在計(jì)算Fib(5)的過(guò)程中，F(xiàn)ib(1)計(jì)算了兩次、Fib(2)計(jì)算了3次，F(xiàn)ib(3)計(jì)算了兩次，本來(lái)只需要5次計(jì)算就可以完成的任務(wù)卻計(jì)算了9次。這個(gè)問(wèn)題隨著規(guī)模的增加會(huì)愈發(fā)凸顯，以至于Fib(1000)已經(jīng)無(wú)法再可接受的時(shí)間內(nèi)算出。

我們當(dāng)時(shí)使用的是簡(jiǎn)單的用定義來(lái)求 fib(n)，也就是使用公式 fib(n) = fib(n-1) + fib(n-2)。這樣的想法是很容易想到的，可是仔細(xì)分析一下我們發(fā)現(xiàn)，當(dāng)調(diào)用fib(n-1)的時(shí)候，還要調(diào)用fib(n-2)，也就是說(shuō)fib(n-2)調(diào)用了兩次，同樣的道理，調(diào)用f(n-2)時(shí)f(n-3)也調(diào)用了兩次，而這些冗余的調(diào)用是完全沒(méi)有必要的?？梢杂?jì)算這個(gè)算法的復(fù)雜度是指數(shù)級(jí)的。

改進(jìn)的斐波那契遞歸算法

那么計(jì)算斐波那契數(shù)列是否有更好的遞歸算法呢？ 當(dāng)然有。讓我們來(lái)觀察一下斐波那契數(shù)列的前幾項(xiàng)：

注意到?jīng)]有，如果我們?nèi)サ羟懊嬉豁?xiàng)，得到的數(shù)列依然滿足f(n) = f(n-1) – f(n-2), (n>2)，而我們得到的數(shù)列是以1，2開(kāi)頭的。很容易發(fā)現(xiàn)這個(gè)數(shù)列的第n-1項(xiàng)就是原數(shù)列的第n項(xiàng)。怎么樣，知道我們?cè)撛趺丛O(shè)計(jì)算法了吧？我們可以寫(xiě)這樣的一個(gè)函數(shù)，它接受三個(gè)參數(shù)，前兩個(gè)是數(shù)列的開(kāi)頭兩項(xiàng)，第三個(gè)是我們想求的以前兩個(gè)參數(shù)開(kāi)頭的數(shù)列的第幾項(xiàng)。

在函數(shù)內(nèi)部我們先檢查n的值，如果n為3則我們只需返回a+b即可，這是簡(jiǎn)單情境。如果n>3，那么我們就調(diào)用f(b, a+b, n-1)，這樣我們就縮小了問(wèn)題的規(guī)模（從求第n項(xiàng)變成求第n-1項(xiàng)）。好了，最終代碼如下：

這樣得到的算法復(fù)雜度是O(n)的。已經(jīng)是線性的了。它的效率已經(jīng)可以與迭代算法的效率相比了，但由于還是要反復(fù)的進(jìn)行函數(shù)調(diào)用，還是不夠經(jīng)濟(jì)。

遞歸與迭代的效率比較

我們知道，遞歸調(diào)用實(shí)際上是函數(shù)自己在調(diào)用自己，而函數(shù)的調(diào)用開(kāi)銷是很大的，系統(tǒng)要為每次函數(shù)調(diào)用分配存儲(chǔ)空間，并將調(diào)用點(diǎn)壓棧予以記錄。而在函數(shù)調(diào)用結(jié)束后，還要釋放空間，彈?；謴?fù)斷點(diǎn)。所以說(shuō)，函數(shù)調(diào)用不僅浪費(fèi)空間，還浪費(fèi)時(shí)間。

這樣，我們發(fā)現(xiàn)，同一個(gè)問(wèn)題，如果遞歸解決方案的復(fù)雜度不明顯優(yōu)于其它解決方案的話，那么使用遞歸是不劃算的。因?yàn)樗暮芏鄷r(shí)間浪費(fèi)在對(duì)函數(shù)調(diào)用的處理上。在C++中引入了內(nèi)聯(lián)函數(shù)的概念，其實(shí)就是為了避免簡(jiǎn)單函數(shù)內(nèi)部語(yǔ)句的執(zhí)行時(shí)間小于函數(shù)調(diào)用的時(shí)間而造成效率降低的情況出現(xiàn)。在這里也是一個(gè)道理，如果過(guò)多的時(shí)間用于了函數(shù)調(diào)用的處理，那么效率顯然高不起來(lái)。

舉例來(lái)說(shuō)，對(duì)于求階乘的函數(shù)來(lái)說(shuō)，其迭代算法的時(shí)間復(fù)雜度為O(n)：

而其遞歸函數(shù)的時(shí)間復(fù)雜度也是O(n)：

但是遞歸算法要進(jìn)行n次函數(shù)調(diào)用，而迭代算法則只需要進(jìn)行n次迭代而已。其效率上的差異是很顯著的。

小結(jié)

由以上分析我們可以看到，遞歸在處理問(wèn)題時(shí)要反復(fù)調(diào)用函數(shù)，這增大了它的空間和時(shí)間開(kāi)銷，所以在使用迭代可以很容易解決的問(wèn)題中，使用遞歸雖然可以簡(jiǎn)化思維過(guò)程，但效率上并不合算。效率和開(kāi)銷問(wèn)題是遞歸最大的缺點(diǎn)。

雖然有這樣的缺點(diǎn)，但是遞歸的力量仍然是巨大而不可忽視的，因?yàn)橛行﹩?wèn)題使用迭代算法是很難甚至無(wú)法解決的（比如漢諾塔問(wèn)題）。這時(shí)遞歸的作用就顯示出來(lái)了。

遞歸的效率問(wèn)題暫時(shí)討論到這里。后面會(huì)介紹到遞歸計(jì)算過(guò)程與迭代計(jì)算過(guò)程，講解得更詳細(xì)點(diǎn)。