Using Python Generators (a recursion example)

Recursion is a powerful programming tool, but also a tricky one. Knowing what’s going on in a recursive function at the various frame levels can be difficult which makes debugging recursive functions challenging.

So below is a code snippet that uses recursion to find the largest odd factor of an input integer, and returns the number of recursions required to find it. You can easily do this with print statements, but I am using a cleaner approach, and one that demonstrates a little more about what you can do with generators

import sys

Starting here with a lambda function. This will return a (1,0  => True, False) when sent an integer.

odd = lambda x: x % 2

Here now is our generator function. It is an unterminated while loop that increments after the yield.

def counter(c=0):
   while True:
       yield c
       c += 1

Next is the recursion function. It takes arguments of the value to factor and the counter object.

def odd_factor(n,c=counter):
     count = next(c)
     if odd(n) or n==2:
         return n        # recursion bottom
     else:
         n = odd_factor(n/2, c)
    return n

Finally, here is the main block. In the first line the counter is initialized, and then passed to the the recursion routine as an argument. In the last line the iterations are checked by calling next and then subtracting one. This is because there is no way to check the current value of the generator.

if __name__ == "__main__":
    c = counter()
    out = odd_factor(int(sys.argv[1]), c)
    if out == 2:
          print "The value %s is a power of 2 - no odd factors." % (sys.argv[1])
    else:
         print "The largest odd factor of %s is: %s" % ( sys.argv[1], out)
    print "Iterations: %s" % (next(c)-1)

Not only does this demonstrate the use of a generator in an interesting context, it also illustrates something of python’s (unusual) variable passing strategy. The counter object reference is established and recorded in the main block (as c), but it is never returned after it is modified in the recursion routine. This would make you think that python was a pass-by-reference language, because it acts like one in this case. However python is neither a pass-by-reference or pass-by-value language. For simple applications you can get away with not knowing or caring how variable passing works in python, but for more advanced applications you should start getting to understand it.

Here is the whole thing for copy and pasting:


import sys

odd = lambda x: x % 2

def counter(c=0):
   while True:
       yield c
       c += 1

def odd_factor(n,c=counter):
     count = next(c)
     if odd(n) or n==2:
         return n        # recursion bottom
     else:
         n = odd_factor(n/2, c)
    return n

if __name__ == "__main__":
    c = counter()
    out = odd_factor(int(sys.argv[1]), c)
    if out == 2:
          print "The value %s is a power of 2 - no odd factors." % (sys.argv[1])
    else:
         print "The largest odd factor of %s is: %s" % ( sys.argv[1], out)
    print "Iterations: %s" % (next(c)-1)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s