遞歸算法的速度會特別慢的原因是什麽？

遞歸調用本身需要使用系統棧,每次分配函數內存以及棧都需要時間.不過這個過程耗時並不多,可以說,單純的遞歸本身並不比非遞歸慢多少.

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

舉例說,用遞歸求解斐波那契數列的第n項,壹般的遞歸公式為

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

f(2) = 1

f(1) = 1

請嘗試模擬計算機運行這個遞歸,妳會發現,其中的某壹項f(x)並不是只算了壹次.當妳計算f(5)的時候,妳會試圖計算f(4)和f(3),然而在妳計算f(4)的時候其實也要計算f(3),這樣f(3)就被調用了兩次.

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

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

定義記憶數組r,函數體改為:

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].

如此改進之後的遞歸函數效率上與遞推算法相差無幾.

上一篇:如何做壹個問卷調查小程序

下一篇:給出壹個矩陣（二維數組），通過編程計算壹下矩陣上三角元素的和，要求元素的值由鍵盤輸入。