19.3. Generating the Fibonacci Sequence

Credit: Tom Good, Leandro Mariano Lopez

. Problem

You want an unbounded generator that yields, one item at a time, the entire (infinite) sequence of Fibonacci numbers.

. Solution

Generators are particularly suitable for implementing infinite sequences, given their intrinsically "lazy evaluation" semantics:

def fib( ):
    ''' Unbounded generator for Fibonacci numbers '''
    x, y = 0, 1
    while True:
        yield x
        x, y = y, x + y
if _ _name_ _ == "_ _main_ _":
    import itertools
    print list(itertools.islice(fib( ), 10))
# outputs: [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

. Discussion

Generators make it quite easy to work with unbounded (infinite) sequences. In this recipe, we show a generator that produces all of the (infinitely many) Fibonacci numbers one after the "other". (If you want the variant in which the sequence starts with 1, 1, 2, . . . , rather than the one, implemented here, which starts with 0, 1, 1, . . . , just interchange the two statements in the loop's body.)

It's worth reflecting on why a generator is so perfectly suitable for implementing an unbounded sequence and letting you work with it. Syntactically, a generator is "just" a function containing the keyword yield. When you call a generator, however, the function body does not yet execute. Rather, calling the generator gives you a special anonymous iterator object that wraps the function's body, the function's local variables (including arguments, which, for any function, 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 anonymous iterator object's next method, the function body executes up to the next yield statement. 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, the function "thaws" and continues from where it left off, again up to the next yield statement.

If the function body "falls off the end", or executes a return, the iterator object raises StopIteration to indicate the end of the sequence. But, of course, if the sequence that the generator is producing is not bounded, the iterator never raises StopIteration. That's okay, as long as you don't rely on such an exception as the only way to terminate a loop. In this recipe, for example, the anonymous iterator object is passed as an argument to itertools.islice: as shown in Recipe 19.2, islice is the most typical way in which an unbounded iterator is made finite (truncated at an externally imposed boundary).

The main point to retain is that it's all right to have infinite sequences represented by generators, since generators are computed lazily (in other words, each item gets computed just in time, when required), as long as some control structure ensures that only a finite number of items are required from the generator. The answer to our curiosity as to why generators are so excellently suitable for this use is in the anonymous iterator object which a generator returns when we call it: that anonymous iterator wraps some code (the generator's function body) and some state (the function's local variables, and, crucially, the point at which the function's execution is to resume) in just the way that's most convenient for the computation of most sequences, be they bounded or unbounded.

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. Although his most notable contributions were the introduction of decimal notation (arabic numerals) in the West, and the codification of the rules for double-entry bookkeeping, these monumental achievements are not usually connected to his name. The one that is, however—from 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.

. See Also

Recipe 19.2, shows how to make bounded iterators from unbounded (or "potentially unbounded") ones.