Fibonacci series by recursive function in Python

Question

Hello I am trying to generate Fibonacci series by using a recursive function in python.

Here is my code

def fibolist(n):
    list1 = [1, 1]
    if n in (1,2) :
        return list1
    else:
        fibolist(n-1).append(sum(fibolist(n-1)[n-3:]))
        return list1

but when I enter any number as an argument, the result is [1, 1] Could you please help me?!

Try this... https://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence — gsb22, Feb 12 '20 at 19:24
I would recommend reading the follow article: https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — AMC, Feb 12 '20 at 19:46
You never update list1, so it will always be [1,1]. Even when you recursively call fibolist, you need to change list1 or do something with it and return that value. — linamnt, Feb 12 '20 at 21:20

score 2 · Answer 1 · answered Feb 12 '20 at 19:26

2

You start with

list1 = [1, 1]

You never change that value, and then you return it to the calling routine.

Each invocation of fibolist has a local variable named list1; appending to one does not change the list1 value in the calling program. You need to explicitly do that. Try

else:
    return fibolist(n-1) + [sum(fibolist(n-1)[n-3:])]

answered Feb 12 '20 at 19:26

Prune

75,308
14
55
76

Thank you very much, It was a big help! :) – Behzad Norouzi Feb 12 '20 at 19:38

Grzegorz Skibinski · Answer 2 · 2020-02-12T19:38:35.307

1

Just to fix your code:

def fibolist(n):
    if n in (0,1) :
        return [1,1]
    else:
        return fibolist(n-1)+[sum(fibolist(n-1)[n-2:])]

Few notes:

lists in python have starting index=0, so it's better start with it (unless you want to put start return to [0,1,1] for n in (1,2)).

Also - as already mentioned you shouldn't return local variable, which you preassign in each go.

edited Feb 12 '20 at 19:38

answered Feb 12 '20 at 19:32

Grzegorz Skibinski

12,152
2
9
32

1

Thank you very much, It was a big help! :) – Behzad Norouzi Feb 12 '20 at 19:36

score 1 · Answer 3 · edited Feb 12 '20 at 19:52

Your code is not updating the list1 variable that it returns upon coming back from the recursion. Doing fibolist(n-1).append(...) updates the list returned by the next level but that is a separate list so list1 is not affected.

You could also make your function much simpler by making it pass the last two values to itself:

def fibo(n,a=1,b=1): return [a] if n==1 else [a] + fibo(n-1,b,a+b)

BTW, the modern interpretation of the fibonacci sequence starts at 0,1 not 1,1 so the above signature should be def fibo(n,a=0,b=1).

Output:

print(fibo(5))
#[1, 1, 2, 3, 5]

Fibonacci series by recursive function in Python

3 Answers3