Python: 这个Fibonacci函数有什么问题？

Question

我试着写一个简单的Python函数，想要返回一个斐波那契数列，直到指定的最大值。但是我遇到了一个错误。我不知道自己哪里出错了。

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

你可能会对一个特别有趣的斐波那契数列实现感兴趣，不过它只适用于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())

像上面那样做，因为这样就不需要占用那么多空间来存储大量的结果。

Answer 2

list.extend 是用来直接在原来的列表上添加内容的。你也可以用 + 这个符号把两个列表合并在一起。

不过，你的代码写得不是特别符合 Python 的风格。对于无限序列，最好使用生成器，或者稍微改进一下你的代码：

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() 来获取下一个值。