An iterative algorithm for Fibonacci numbers

python algorithm fibonacci

101,771

Solution 1

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

Solution 2

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.

Solution 3

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

101,771

Ris

Updated on July 09, 2022

Comments

Ris almost 2 years
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
- RBT over 6 years
  
  A post worth looking at if you are interested in complexity of your algorithm for Fibonacci series.
poke about 11 years

(wherever those curly braces came from… from __future__ import braces? :P)
poke about 11 years

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.
rbp about 10 years

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.
Halcyon Abraham Ramirez almost 9 years

@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?
Adelin almost 9 years

public int[] get(int limit) { int[] elements = new int[limit]; if (limit == 0) { return null; } elements[0] = 1; elements[1] = 1; for (int i = 2; i < limit; i++) { elements[i] = elements[i - 2] + elements[i - 1]; } return elements; } Can you verify this one ?
poke almost 9 years

@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.
eton_ceb over 7 years

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
poke over 7 years

@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.
greybeard over 7 years

@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 over 7 years

What is this supposed to do and how? My python environment doesn't seem to have more clues than I.
greybeard over 7 years

Does this answer did I not implement it right ? ? (I find poke's code intuitive, and "counting down n by hand" irritating.)
greybeard over 7 years

I don't see the improvement over "the a-b-formulation". fastest way you are aware of approaches using O(log n) iterations?
digitect38 over 7 years

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?
greybeard about 7 years

Does this answer did I not implement it right ? ?
karuna about 7 years

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
greybeard about 7 years

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.
MsO almost 7 years

@greybeard Who's asking did I not implement it right? ? (what's wrong counting down, Python allows it why not use it?!)
greybeard almost 7 years

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.
MsO almost 7 years

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...
Florimond almost 5 years

You can ignore i and just write for _ in range(n)
Blckknght over 4 years

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.
greybeard over 4 years

How does this answer did I not implement it right ?
Maksood over 3 years

This is a recursive solution, original question is looking for an iterative solution
Ng Sek Long almost 3 years

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.
bergee about 2 years

Works fine. When the sequence starts from 0, the second line should be: a,b=1,0