20

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

greybeard
  • 2,249
  • 8
  • 30
  • 66
Ris
  • 1,892
  • 9
  • 26
  • 43
  • A [post](https://stackoverflow.com/a/8532405/465053) worth looking at if you are interested in complexity of your algorithm for Fibonacci series. – RBT Aug 10 '17 at 06:52

13 Answers13

69

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
poke
  • 369,085
  • 72
  • 557
  • 602
  • 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 ? – Adelin Jul 19 '15 at 15:52
  • 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](http://codereview.stackexchange.com/) for review of your code. That being said, your array size is wrong for `limit=1` which will give you an index exception. – poke Jul 19 '15 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 Dec 04 '16 at 16:13
  • 2
    @eton_ceb That depends on your definition of the [Fibonacci sequence](https://en.wikipedia.org/wiki/Fibonacci_number). I usually start the sequence with `0` and `1` instead of `1` and `1`. – poke Dec 04 '16 at 16:59
  • 2
    You can ignore `i` and just write `for _ in range(n)` – Florimond Jul 06 '19 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. – Ng Sek Long May 27 '21 at 04:27
  • Works fine. When the sequence starts from 0, the second line should be: `a,b=1,0` – bergee Mar 08 '22 at 15:15
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.

KebertX
  • 304
  • 1
  • 6
  • 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 Feb 24 '13 at 00: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 Mar 11 '14 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? – Halcyon Abraham Ramirez Jun 23 '15 at 03: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 Jan 05 '17 at 10:27
  • This is a recursive solution, original question is looking for an iterative solution – Maksood Oct 13 '20 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

Community
  • 1
  • 1
John Hornsby
  • 321
  • 1
  • 10
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
Community
  • 1
  • 1
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
MsO
  • 87
  • 1
  • 13
  • 1
    Does this answer `did I not implement it right ? `? (I find [poke's code](http://stackoverflow.com/a/15047141/3789665) intuitive, and "counting down `n` _by hand_" irritating.) – greybeard Jan 05 '17 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 Jun 03 '17 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 Jun 03 '17 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 Jun 08 '17 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.

  • 1
    I don't see the improvement over ["the `a`-`b`-formulation"](http://stackoverflow.com/a/15047141/3789665). `fastest way` you are aware of [approaches using _O(log_ n) iterations](http://stackoverflow.com/a/1526036/3789665)? – greybeard Jan 06 '17 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 Jan 07 '17 at 05: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]

karuna
  • 59
  • 1
  • 2
  • 1
    Does this answer `did I not implement it right ?` ? – greybeard Apr 11 '17 at 08: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 Apr 17 '17 at 11:25
  • I don't have output. I happen to know [OEIS A000045](http://oeis.org/A000045), and to be the one to try and improve the presentation of a 2013/2 question in '17/1. – greybeard Apr 17 '17 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))
Zoe
  • 27,060
  • 21
  • 118
  • 148
Loki
  • 33
  • 1
  • 9
  • 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 `n`th 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 Aug 20 '19 at 01: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; 
}
yadriel
  • 49
  • 4
-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))  
Zoe
  • 27,060
  • 21
  • 118
  • 148
Loki
  • 33
  • 1
  • 9
-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.

RedBaron
  • 4,717
  • 5
  • 41
  • 65
tony
  • 1