使用 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

Answer 2

您可以记住斐波那契函数以提高效率，但如果您需要递归函数，它仍然至少需要 O(n)：

def mem_fib(n, _cache={}):
    '''efficiently memoized recursive function, returns a Fibonacci number'''
    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, mem_fib(n-1) + mem_fib(n-2))
    return n

这是我对 Python 中主要斐波那契数列问题的回答：How to write the Fibonacci Sequence in Python

如果你被允许使用迭代而不是递归，你应该这样做：

def fib():
    a, b = 0, 1
    while True:            # First iteration:
        yield a            # yield 0 to start with and then
        a, b = b, a + b    # a will now be 1, and b will also be 1, (0 + 1)

用法：

>>> list(zip(range(10), fib()))
[(0, 0), (1, 1), (2, 1), (3, 2), (4, 3), (5, 5), (6, 8), (7, 13), (8, 21), (9, 34)]

如果您只想获得第 n 个数字：

def get_fib(n):
    fib_gen = fib()
    for _ in range(n):
        next(fib_gen)
    return next(fib_gen)

和用法

>>> get_fib(10)
55