I need to find the list of Fibonacci numbers up to n by means of recursion. It is easy to find the last Fibonacci number given n but surprisingly difficult to put all of them in a list. I first put the empty list inside the function. Since it didn't work I made it global. I do not get the expected list of Fibonacci numbers. Thanks for any help. Here is the code:

import copy
s = []
def fibo(n):
   if n == 0: # the base case
     s.append(0)
     return 0
   elif n == 1 or n == 2:
     s.append(1)
     return 1 
   else:  
     k = fibo(n-1)   fibo(n-2) 
     s.append(copy.deepcopy(k))
     return k

print(fibo(7)) 
print(s) 

CodePudding user response：

Pass your list to the recursive levels, and append to that list. Since lists are mutable, changes made inside the inner calls to the function will happen on the original list. For the base case, create the list.

def fibo(n, series=None):
    # If no list is provided, create one
    if series is None:
        series = []

    if len(series) == 0:    # Base case 1
        series.append(0)
    elif len(series) == 1:  # Base case 2
        series.append(1)
    else:                   # General case
        series.append(series[-2]   series[-1])

    if len(series) <= n:     # Decide whether another level is required
                             # Comparison is <= because you want fibo(2) to return [0, 1, 1]
        fibo(n, series)      # If needed, pass series to the next level

    return series

Running this using e.g. fibo(10) gives the first 10 numbers of the Fibonacci sequence: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

If you want to pass the list from the bottom-up, you can do that without adding an argument. Just ask for the list containing the first n-1 Fibonacci numbers, and once the inner function returns a list, append to that list:

def fibo(n):
    if n == 0: return [0]
    elif n == 1: return [0, 1]
    else:
        lst = fibo(n-1)
        lst.append(lst[-2]   lst[-1])
        return lst