python - 使用O(1)空间在python中自下而上的斐波那契

Question

我想使用 O(1) 空间写一个自下而上的斐波那契数列。我的问题是 python 的递归堆栈限制了我测试大量数据。有人可以为我所拥有的提供替代或优化吗？这是我的代码:

def fib_in_place(n):
    def fibo(f2, f1, i):
        if i < 1:
            return f2
        else:
            return fibo(f1, f2+f1, i -1)
    return fibo(0, 1, n)

Answer 1

以这种方式使用递归意味着您使用的是 O(N) 空间，而不是 O(1) - O(N) 在堆栈中。

为什么要使用递归？

def fib(n):
    a, b = 0, 1
    for i in range(n):
        a, b = b, a + b

    return a