9.3.4 Generators of recursive sequences

Assume that a sequence is given by an induction formula. For instance, consider the Fibonacci sequence, defined by the recurrence formula: 

.

This sequence depends on two initial values, namely  and , although for the standard Fibonacci sequence those numbers are taken as 0 and 1 respectively. A nifty way of programming the generation of such a sequence is by using generators, as follows:

def fibonacci(u0, u1):
    """
    Infinite generator of the Fibonacci sequence.
    """
    yield u0
    yield u1
    while True:
        u0, u1 = u1, u1 + u0  
        # we shifted the elements and compute the new one
        yield u1

This may then be used, for instance, like this:

# sequence of the 100 first Fibonacci numbers:
list(itertools.islice(fibonacci(0, 1), 100))