Python Cookbook 2Nd Edition Jun 1002005 [Electronic resources] نسخه متنی

Recipe 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, howeverfrom
the third problem in his Liber Abaci, which he
originally expressed in terms of a rabbit-raising farmstill
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.