17.11 Generating the Fibonacci Sequence

Credit: Tom Good

17.11.1 Problem

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

17.11.2 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

17.11.3 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 the start of the function.

When you call this iterator object's next method, the function body executes up to the next yield statement. Then yield's argument is returned as the result of the iterator's next method, and the function is frozen with its execution state intact. When you call next again on the same iterator object, execution of the function body continues from where it left off, again up to the next yield statement to execute.

If the function body falls off the end or executes a return statement, the iterator object raises a StopIteration to indicate the end of the sequence. But, of course, if the sequence that the generator is producing is not bounded, the iterator will never raise a StopIteration. That's okay, as long as you don't rely on this as the only way to terminate a loop. In this recipe, for example, the loop's termination is controlled by an independent counter i, so the fact that g would never terminate is not a problem.

The main point to keep in mind is that it's all right to have infinite sequences represented by generators, since generators are computed lazily (in which each item is computed just in time), as long as a control structure ensures that only a finite number of items are required from the generator.

Leonardo Pisano (meaning "from Pisa"), most often called Leonardo Bigollo ("the traveler" or "the good for nothing") during his lifetime in the 12th and 13th centuries, and occasionally Leonardo Fibonacci (for his connection to the Bonacci family), must look down with considerable pride from his place in the mathematicians' Empyreon. The third problem in his Liber Abaci, which he originally expressed in terms of a rabbit-raising farm, still provides interesting applications for the distant successors of the abacus, modern computers.

17.11.4 See Also

Recipe 17.12 shows one approach to restriction (filtering) of potentially unbounded iterators (and thus, as a special case, generators).