Archive

Posts Tagged ‘fibonacci’

Generators

October 19, 2010 Leave a comment

Generators are a simple and powerful tool for creating iterators. They are written like regular functions but use the yield statement whenever they want to return data. Each time next() is called, the generator resumes where it left-off (it remembers all the data values and which statement was last executed).”

Let’s rewrite our Fibonacci function using generators. In the previous approach, we specified how many Fibonacci numbers we want to get. The function calculated all of them and returned a list containing all the elements. With generators, we can calculate the numbers one by one. The new function will calculate a number, return it, and suspend its execution. When we call it again, it will resume where it left off and it runs until it computes another number, etc.

First let’s see a Fibonacci function that calculates the numbers in an infinite loop:

#!/usr/bin/env python

def fib():
    a, b = 0, 1
    while True:
        print a    # the current number is here
        a, b = b, a+b

fib()

In order to rewrite it in the form of a generator, we need to locate the part where the current value is calculated. This is the line with print a. We only need to replace this with yield a. It means that the function will return this value and suspend its execution until called again.

So, with generators it will look like this:

#!/usr/bin/env python

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

f = fib()
for i in range(10):    # print the first ten Fibonacci numbers
    print f.next(),    # 0 1 1 2 3 5 8 13 21 34

It is also possible to get a slice from the values of a generator. For instance, we want the 5th, 6th, and 7th Fibonacci numbers:

#!/usr/bin/env python

from itertools import islice

def fib():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

for i in islice(fib(), 5, 8):
    print i    # 5 8 13

More info on islice is here. For this post I used tips from here.

Update (20110406)

Here is a presentation in PDF entitled “Generator Tricks For Systems Programmers” by David Beazley (presented at PyCon 2008). (Reddit thread is here.)

Fibonacci numbers

September 28, 2010 1 comment

Exercise

Now an easy one. Calculate the first N Fibonacci numbers, where F0 = 0, F1 = 1, …, Fn = Fn-1 + Fn-2. Write a function that receives N as a parameter and returns a list with the first N Fibonacci numbers. Example: fib(10) would produce [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]. Notice that F0 = 0 is included in the result.

Solution

#!/usr/bin/env python

# fibonacci.py

def fib(n):
    assert(n >= 0)
    li = []
    a, b = 0, 1
    for i in range(n+1):
        li.append(a)
        a, b = b, a+b
    return li
            
if __name__ == "__main__":
    print fib(10)

Here we solved the problem in an iterative way, but you can do it with recursive calls too.

Links
See http://www.scriptol.com/programming/fibonacci.php for a comprehensive list how to implement it in any language.

Categories: python Tags: ,