python - 在 python 中使用递归计算斐波那契数时的问题

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 的结果。

....
caching 1008
1007
caching 1007
1006
caching 1006
1005
caching 1005

这是以 1000 作为输入的结果。

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

貌似995存入字典后，就挂了。这可能有什么问题？我可以使用什么调试技术来查看 python 中出了什么问题？

我在 Mac OS X 10.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.