遞迴呼叫本身需要使用系統棧,每次分配函式記憶體以及棧都需要時間.不過這個過程耗時並不多,可以說,單純的遞迴本身並不比非遞迴慢多少.然而,實踐中就會發現,遞迴處理部分問題,特別是遞推類問題時會表現出效率極低.這個問題的出現是因為重複計算.舉例說,用遞迴求解斐波那契數列的第n項,一般的遞迴公式為f(n) = f(n-1)+f(n-2)f(2) = 1f(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].如此改進之後的遞迴函式效率上與遞推演算法相差無幾.
遞迴呼叫本身需要使用系統棧,每次分配函式記憶體以及棧都需要時間.不過這個過程耗時並不多,可以說,單純的遞迴本身並不比非遞迴慢多少.然而,實踐中就會發現,遞迴處理部分問題,特別是遞推類問題時會表現出效率極低.這個問題的出現是因為重複計算.舉例說,用遞迴求解斐波那契數列的第n項,一般的遞迴公式為f(n) = f(n-1)+f(n-2)f(2) = 1f(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].如此改進之後的遞迴函式效率上與遞推演算法相差無幾.