1

我对 Python 还很陌生，但我遇到了这个挑战，要递归地创建一个斐波那契生成器，让我开始学习这门语言。问题是，如果我发现超过 3226/3227 个斐波那契数，Python 就会崩溃。(Python 3)

注意：我在 PHP、JavaScript、VBA 和 Java 中做了很多编程，但我对 Python 完全陌生。因此，如果这只是数据类型错误之类的问题，我真的很抱歉。

import sys
sys.setrecursionlimit(1000000000)

cache = dict()

 def fibonacci(n, arr = False):
    global cache

    if n == 0 or n == 1:
         r = n
    else:
        nVal1 = n - 1
        nVal2 = n - 2
        if (not nVal1 in cache):
            num1 = cache[nVal1] = fibonacci(nVal1, arr)
        else:
            num1 = cache[nVal1]
        if (not nVal2 in cache):
            num2 = cache[nVal2] = fibonacci(nVal2)
        else:
            num2 = cache[nVal2]

        r = num1 + num2


     if arr != False:
        arr.append(r)


    return r

fib = list()
# 3227 is max without generating a list.
# 3226 is max when generating a list.
fibonacci(3226, fib)
for x in fib: print(x)

我能做些什么让它比这更进一步？我不认为它已经耗尽内存，因为它在我的慢速 i3 笔记本电脑上运行大约两秒钟..

4

2 回答 2

2

阅读sys.setrecursionlimit的注释

可能的最高限制取决于平台。当用户有一个需要深度递归的程序和一个支持更高限制的平台时，她可能需要将限制设置得更高。这应该小心完成，因为过高的限制会导致崩溃。

我会这样实现fibo

def fib():
    a,b = 1,0
    while True:
        yield a
        b = a+b
        yield b
        a = a+b

fibs = fib()
fibo = [next(fibs) for i in xrange(100)]
于 2013-01-26T23:42:26.320 回答
2

我猜你超过了 python 解释器允许的最大堆栈深度。随着您进一步研究新功能，您最终将耗尽 python VM 分配的内存量以适应堆栈。

您可以将http://docs.python.org/library/sys.html#sys.setrecursionlimit更改为某个点，但最大可能的深度是由实现定义的。

于 2013-01-26T23:42:47.207 回答