An iterative algorithm for Fibonacci numbers

Ris picture Ris · Feb 24, 2013 · Viewed 83k times · Source

I am interested in an iterative algorithm for Fibonacci numbers, so I found the formula on wiki...it looks straight forward so I tried it in Python...it doesn't have a problem compiling and formula looks right...not sure why its giving the wrong output...did I not implement it right ?

def fib (n): 
    if( n == 0):
        return 0
    else:
        x = 0
        y = 1
        for i in range(1,n):
            z = (x + y)
            x = y
            y = z
            return y

for i in range(10):
    print (fib(i))

output

0
None
1
1
1
1
1
1

Answer

poke picture poke · Feb 24, 2013

The problem is that your return y is within the loop of your function. So after the first iteration, it will already stop and return the first value: 1. Except when n is 0, in which case the function is made to return 0 itself, and in case n is 1, when the for loop will not iterate even once, and no return is being execute (hence the None return value).

To fix this, just move the return y outside of the loop.

Alternative implementation

Following KebertX’s example, here is a solution I would personally make in Python. Of course, if you were to process many Fibonacci values, you might even want to combine those two solutions and create a cache for the numbers.

def f(n):
    a, b = 0, 1
    for i in range(0, n):
        a, b = b, a + b
    return a