#!/usr/bin/env python3
# generate.py
# Glenn G. Chappell
# 1 Feb 2013
#
# For CS 321 Spring 2013
# Example of coroutines in Python
# Requires Python 3.0 or later
# ----------------------------------------------------------------------
# Standard iterative computation of Fibonacci numbers.
#
# Fibonacci computation function is called in a loop.
#
# NOTE: The following two functions are not currently called when this
# file is executed.
# ----------------------------------------------------------------------
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 range(n): # i = 0, 1, 2, ..., n-1
newfib = prev + curr
prev = curr
curr = newfib
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 each value 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.
#
# A nicer 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. Each value is not computed until it is requested.
# ----------------------------------------------------------------------
def fibos_gen():
"""Generator. Yield Fibonacci numbers 0, 1, 1, 2, 3, 5, ...."""
prev = 1
curr = 0
yield curr
while True:
newfib = prev + curr
prev = curr
curr = newfib
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 call the more inefficient form; they are commented out
#print "Fibonacci numbers:"
#print_fibos()