Write a recursive function to solve Fibonacci

Question

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.

Answer 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]