CODEWITHSUNDEEP
python-3.x
Ahmed Nishaal
Ahmed Nishaal

Reputation: 96

I was trying to make a recursion function with python for the fibonacci sequence

The function is supposed to return a list of the first n numbers of the fibonacci sequence, but its returning nothing and I'd like to know why


def fibonacci(n, sequence=[0, 1], originalN=0):
    print(n, sequence[:-2])

    if n <= 0:
        print(n)
        return(sequence[:-2])

    nextValue = sequence[-1] + sequence[-2]
    sequence.append(nextValue)

    

    fibonacci(n-1, sequence, originalN)

print(fibonacci(10))

some print functions inside the main function are left behind for debugging purposes

Upvotes: 0

Views: 133

Answers (2)

Anonymous Coder
Anonymous Coder

Reputation: 586

it is due to the missing return statement, if the condition not enter the if block then it just simply calls the recursive function but don't return anything. It only return only for the base case.

def fibonacci(n, sequence=[0, 1], originalN=0):
    #print(n, sequence[:-2])

    if n <= 0:
        #print(n)
        return(sequence[:-2])

    nextValue = sequence[-1] + sequence[-2]
    sequence.append(nextValue)

    return fibonacci(n-1, sequence, originalN)

print(fibonacci(10))

Upvotes: 0

Shubham
Shubham

Reputation: 1438

You are missing a return statement. The recursive calls are not returning back the slice up the recursion stack. The only reason your Fibonacci series is even building with the previous code is that they are all sharing the same list object.

def fibonacci(n, sequence=[0, 1], originalN=0):
    if n <= 0:
        return (sequence[:-2])

    nextValue = sequence[-1] + sequence[-2]
    sequence.append(nextValue)

    return fibonacci(n-1, sequence, originalN)

print(fibonacci(10))

Output:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

Edit: To clarify, the return statement you previously had only returned the sequence from the deepest call (leaf on the recursion tree to its parent (when n was 1), but the return statement is also needed for the recursive call to pass this value up the recursion tree.

You can avoid using the recursion stack and do a more efficient Fibonacci sequence computation as follows:

def fibonacci(n):
    sequence = [0, 1]
    for i in range(2, n):
        sequence.append(sequence[-1] + sequence[-2])
    return sequence

Edit 2: As @Clockwork-Muse recommended, a more pythonic way is to use an infinite generator instead of returning lists. You can also generate as long sequences as you want. Here is my take at this approach:

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

sequence = fib()

Demo (n can be anything, as fib is a generator object and will keep generating the next number in the sequence):

n = 10
for i in range(n):
    print(next(sequence), end=", ")

Output: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,

Upvotes: 1

Related Questions