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

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

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))

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

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/

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

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))

我不确定我是不是在重复某人的意思但前段时间有人写了一个y算子用于递归调用函数

def tail_recursive(func):
  y_operator = (lambda f: (lambda y: y(y))(lambda x: f(lambda *args: lambda: x(x)(*args))))(func)
  def wrap_func_tail(*args):
    out = y_operator(*args)
    while callable(out): out = out()
    return out
  return wrap_func_tail

然后递归函数需要形式:

def my_recursive_func(g):
  def wrapped(some_arg, acc):
    if <condition>: return acc
    return g(some_arg, acc)
  return wrapped

# and finally you call it in code

(tail_recursive(my_recursive_func))(some_arg, acc)

对于斐波那契数，你的函数是这样的:

def fib(g):
  def wrapped(n_1, n_2, n):
    if n == 0: return n_1
    return g(n_2, n_1 + n_2, n-1)
  return wrapped

print((tail_recursive(fib))(0, 1, 1000000))

输出:

..684684301719893411568996526838242546875

(实际上是数字的音调)

使用一种保证尾部调用优化的语言。或者使用迭代。或者，和装饰师一起玩。