3

I want to write a recursive function in Python for Fibonacci.

x will be the starting point, y will be the subsequent of x and l is the length.

I don't understand what is my error in thinking:

 def fib(x, y, l, fibList=None):
    fibList = []
    z = x + y
    x = y
    fibList.append(z)
    y = z

    if len(fibList) <= l:
        return fib(x, y, l, fibList)
    else:
        return(fibList)

The result is:

RecursionError: maximum recursion depth exceeded while calling a Python object

I can solve it with a for loop but not with recursive function.

Tomerikoo
  • 18,379
  • 16
  • 47
  • 61
TheDev
  • 153
  • 5
  • 3
    Why don't you print out the values of `x`, `y`, `l`, and `fibList` as you enter the function to see if they are what you expected them to be. – jarmod Oct 14 '20 at 16:14
  • 1
    you can read this https://www.programiz.com/python-programming/recursion the page have visual explanation for what happen in recursion function – minion Oct 14 '20 at 16:15
  • 5
    I mean someone gave you a solution, but the error is, at the start of every fib function call you clear your fibList.. so the lists length will always be <= 1, thus you run into an infinite recursion loop which isnt good. add something like "if fibList == None:..." – Raqha Oct 14 '20 at 16:15
  • Please be aware that your code won't give a quite proper result even with the fix proposed by other answers. The Fibonacci sequence starts with a `0` term, and then two `1` terms. There is no way to call your function so that it produces the first two terms. The only way to get zero, for example, would be to pass in `0` for both `x` and `y`, and that of course will not lead to the correct production of each term in the sequence. See my answer, which solves this problem as well as the infinite recursion problem, and also provides a mod to your function to make it more caller-friendly. – CryptoFool Oct 14 '20 at 17:00

3 Answers3

1

There are a few problems here. Once you fix the infinite recursion, you still have an issue.

As @Raqha points out, you need to not initialize your list every time the fib function is called, but rather only the first time, when the fibList parameter isn't supplied and so defaults to None.

Your code is not able to generate the first two numbers in the sequence, 0 and 1. You can fix this by simply initializing your list to include these terms, and adjust the logic to only provide N-2 more terms.

The signature of your function could be improved to make it much easier for the caller to use it. The caller only cares about the number of terms he/she wants. The user shouldn't have to know what to enter for the initial x and y values.

Here's a version of your code with the fix for the infinite recursion, the fix for the missing terms, and also with the signature rearranged so that the user can call the function simply and obviously:

def fib(l, x=0, y=1, fibList=None):
    if fibList is None:
        fibList = [0, 1]
    z = x + y
    x = y
    fibList.append(z)
    y = z

    if len(fibList) < l-1:
        return fib(l, x, y, fibList)
    else:
        return(fibList)

print(fib(10))

Result:

[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
CryptoFool
  • 21,719
  • 5
  • 26
  • 44
0

At the start of every fib function call you clear your fibList with fibList = []. So the list's length will always be <= 1, thus you run into an infinite recursion loop which isn't good. You need to add something like if fibList is None:

When you first call the function "fib" without providing any 4th statement in the argument list, the value of fibList will initially set to "None". But later when you recursively call the function "fib" again, you provide a fibList in the argument list. So the value isnt "None" anymore. So when adding an if-statement as mentioned above, the function knows when you call the function from the outside (when you call it in your code as "fib(1,2,10)"), or when the function recursively calls itself. And so you dont reset the fibList everytime you call the function, but set it only 1 time at the start.

def fib(x, y, l, fibList=None):
    if fibList is None:
        fibList = []
    z = x + y
    ...
Raqha
  • 754
  • 4
  • 17
  • what does it do "if fibList == None:"? if the fibList is None it creats a new empty list otherwise it appends to the list correct? – TheDev Oct 14 '20 at 16:25
  • If the fibList isnt initiated yet, it will initiate it --> fibList = []. Then you append the new fib to this list, in the next if statement you look for its length. Which is in the first iteration 1, when your l variable is greater than 1, you will call this function again, but this time with a given fibList, so your fib list isnt None anymore, thus the if statement is false and it doesnt reset your fibList. know the length of the list can grow until it reached the l variable, then the 2nd if statement is false, thus you return the fiblist – Raqha Oct 14 '20 at 16:29
  • @Raqha, you should put the comment above in your answer. it's good stuff – CryptoFool Oct 14 '20 at 17:02
0

On the second line you set fibList = []. This means that every time you call the function recursively it resets the list to be empty so len(fibList) will always equal 1.

Remove that line so the fibList variable is not reset, then it should hit your exit condition correctly. How it is written now it runs forever until it breaks.

akerr
  • 355
  • 1
  • 11