如何通過超前檢測邊界的情況下減少遞歸次

例如，在教科書的代碼 - 用遞歸解決問題的斐波那契 - 是這樣的：如何通過超前檢測邊界的情況下減少遞歸次

cache = {} 

def fibo(n): 
    if n in cache : 
     return cache[n] 
    elif n <=2: 
     cache[n] = 1 
    else: 
     cache[n] = fibo(n-1) + fibo(n-2) 
    return cache[n]

然而，我所關注的，每次做函數調用，需要成本。爲什麼沒有教科書使用此代碼代替，以避免不必要的函數調用：

cache = {} 

def fibo(n): 
    if n <=2: 
     cache[n] = 1 
    else: 
     # to avoid unnecessary function call 
     if n-1 in cache: 
      f1 = cache[n-1] 
     else: 
      f1 = fibo(n-1) 
     if n-2 in cache: 
      f2 = cache[n-2] 
     else: 
      f2 = fibo(n-2) 

     cache[n] = f1 + f2 

    return cache[n]

通過這種方式，我們能夠避免實際調用之前不必要的函數調用。

無論如何，我的問題是，爲什麼教科書的作者不以第二種方式編寫代碼？

來源

2012-08-04 user1481096

你意識到你沒有使用'f1'和'f2'，所以你正在做更多不必要的函數調用，對吧？ – murgatroid99 2012-08-04 00:16:49

我想說他們通常會試圖展示一個概念 - 通常是遞歸。優化遞歸函數可能會稍後。 – ernie 2012-08-04 00:18:36

由於代碼示例應該優先於（過早）微優化的可讀性。這與他們沒有用局部變量替換全局查找的原因是一樣的。 – Antimony 2012-08-04 00:26:45

你所描述的是dynamic programming。您正在使用數組來存儲遞歸步驟，ala memoization。對於像Fibonacci這樣的每次迭代都有多次遞歸調用的人來說，動態編程確實是首選技術。

至於爲什麼教科書向您展示了它所做的代碼，很可能是因爲作者想要展示遞歸而不會一次性導入太多概念。

來源

2012-08-04 00:19:16 chrisaycock

如何通過超前檢測邊界的情況下減少遞歸次

回答

相關問題