当然，斐波那契数可以用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)值。

正如@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

是的，它是防止堆栈溢出的一种方法。Python(或者更确切地说，CPython实现)没有优化尾部递归，并且无限制的递归会导致堆栈溢出。你可以用sys.getrecursionlimit检查递归限制:

import sys
print(sys.getrecursionlimit())

并使用sys.setrecursionlimit更改递归限制:

sys.setrecursionlimit(1500)

但这样做是危险的——标准限制有点保守，但Python的堆栈框架可能相当大。

Python不是函数式语言，尾递归也不是一种特别有效的技术。如果可能的话，迭代地重写算法通常是一个更好的主意。

资源。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上测试。

这是为了避免堆栈溢出。Python解释器限制了递归的深度，以帮助您避免无限递归，从而导致堆栈溢出。 尝试增加递归限制(sys.setrecursionlimit)或重写不使用递归的代码。

来自Python文档:

sys.getrecursionlimit () 返回递归限制的当前值，即Python解释器堆栈的最大深度。这个限制可以防止无限递归导致C堆栈溢出和Python崩溃。可以通过setrecursionlimit()来设置。

我们还可以使用一种自底向上的动态规划方法

def fib_bottom_up(n):

    bottom_up = [None] * (n+1)
    bottom_up[0] = 1
    bottom_up[1] = 1

    for i in range(2, n+1):
        bottom_up[i] = bottom_up[i-1] + bottom_up[i-2]

    return bottom_up[n]

print(fib_bottom_up(20000))