在python中使用递归计算fibonacci数时出现的问题

Question

我有这段代码，用于使用缓存（字典）计算斐波纳契数。在

cache = {} 
def dynamic_fib(n):
    print n
    if n == 0 or n == 1:
        return 1
    if not (n in cache):
        print "caching %d" % n
        cache[n] = dynamic_fib(n-1) + dynamic_fib(n-2)

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    print "DYNAMIC: ", dynamic_fib(2000)
    print (time.time() - start)

我可以很好地处理小数字，但是如果输入超过1000个，它似乎就停止了。在

这是2000作为输入的结果。在

^{pr2}$

这是一个输入为1000的结果。在

....
8
caching 8
7
caching 7
6
caching 6
5
caching 5

它看起来像995存储到字典后，它就挂起了。 这有什么不对？我可以使用什么调试技术来查看python中出现了什么问题？在

我在macosx10.7.5上运行python，我有4G字节的RAM，所以我认为一些KB（甚至MB）的内存使用并不重要。在

Answer 1

Python的默认递归限制设置为1000。 你需要在你的计划中增加它。

import sys

sys.setrecursionlimit(5000)

发件人：http://docs.python.org/2/library/sys.html#sys.setrecursionlimit

sys.setrecursionlimit(limit)

Set the maximum depth of the Python interpreter stack to limit. 
This limit prevents infinite recursion from causing an overflow of the C 
stack and crashing Python.
The highest possible limit is platform-dependent. A user may need to set the
limit higher when she  has a program that requires deep recursion and a 
platform that supports a higher limit. This should bedone with care, because
a too-high limit can lead to a crash.

Answer 2

将缓存存储为字典并不能真正获得任何好处，因为为了计算f(n)，您需要知道f(n-1)（和f(n-2)）。换句话说，你的字典总是有2-n的键，你也可以用一个列表代替（它只是额外的2个元素）。以下是一个正确缓存且不会达到递归限制的版本：

import time
cache = [1,1]

def dynamic_fib(n):
    #print n
    if n >= len(cache):
        for i in range(len(cache),n):
            dynamic_fib(i)

        cache.append(dynamic_fib(n-1) + dynamic_fib(n-2))
        print "caching %d" % n

    return cache[n]

if __name__ == "__main__":
    start = time.time()
    a = dynamic_fib(4000)
    print "Dynamic",a
    print (time.time() - start)

注意，你可以用dict做同样的事情，但我几乎肯定列表会更快。

---

这里有很多选择公司名称：

^{pr2}$

结果是：

0.269892930984 dyn_fib_simple
0.256865024567 dynamic_fib2
0.241492033005 dynamic_fib
0.222282171249 fib_iter_memo
7.23831701279 fib_iter
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101
573147844013817084101

Answer 3

无递归版本：

def fibo(n):
   cache=[1,1]
   while len(cache) < n:
       cache.append(cache[-1]+cache[-2])
   return cache