OChem1 - 8 months ago 31

Python Question

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 `n`

th 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
```