CODEWITHSUNDEEP
pythonlistrecursionfibonacci
LEJ
LEJ

Reputation: 1958

Calculate Fibonacci numbers up to at least n

I am trying to make a function that allows a user to input a number and the result will be a list containing Fibonacci numbers up to the input and one above if the input is not in the series. For example, input of 4 will return [0, 1, 1, 2, 3, 5] but input of 3 would return [0, 1, 1, 2, 3]. I have managed to do this using the function below :

    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)

However, I would now like to be able to do this recursively, any ideas?

Upvotes: 0

Views: 1652

Answers (2)

Ayoub ABOUNAKIF
Ayoub ABOUNAKIF

Reputation: 480

 def calculate_fibonnaci(n):
     if n == 0:
         return 0
     if n == 1:
         return 1
     else:
         return calculate_fibonnaci(n - 1) + calculate_fibonnaci(n - 2)

Here's a simple solution using a recursive function.

Upvotes: 1

6502
6502

Reputation: 114481

A possible solution is the following

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

the idea is that to return the list of all fibonacci numbers less than n you can ask for the list of those less than n-1 and then possibly add just one element. This works from 2 on if we define the first two numbers being [1, 1]. Using [0, 1] instead creates a problem for 2 because a single next element is not enough.

This code is not inefficient on time (fibonacci is a double recursion, this is a simple recursion), but uses a lot of stack space.

Upvotes: 2

Related Questions