斐波那契序列：遞歸深度過剩

鑑於生成Fibonacci數的函數：斐波那契序列：遞歸深度過剩

def fibonacci(x, memory = {0:0, 1:1}): 
     if x not in memory: 
       memory[x] = fibonacci(x-1, memory)+fibonacci(x-2, memory) 
     return memory[x]

當我嘗試一些任意大的數，如第4000斐波那契數，我得到一個錯誤：

RuntimeError: maximum recursion depth exceeded

什麼是造成的錯誤？在不犧牲效率的前提下，可以做些什麼？我更喜歡迭代，因爲通過迭代計算即使第50個位置對於計算機來說也需要天文學上的漫長時間（閱讀：半分鐘）。

來源

2014-12-04 Alvin Lepik

迭代應該顯著強於大盤遞歸 - 它不健全的權利，這將需要超過一秒鐘的一個很小的部分來計算F1通過F50。無論如何，如果這是Python，那麼你可能想看看sys.getrecursionlimit（）和sys.setrecursionlimit（） – 2014-12-04 06:25:50

在我看來，迭代比遞歸好得多。因爲

迭代比遞歸更容易讀取和追蹤。
您可以使用諸如Generators的概念來減少遞歸函數可能無法實現的內存負載。

至於什麼是遞歸限制，你可以看到here。它給出了遞歸限制的基本解釋。如圖所示，您可以將sys.setrecursionlimit設爲您所需的任何值。

使用迭代器，這可以用於斐波納契數列：

def fib(a, b): 
    return b, a+b 

for i in range(20): 
    if i in (0, 1): 
     print i 
    else: 
     print a 
    a, b = fib(a, b)

來源

2014-12-04 06:59:10 thiruvenkadam

我想你碰到了遞歸限制。 Here是指向類似帖子的鏈接，這可能有所幫助。我會建議您使用迭代，但我也遇到了這個代碼，以增加堆棧大小，但沒有測試它：

import sys 
sys.setrecursionlimit(10000) # change the '10000' to something that works

來源

2014-12-04 06:29:00 pietergdp

正如其他人提到你已經一堆棧內存限制。在達到此限制之前，通常最多可以有50-100個最大嵌套遞歸調用。

我想你可能有一個關於迭代誤解（展開遞歸函數）

def fib(): 
    a=0 
    b=1; 
    c=1; 
    for x in range(4000): 
     c = a + b; 
     a = b; 
     b = c; 
    print c; 

fib();

沒有辦法，這個功能將需要更長的時間比你的遞歸之一。

來源

2014-12-04 06:38:36 softwarenewbie7331

斐波那契序列：遞歸深度過剩

回答

相關問題