正如@alex所建议的，您可以使用生成器函数按顺序而不是递归地完成此操作。

这里是你问题中的等效代码:

def fib(n):
    def fibseq(n):
        """ Iteratively return the first n Fibonacci numbers, starting from 0. """
        a, b = 0, 1
        for _ in xrange(n):
            yield a
            a, b = b, a + b

    return sum(v for v in fibseq(n))

print format(fib(100000), ',d')  # -> no recursion depth error

资源。Setrlimit还必须用于增加堆栈大小和防止段故障

Linux内核限制了进程的堆栈。

Python将局部变量存储在解释器的堆栈上，因此递归占用解释器的堆栈空间。

如果Python解释器试图超过堆栈限制，Linux内核会使其出现分段错误。

堆栈限制大小由getrlimit和setrlimit系统调用控制。

Python通过资源模块提供了对这些系统调用的访问。

sys。例如，https://stackoverflow.com/a/3323013/895245中提到的setrecursionlimit只增加了Python解释器自身对其堆栈大小的限制，但它不会触及Linux内核对Python进程施加的限制。

示例程序:

main.py

import resource
import sys

print resource.getrlimit(resource.RLIMIT_STACK)
print sys.getrecursionlimit()
print

# Will segfault without this line.
resource.setrlimit(resource.RLIMIT_STACK, [0x10000000, resource.RLIM_INFINITY])
sys.setrecursionlimit(0x100000)

def f(i):
    print i
    sys.stdout.flush()
    f(i + 1)
f(0)

当然，如果你继续增加setrlimit，你的RAM最终会用完，这将使你的计算机由于疯狂的交换而变慢到停止，或者通过OOM杀手杀死Python。

在bash中，您可以使用以下命令查看并设置堆栈限制(单位为kb):

ulimit -s
ulimit -s 10000

我的默认值是8Mb。

参见:

在python脚本中设置stacksize Linux、Mac和Windows的硬递归限制是什么?

在Ubuntu 16.10, Python 2.7.12上测试。

我知道这是一个老问题，但对于那些阅读的人来说，我建议不要使用递归来解决这样的问题——列表要快得多，并且完全避免递归。我将这样实现:

def fibonacci(n):
    f = [0,1,1]
    for i in xrange(3,n):
        f.append(f[i-1] + f[i-2])
    return 'The %.0fth fibonacci number is: %.0f' % (n,f[-1])

(在xrange中使用n+1，如果你从0开始计数你的斐波那契数列，而不是从1开始。)

如果你只想得到很少的斐波那契数，你可以使用矩阵法。

from numpy import matrix

def fib(n):
    return (matrix('0 1; 1 1', dtype='object') ** n).item(1)

它的速度很快，因为numpy使用了快速求幂算法。结果是O(log n)比比奈公式好因为它只使用整数。但如果你想让所有的斐波那契数都不超过n，最好是死记硬背。

如果你经常需要改变递归限制(例如在解决编程难题时)，你可以定义一个简单的上下文管理器，像这样:

import sys

class recursionlimit:
    def __init__(self, limit):
        self.limit = limit

    def __enter__(self):
        self.old_limit = sys.getrecursionlimit()
        sys.setrecursionlimit(self.limit)

    def __exit__(self, type, value, tb):
        sys.setrecursionlimit(self.old_limit)

然后调用具有自定义限制的函数，您可以这样做:

with recursionlimit(1500):
    print(fib(1000, 0))

从with语句体退出时，递归限制将恢复到默认值。

附注:您可能还想增加Python进程的堆栈大小，以获得较大的递归限制值。例如，这可以通过ulimit shell内置或limits.conf(5)文件来完成。

当然，斐波那契数可以用O(n)计算，应用比奈公式:

from math import floor, sqrt

def fib(n):                                                     
    return int(floor(((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))+0.5))

正如评论者指出的那样，它不是O(1)，而是O(n)，因为2**n。另一个不同之处在于，您只能得到一个值，而使用递归则可以得到该值之前的所有Fibonacci(n)值。