計算斐波納契數字至少爲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

一個可能的解決方案是以下

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 

的想法是，返回所有斐波那契數小於n你可以要求那些小於n-1和列表的列表，然後可能只添加一個元素。如果我們定義前兩個數字爲[1, 1]，則這從2開始工作。相反，使用[0, 1]會爲2創建一個問題，因爲僅有一個下一個元素是不夠的。

這段代碼在時間上並不低效（斐波那契是一個雙遞歸，這是一個簡單的遞歸），但是使用了很多棧空間。