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)