OChem1 OChem1 - 6 months ago 13
Python Question

Getting an index error in a python fibonacci program

I just started "Algorithmic toolbox" on Coursera, and was writing their version of the Fibonacci program in python 2.7

def fibonacci(n):
F = []
F[0] = 0
F[1] = 1

for i in range(0,n):
F[i] = F[i-1] + F[i-2]

return F[n]

fibonacci(3)


But, I keep getting this error:

Traceback (most recent call last):
File "fibonacci.py", line 11, in <module>
fibonacci(3)
File "fibonacci.py", line 3, in fibonacci
F[0] = 0


IndexError: list assignment index out of range

Answer

You can't create new elements in a Python list by assigning to non-existing indices. Your list is empty, so indices 0 and 1 don't exist.

Use list.append() instead:

def fibonacci(n):
    F = [0, 1]  # a list with two initial elements

    for i in range(2, n + 1):
        F.append(F[i-1] + F[i-2])

    return F[n]

Note that the loop starts at 2, not 0, because you already have the values for 0 and 1. The stop argument to range() is not included so if you want to find the nth fibonacci number, you need to run the range up to n + 1.

Now the code works:

>>> def fibonacci(n):
...     F = [0, 1]  # a list with two initial elements
...     for i in range(2, n + 1):
...         F.append(F[i-1] + F[i-2])
...     return F[n]
...
>>> fibonacci(10)
55

Note that you don't really need to store all values in a list; you only need to track the last 2. You could use just two variables and swap these around for each iteration; one stores the

def fibonacci(n):
    prev, current = 0, 1
    for _ in range(n - 1):  # run n - 2 times
        prev, current = current, prev + current
    return current
Comments