一般遞歸算法比非遞歸算法慢嗎？

遞歸調(diào)用本身需要使用系統(tǒng)棧,每次分配函數(shù)內(nèi)存以及棧都需要時間.不過這個過程耗時并不多,可以說,單純的遞歸本身并不比非遞歸慢多少.

然而,實踐中就會發(fā)現(xiàn),遞歸處理部分問題,特別是遞推類問題時會表現(xiàn)出效率極低.這個問題的出現(xiàn)是因為重復(fù)計算.

舉例說,用遞歸求解斐波那契數(shù)列的第n項,一般的遞歸公式為

f(n) = f(n-1)+f(n-2)

f(2) = 1

f(1) = 1

請嘗試模擬計算機運行這個遞歸,你會發(fā)現(xiàn),其中的某一項f(x)并不是只算了一次.當(dāng)你計算f(5)的時候,你會試圖計算f(4)和f(3),然而在你計算f(4)的時候其實也要計算f(3),這樣f(3)就被調(diào)用了兩次.

想象這個過程是指數(shù)型擴展的,效率會隨著n的增大極快地下降.

要解決這個問題,可以使用記憶化思想.

定義記憶數(shù)組r,函數(shù)體改為:

define f(n):

if r[n] is defined, then simply return r[n] as the answer.

else, f(n) = f(n-1) + f(n-2)

before return the value, take it down in r[n].

如此改進之后的遞歸函數(shù)效率上與遞推算法相差無幾