少なくともnまでのフィボナッチ数を計算する

Question

ユーザが数字を入力できるようにしようとしていますが、入力がフィボナッチ数を含むリストになります。シリーズ。たとえば、4の入力は[0, 1, 1, 2, 3, 5]を返しますが、3の入力は[0, 1, 1, 2, 3]を返します。私は、以下の機能使ってこれを行うために管理している：

def fibonacci(n): 
     series = [0] 
     if (n == 0): 
      pass 
     else: 
      series.append(1) 
      if (n == 1): 
       pass 
      else: 
       while(series[len(series)-1] < n): 
        newValue = series[len(series)-1] + series[len(series)-2] 
        series.append(newValue) 
     print(series) 

をしかし、私は今、再帰的に任意のアイデアをこれを実行できるようにしたいと思いますか？

Answer 1

可能な解決策は、アイデアは、それはあなたがそれらの少ないn-1以上のリストを要求し、その後、おそらくただ一つの要素を追加することができますn未満のすべてのフィボナッチ数のリストを返すことです以下

def fibo_up_to(n): 
    if n < 2: 
     return [1,1] 
    else: 
     L = fibo_up_to(n-1) 
     if L[-1] < n: 
      L.append(L[-1] + L[-2]) 
     return L 

です。これは、最初の2つの数値が[1, 1]であると定義すると、2から始まります。 [0, 1]を使用すると、代わりに1つの次の要素では不十分なため、2に問題が発生します。

このコードは、時間の経過に伴って非効率的ではありません（フィボナッチは2回の再帰ですが、これは単純な再帰です）が、多くのスタックスペースを使用します。