Python：这个斐波那契函数有什么问题？

Question

我尝试编写一个简单的 python 函数，该函数应返回不超过指定最大值的 fib 数字列表。但我收到这个错误。我似乎无法找出我做错了什么。

def fib(a,b,n):
    f = a+b
    if (f > n):
        return []
    return [f].extend(fib(b,f,n))

>>>fib(0,1,10)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
  File "lvl2.py", line 35, in fib
    return [f].extend(fib(b,f,n))
TypeError: 'NoneType' object is not iterable

Answer 1

list.extend 就地扩展列表。您可以使用 + 运算符将两个列表连接在一起。

但是，您的代码并不是特别Pythonic。您应该使用无限序列生成器，或者作为对代码的轻微改进：

def fib(a,b,n):
    data = []
    f = a+b
    if (f > n):
        return data
    data.append(f)
    data.extend(fib(b,f,n))
    return data

使用无限序列生成器的示例：

def fibgen(a, b):
    while True:
        a, b = b, a + b
        yield b

您可以使用 fibgen() 创建生成器，并使用以下方法获取下一个值： .next()。

Answer 2

您可能对一个特别简洁的 Fibonacci 实现感兴趣，尽管它仅适用于 Python 3.2 及更高版本：

@functools.lru_cache(maxsize=None)
def fib(n):
    return fib(n-1) + fib(n-2) if n > 0 else 0

第一行的要点是记住递归调用。换句话说，例如 fib(20) 的计算速度很慢，因为您将重复大量工作，因此我们在计算值时缓存它们。

如上所述，这样做可能仍然更有效

import itertools
def nth(iterable, n, default=None):
    "Returns the nth item or a default value"
    return next(islice(iterable, n, None), default)
nth(fibgen())

，因为它没有大缓存的空间开销。