21

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

1
  • A post worth looking at if you are interested in complexity of your algorithm for Fibonacci series.
    – RBT
    Commented Aug 10, 2017 at 6:52

13 Answers 13

73

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
7
  • 4
    @Adelin What language is that? This is a Python question and that’s not Python code. Consider creating a new question, or ask on codereview.SE for review of your code. That being said, your array size is wrong for limit=1 which will give you an index exception.
    – poke
    Commented Jul 19, 2015 at 18:51
  • 1
    Returning a at the end of the script is the computation of f(n - 1) and not f(n). You should return b to have f(n) returned
    – eton_ceb
    Commented Dec 4, 2016 at 16:13
  • 2
    @eton_ceb That depends on your definition of the Fibonacci sequence. I usually start the sequence with 0 and 1 instead of 1 and 1.
    – poke
    Commented Dec 4, 2016 at 16:59
  • 2
    You can ignore i and just write for _ in range(n)
    – Florimond
    Commented Jul 6, 2019 at 13:33
  • 1
    I would make 2 changes: (1) : Instead of return a, we can return b, then we can loop one less time and get the ans. (2): Instead of for i in range(0, n):, use for i in range(2, n+1):, so the i would represent the actual fib calculation for fib(b). Finally, caching is unnecessary, we are doing O(1) time complexity each round anyway. Cheers. Commented May 27, 2021 at 4:27
5

You are returning a value within a loop, so the function is exiting before the value of y ever gets to be any more than 1.

If I may suggest something shorter, and much more pythonful:

def fibs(n):                                                                                                 
    fibs = [0, 1, 1]                                                                                           
    for f in range(2, n):                                                                                      
        fibs.append(fibs[-1] + fibs[-2])                                                                         
    return fibs[n]

This will do exactly the same thing as your algorithm, but instead of creating three temporary variables, it just adds them into a list, and returns the nth fibonacci number by index.

5
  • 1
    This will take much more memory though as it needs to keep them all in the list (you’d notice it for very large n). Also I don’t think this is the best pythonic solution for this. I think using tuple (un)packing in a simple for loop (see edit to my answer) would be even nicer.
    – poke
    Commented Feb 24, 2013 at 0:57
  • 1
    i would go one step further and say that although this solution is iterative, it has the same drawback as the recursive solution in the sense that it doesn't run in constant space. you've just replaced the stackframes with list elements.
    – rbp
    Commented Mar 11, 2014 at 17:06
  • @KebertX I know this thread is old but why does a,b = b,a+b inside the for loop work and not when you write it like this a=b and b = a+b? i mean a,b = b,a+b is just a = b and b = a+b right? Commented Jun 23, 2015 at 3:06
  • 1
    @HalcyonAbrahamRamirez: Tuple assignment is not the same as sequentially assigning each right side expressions to its respective "variable": with tuple assignment, the last evaluation is done before the first assignment - consider swapping: a, b = b, a
    – greybeard
    Commented Jan 5, 2017 at 10:27
  • This is a recursive solution, original question is looking for an iterative solution
    – Maksood
    Commented Oct 13, 2020 at 18:44
1

On fib(0), you're returning 0 because:

if (n == 0) {
    return 0;
}

On fib(1), you're returning 1 because:

y = 1
return y

On fig(2), you're returning 1 because:

y = 1
return y

...and so on. As long as return y is inside your loop, the function is ending on the first iteration of your for loop every time.

Here's a good solution that another user came up with: How to write the Fibonacci Sequence in Python

1
  • (wherever those curly braces came from… from __future__ import braces? :P)
    – poke
    Commented Feb 24, 2013 at 0:13
0
def fibiter(n):
    f1=1
    f2=1
    tmp=int()
    for i in range(1,int(n)-1):
        tmp = f1+f2
        f1=f2
        f2=tmp
    return f2

or with parallel assignment:

def fibiter(n):
    f1=1
    f2=1
    for i in range(1,int(n)-1):
        f1,f2=f2,f1+f2
    return f2

print fibiter(4)

0

I came across this on another thread and it is significantly faster than anything else I have tried and wont time out on large numbers. Here is a link to the math.

def fib(n):
    v1, v2, v3 = 1, 1, 0  
    for rec in bin(n)[3:]: 
        calc = v2*v2
        v1, v2, v3 = v1*v1+calc, (v1+v3)*v2, calc+v3*v3
        if rec=='1':    v1, v2, v3 = v1+v2, v1, v2
    return v2
0

This work (intuitively)

def fib(n):
    if n < 2:
        return n
    o,i = 0,1
    while n > 1:
        g = i
        i = o + i
        o = g
        n -= 1
    return i
4
  • 1
    Does this answer did I not implement it right ? ? (I find poke's code intuitive, and "counting down n by hand" irritating.)
    – greybeard
    Commented Jan 5, 2017 at 10:44
  • @greybeard Who's asking did I not implement it right? ? (what's wrong counting down, Python allows it why not use it?!)
    – MsO
    Commented Jun 3, 2017 at 19:54
  • 1
    Who's asking… [user:Ris] is (in the last sentence of this question). In my eyes, there is nothing wrong with counting down - I emphasised by hand (using explixit expressions, assignments, conditions…) in my comment, I don't think it pythonesque*/*pythonic. It is avoidably verbose.
    – greybeard
    Commented Jun 3, 2017 at 21:12
  • I got your point, but I am not a python guy, that was a thought(algorithm) and just expressed it with python (nothing more), -- while reading sicp...
    – MsO
    Commented Jun 8, 2017 at 10:30
0

How about this simple but fastest way... (I just discovered!)

def fib(n):
    x = [0,1]
    for i in range(n >> 1):
        x[0] += x[1]
        x[1] += x[0]
    return x[n % 2]

Note! as a result, this simple algorithm only uses 1 assignment and 1 addition, since loop length is shorten as 1/2 and each loop includes 2 assignment and 2 additions.

2
  • 1
    I don't see the improvement over "the a-b-formulation". fastest way you are aware of approaches using O(log n) iterations?
    – greybeard
    Commented Jan 6, 2017 at 19:00
  • Correctly, the number of assignment in other a-b formation is 3*n , since there is a hidden assignment inclused ( any swap like problem can not avoid this sequence: temp = a, a = a+ b, b = temp). So I can say my sugestion is faster way. Actually I tested and checked the result 2x or 3x fast then other a-b formation. And can you suggest any O(log n) algorithm in fibonacci problem?
    – digitect38
    Commented Jan 7, 2017 at 5:04
0
fcount = 0 #a count recording the number of Fibonacci numbers generated
prev = 0
current = 0
next = 1
ll = 0 #lower limit
ul = 999 #upper limit

while ul < 100000:
    print("The following Fibonacci numbers make up the chunk between %d and %d." % (ll, ul))
    while next <= ul:
        print(next)
        prev = current
        current = next
        next = prev + current
        fcount += 1 #increments count

    print("Number of Fibonacci numbers between %d and %d is %d. \n" % (ll, ul, fcount))        
    ll = ul + 1 #current upper limit, plus 1, becomes new lower limit
    ul += 1000 #add 1000 for the new upper limit
    fcount = 0 #set count to zero for a new batch of 1000 numbers
0

Non recursive Fibonacci sequence in python

def fibs(n):
    f = []
    a = 0
    b = 1
    if n == 0 or n == 1:
        print n
    else:
        f.append(a)
        f.append(b)
        while len(f) != n:
            temp = a + b
            f.append(temp)
            a = b
            b = temp

    print f

fibs(10)

Output: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

3
  • 1
    Does this answer did I not implement it right ? ?
    – greybeard
    Commented Apr 11, 2017 at 8:59
  • Fibonacci series values: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711,..... Please compare the values of your output with this values
    – karuna
    Commented Apr 17, 2017 at 11:25
  • I don't have output. I happen to know OEIS A000045, and to be the one to try and improve the presentation of a 2013/2 question in '17/1.
    – greybeard
    Commented Apr 17, 2017 at 15:12
0

Another possible approach:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=2
while i<n:
    e=d[-1]+d[-2]
    d.append(e)
    i+=1
print("Fibonacci series of {} is {}".format(n,d))
1
  • While this code works, it seems to be solving a different problem than what the questioner was asking about. You're computing a list of all the first n values in the Fibonacci series, while their function just computes the nth value. There's no need to use O(n) memory for that. And I really don't understand why you've answered twice, with very similar code in each. If you think there are multiple useful algorithms, you can post them both in the same answer.
    – Blckknght
    Commented Aug 20, 2019 at 1:16
-1

Assuming these values for the fibonacci sequence:

F(0) = 0;

F(1) = 1;

F(2) = 1;

F(3) = 2

For values of N > 2 we'll calculate the fibonacci value with this formula:

F(N) = F(N-1) + F(N-2)

One iterative approach we can take on this is calculating fibonacci from N = 0 to N = Target_N, as we do so we can keep track of the previous results of fibonacci for N-1 and N-2

public int Fibonacci(int N)
{
    // If N is zero return zero
    if(N == 0)
    {
        return 0;
    }

    // If the value of N is one or two return 1
    if( N == 1 || N == 2)
    {
       return 1;
    }

    // Keep track of the fibonacci values for N-1 and N-2
    int N_1 = 1;
    int N_2 = 1;

    // From the bottom-up calculate all the fibonacci values until you 
    // reach the N-1 and N-2 values of the target Fibonacci(N)
    for(int i =3; i < N; i++)
    {
       int temp = N_2;
       N_2 = N_2 + N_1;
       N_1 = temp;
    }

    return N_1 + N_2; 
}
-1

Possible solution:

a=0
b=1
d=[a,b]
n=int(input("Enter a number"))
i=0
while len(d)<n:
    temp=a+b
    d.append(temp)
    a=temp
    b=d[i+1]
    i+=1
print("Fibonacci series of {} is {}".format(n,d))  
1
  • How does this answer did I not implement it right ?
    – greybeard
    Commented Aug 20, 2019 at 15:44
-3
import time

a,b=0,1
def fibton(n):
    if n==1:
        time.clock()
        return 0,time.clock()
    elif n==2:
        time.clock()
        return 1,time.clock()
    elif n%2==0:
        read="b"
    elif n%2==1:
        read="a"
    else:
        time.clock()
        for i in range(1,int(n/2)):
            a,b=a+b,a+b
        if read=="b":
            return b,time.clock()
        elif read=="a":
            return.a,time.clock()

Disclaimer: I am currently on a mobile device and this may not be totally correct

This algorithm utilizes a gap in some other peoples' and now it is literally twice as fast. Instead of just setting b equal to a or vice versa and then setting a to a+b, I do it twice with only 2 more characters. I also added speed testing, based off of how my other iterative algorithm went. This should be able to go to about the 200,000th Fibonacci number in a second. It also returns the length of the number instead of the whole number, which would take forever.

My other one could go to the second Fibonacci number, as indicated by the built in clock: in 10^-6 seconds. This one can do it in about 5^-6. I'm going to get some more advanced algorithms soon and refine them for utmost speed.

1
  • What is this supposed to do and how? My python environment doesn't seem to have more clues than I.
    – greybeard
    Commented Jan 5, 2017 at 10:35

Not the answer you're looking for? Browse other questions tagged or ask your own question.