CODEWITHSUNDEEP
python
Loki
Loki

Reputation: 99

Fibonacci - I am stuck

so I am new in programming (as you will see from my silly question). I am really stuck with this bit: 

def Fibonnaci():
    num = int(raw_input("How many numbers? "))
    i = 1
    if num ==0:
        fib = []
    elif num ==1:
        fib = [1]
    elif num ==2:
        fib = [1,1]
    elif num >2:
        fib = [1,1]
    while i < (num - 1):
        fib.append(fib[i] + fib[i -1])
        i += 1
    return fib
print Fibonnaci()

What I don’t get is the fib.append(fib[i] + fib[i-1])

So lets say the number I selected in the input is 5. So the fib list will have [1,1] in. Then the i will be 1. Now I get confused. If the i in fib[i] is 1, then the i-1 is 0. 1+0 is 1 and the print out should then be [1,1,1,3,5]. This actually happened when I removed the fib. and left it only as fib.append(i+(i-1)).

So I presume the fib is doing something important but I cant figure out what. Because at this point i = 1. So how does the list get the 2 there? The output is 1,1,2,3,5. Even if the fib[i] would mean that the i is now 2 as there are [1,1] in the list, then it would go 2+1 = 3 hence the fib would now be [1,1,3].

I hope I haven’t confused you completely (because I am confusing myself).

Upvotes: 0

Views: 128

Answers (2)

willeM_ Van Onsem
willeM_ Van Onsem

Reputation: 476584

If one writes fib[i] it means the expression is expanded to the value in list fib on index i. So say we have constructed fib and it is:

fib = [1,1]

The first iteration

now i = 1 and we execute the line:

fib.append(fib[i]+fib[i-1])

Now what does this mean, first the expression is expanded by substituting i into 1, we thus read:

fib.append(fib[1]+fib[1-1])

or

fib.append(fib[1]+fib[0])

Now the second (lists start at index 0) value of fib (fib[1]) is 1 and so is the first element (fib[0]) so we expand this to:

fib.append(1+1)

or:

fib.append(2)

Now Python will perform this action and fib now is:

fib = [1,1,2]

The second iteration

After fib is altered, i is updated (now i = 2), and so we go for the next iteration. In this iteration we again perform:

fib.append(fib[i]+fib[i-1])

since i=2, we can substitute this for:

fib.append(fib[2]+fib[1])

Now the third (fib[2]) and the second (fib[1]) element of the list are 1 and 2 respectively (you can check this from the end of the previous section), and thus Python will run:

fib.append(2+1)

which is thus equivalent to:

fib.append(3)

So after this iteration, fib is equal to:

fib = [1,1,2,3]

This process is repeated until i gets to the bound. So each time, Python reads the last two elements of the fib list constructed this far, adds them together and adds this at the end of the list (fib). Finally if the bound is reached, the result is returned.

Upvotes: 3

Marat
Marat

Reputation: 15738

i is only a counter here. The last part could be changed this way:

# we need to repeat n-2 times (i.e. once for a list of 3)
for i in range(num-2):
    # fib is the array of numbers we already have
    # we append sum of the last two elements n-2 times
    fib.append(fib[-1] + fib[-2])  
return fib

In the original example, since i is the same as the length of fib, it is used as index. So, fib[i] is the last element and fib[i-1] is the last but one

Upvotes: 2

Related Questions