python 2.7 - 遞歸斐波那契爆炸

我有兩個函數fib1和fib2來計算斐波納契。python 2.7 - 遞歸斐波那契爆炸

def fib1(n): 
    if n < 2: 
     return 1 
    else: 
     return fib1(n-1) + fib1(n-2) 

def fib2(n): 
    def fib2h(s, c, n): 
     if n < 1: 
      return s 
     else: 
      return fib2h(c, s + c, n-1) 
    return fib2h(1, 1, n)

fib2直到它炸燬遞歸限制正常工作。如果理解正確，Python不會針對尾遞歸進行優化。這對我來說很好。

什麼讓我是fib1開始放緩，即使值很小的n也停下來。爲什麼會發生？在它遲緩之前它怎麼沒有達到遞歸限制？

來源

2012-10-10 JBoyer

CPU時間：用戶0.35 S，SYS：0.00 s，共0.35小號牆時間：0.35小號......這就是花了多長時間我要'FIB1（30）'..似乎理由在Python 3中能夠使用 –

'fib2（30）'，real：0m0.032s，user：0m0.025s，sys：0m0.006s。您使用的是什麼版本的Python？ –

@JoranBeasley嘗試fib1（100） – JBoyer

基本上，你是在浪費大量的時間。你可以很容易地記憶這樣的功能

def fib1(n, memo={}): 
    if n in memo: 
     return memo[n] 
    if n < 2: 
     memo[n] = 1 
    else: 
     memo[n] = fib1(n-1) + fib1(n-2) 
    return memo[n]

你會注意到我使用了一個空字典作爲默認參數。這通常是一個壞主意，因爲每個函數調用都使用相同的字典作爲缺省值。

在這裏，我趁着通過使用它來memoize的每個結果我計算

你也可以主要用0和1的備忘錄，以避免需要的n < 2測試

def fib1(n, memo={0: 1, 1: 1}): 
    if n in memo: 
     return memo[n] 
    else: 
     memo[n] = fib1(n-1) + fib1(n-2) 
    return memo[n]

這成爲

def fib1(n, memo={0: 1, 1: 1}): 
    return memo.setdefault(n, memo.get(n) or fib1(n-1) + fib1(n-2))

來源

2012-10-11 00:28:45

+1教我一些新東西今天通過實際利用有一個默認參數在多個調用中引用相同的對象。 –

這是非常聰明的 – JBoyer

後來的版本會導致'n <0'的無限遞歸，不過不可否認的是，它不在問題域內。 –

想想每個中的遞歸樹。第二個版本是遞歸的一個分支，在函數調用的參數計算中增加了它，然後它返回值。如您所知，Python不需要尾遞歸優化，但是如果尾調用優化是解釋器的一部分，尾遞歸優化也可以被觸發。

另一方面，第一個版本需要2個遞歸分支在每個級別！因此，相當多的函數skyrockets可能執行。不僅如此，大部分工作都重複了兩次！考慮：fib1(n-1)最終再次調用fib1(n-1)，這與從第一個調用幀的參考點調用fib1(n-2)相同。但在計算出該值後，必須再次將它加到fib1(n-2)的值上！所以這項工作被不必要地重複了很多次。

來源

2012-10-11 00:09:48

你的問題不是python，它是你的算法。 fib1就是tree recursion的一個很好的例子。你可以找到一個證明here on stackoverflow，這個特定的算法是（〜θ(1.6ⁿ)）。

n=30（顯然來自評論）大約需要三分之一秒。如果計算時間大大加快了爲1.6^n，我們預計n=100通過計算一遍又一遍n的值相同的FIB1約需2.1 million years.

來源

2012-10-11 00:12:55

不錯:)我喜歡你對n = 100會花費多少時間的解釋:) ...時間可以獲得大約210萬個核心......然後你可以在一年內完成：P –

python 2.7 - 遞歸斐波那契爆炸

回答

相關問題