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

您可能感兴趣的特别整齐的斐波那契实现，但它只能在Python 3.2和更高版本：

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

第一线的点是memoise递归调用。换句话说，评估是很慢的，例如， 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()) 

如上，因为它不具备大缓存的空间开销。