#!/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()