Python：このフィボナッチ関数の問題は何ですか？

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

list.extendインプレースリストを拡張します。 +演算子を使用すると、2つのリストを連結することができます。

しかし、あなたのコードは特に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 

無限シーケンスのための発電機を使用した例：あなたはfibgen()で発電機を作成して引き出すことができる

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

.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()) 

を行うには、まだおそらくより効率的です。