Simple Recursive Generator Question

[Christian Tismer]

MetalOne wrote:

> I am trying to write a generator function that yields the index position
> of each set bit in a mask.
> e.g. 
> for x in bitIndexGenerator(0x16): #10110
>     print x
> --> 1 2 4
> 
> 
> This is what I have, but it does not work.
> Changing yield to print, shows that the recursion works correctly.
> 
> def bitIndexGenerator(mask, index=0):
>     if mask == 0: return
>     elif mask & 0x1: yield index
>     bitIndexGenerator(mask >> 1, index+1)
> 
> What am I missing?

Your recursive generator is yielding to itself,
but not taking its result. Recursion does not
make sense with generators, since they can yield
only one level up.

The above would work pretty fine with a Stackless
tasklet.

Here is a recursion solution, but be warned, this
is really really inefficient, since it has quadratic
behavior due to the repeated recursion activation:

def bitIndexGenerator(mask, index=0):
     if mask == 0: return
     elif mask & 0x1: yield index
     for each in bitIndexGenerator(mask >> 1, index+1):
         yield each

An interative version is easy and adequate here.

def bitIndexGenerator(mask):
     index = 0
     while mask:
         if mask & 0x1: yield index
         mask >>= 1
         index += 1

-- 
Christian Tismer             :^)   <mailto:tismer at tismer.com>
Mission Impossible 5oftware  :     Have a break! Take a ride on Python's
Johannes-Niemeyer-Weg 9a     :    *Starship* http://starship.python.net/
14109 Berlin                 :     PGP key -> http://wwwkeys.pgp.net/
work +49 30 89 09 53 34  home +49 30 802 86 56  mobile +49 173 24 18 776
PGP 0x57F3BF04       9064 F4E1 D754 C2FF 1619  305B C09C 5A3B 57F3 BF04
      whom do you want to sponsor today?   http://www.stackless.com/