Calculer les nombres de Fibonacci jusqu'à au moins n

Question

J'essaye de faire une fonction qui permet à un utilisateur d'entrer un nombre et le résultat sera une liste contenant des nombres de Fibonacci jusqu'à l'entrée et un dessus si l'entrée n'est pas dans le séries. Par exemple, l'entrée de 4 renvoie [0, 1, 1, 2, 3, 5] mais l'entrée de 3 renvoie [0, 1, 1, 2, 3]. J'ai réussi à le faire en utilisant la fonction ci-dessous:

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) 

Cependant, je voudrais maintenant pouvoir faire récursive, des idées?

Answer 1

Une solution possible est la suivante

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 

l'idée est que pour retourner la liste de tous les numéros de fibonacci moins de n vous pouvez demander la liste des moins de n-1 et peut-être ajouter un seul élément . Cela fonctionne à partir de 2 si nous définissons les deux premiers nombres étant [1, 1]. L'utilisation de [0, 1] crée à la place un problème pour 2 car un seul élément suivant ne suffit pas.

Ce code n'est pas inefficace à l'heure (fibonacci est une double récursion, c'est une récursion simple), mais utilise beaucoup d'espace de pile.