#!/usr/bin/env python
# generate.py
# Glenn G. Chappell
# 3 Feb 2012
#
# For CS 321 Spring 2012
# Example of coroutines in Python
# ----------------------------------------------------------------------
# Standard iterative computation of Fibonacci numbers.
#
# Fibonacci computation function is called in a loop.
#
# NOTE: The following two functions are not currently called.
# ----------------------------------------------------------------------
def fibo(n):
"""Return F(n), the nth Fibonacci number.
F(0) = 0. F(1) = 1. For n >= 2, F(n) = F(n-2)+F(n-1).
"""
prev = 1
curr = 0
for i in xrange(n): # i = 0, 1, 2, ..., n-1
next = prev + curr
prev = curr
curr = next
return curr
def print_fibos():
"""Print first 20 Fibonacci numbers, each on a separate line."""
for n in xrange(20): # n = 0, 1, 2, ..., 19
print fibo(n)
# ----------------------------------------------------------------------
# The above is inefficient, since computing fibo(19) requires computing
# all previous Fibonacci numbers. These were already computed and
# printed, but not saved.
#
# One way to deal with this would be to print the numbers inside the
# computation loop. But that makes the function less versatile. Another
# would be to save the computed numbers in a data structure. But that
# takes storage, as well as extra code to create the storage, save
# the values, and then check for them when they are requested.
#
# Another way is to use a coroutine, which Python makes available in the
# form of "generators": functions that can "yield" a value. Yielding is
# like returning, except that the function can then be restarted from
# the point just after the yield. Such a function actually returns an
# iterator; the yielded values can be obtained using a standard loop
# construction.
# ----------------------------------------------------------------------
def fibos_gen():
"""Generator. Return Fibonacci numbers 0, 1, 1, 2, 3, 5, ...."""
prev = 1
curr = 0
yield curr
while True:
next = prev + curr
prev = curr
curr = next
yield curr
def print_fibos_from_generator():
"""Print first 20 Fibonacci numbers, each on a separate line.
Same as print_fibos, but uses a generator function.
"""
count = 0
for f in fibos_gen():
print f
count += 1
if count >= 20:
break
# ----------------------------------------------------------------------
# Call function to print Fibonacci numbers.
# ----------------------------------------------------------------------
print "Fibonacci numbers (computed by generator):"
print_fibos_from_generator()
# Lines below are commented out
#print "Fibonacci numbers:"
#print_fibos()