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

我想给你一个使用内存计算斐波那契的例子，因为这将允许你使用递归计算更大的数字:

cache = {}
def fib_dp(n):
    if n in cache:
        return cache[n]
    if n == 0: return 0
    elif n == 1: return 1
    else:
        value = fib_dp(n-1) + fib_dp(n-2)
    cache[n] = value
    return value

print(fib_dp(998))

这仍然是递归的，但是使用了一个简单的哈希表，允许重用以前计算的斐波那契数，而不是重新计算。

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

看起来你只需要设置一个更高的递归深度:

import sys
sys.setrecursionlimit(1500)

RecursionError:在比较中超出的最大递归深度

解决方案:

首先，最好知道当你在一个大输入(> 10^4)上用Python执行递归函数时，你可能会遇到“最大递归深度超出错误”。

Python中的sys模块有一个函数getrecursionlimit()可以显示Python版本中的递归限制。

import sys
print("Python Recursive Limitation = ", sys.getrecursionlimit())

在某些版本的Python中，默认值是1000，而在另一些版本中则是1500

你可以改变这个限制，但重要的是要知道，如果你增加太多，就会出现内存溢出错误。

所以在增加它之前要小心。你可以使用setrecursionlimit()在Python中增加这个限制。

import sys
sys.setrecursionlimit(3000)

请点击此链接了解导致此问题的更多信息:

https://elvand.com/quick-sort-binary-search/

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