Python Cookbook

Generating the Fibonacci Sequence

Credit: Tom Good

Problem

You need to implement a Python 2.2 generator for an infinite sequence, for example, the Fibonacci sequence.

Solution

Python 2.2’s generators provide a wonderful way to implement infinite sequences, given their intrinsically lazy-evaluation semantics:

from _ _future_ _ import generators

def fib(  ):
    "unbounded generator, creates Fibonacci sequence"
    x = 0
    y = 1
    while 1:
        x, y = y, x + y
        yield x

if _ _name_ _ == "_ _main_ _":
    g = fib(  )
    for i in range(9):
        print g.next(  ),
    print

Discussion

Python 2.2 generators let you work with infinite (unbounded) sets. As shown in this recipe, it is easy to create a generator that produces the Fibonacci sequence. Running the recipe’s script produces the following result:

c:\python22> python fib.py
1 1 2 3 5 8 13 21 34

In Python 2.2, if you start your module with the statement from _ _future_ _ import generators, yield becomes a keyword. (In 2.3 and later versions of Python, yield will always be a keyword; the “import from the future” statement lets you use it in 2.2, but only when you specifically request it.)

A generator is a function containing the keyword yield. When you call a generator, the function body does not execute. Rather, calling the generator gives you a special iterator object that wraps the function’s body, the set of its local variables (including the arguments, which are local variables that happen to be initialized by the caller), and the current point of execution, which is initially ...