ActiveState Code

For a function without arguments, calling itself recursively is a quick way to get into an infinite loop. But for a generator, it can actually be useful...here are some simple numerical examples.

Comments

1. 1. At 6:04 p.m. on 14 sep 2003, David Eppstein (the author) said:

   Another one.

   def A000069():
       '''Odious numbers: numbers with an odd number of ones in their binary representation.
   For more info, see http://www.research.att.com/projects/OEIS?Anum=A000069'''
       yield 1
       for x in A000069():
           if x & 1 and x > 1:
                   yield 2*x - 1
           yield 2*x
           if not (x & 1):
               yield 2*x + 3
   

2. 2. At 8:24 a.m. on 19 jan 2006, Bob Hossley said:

   Non-Recursive A003714(). A003714() fascinates me because I don't understand how it works. But I do understand

   a little about its execution. It causes the "yield stack" depth to grow without bound.

   When calculating the nth Fibbinary number the "yield stack" depth for A003714() is

   approximately the log base 2 of n. For my own amusement I eliminated the recursion and

   hence the unbounded "yield stack" as follows:

   def A003714nr():
       """
       Fibbinary numbers (no consecutive ones in binary representation).
       For more info see   http://www.research.att.com/projects/OEIS?Anum=A003714
       http://www.research.att.com/~njas/sequences/A003714
   
       2006/01/09 M - 2006/01/12 Th Bob Hossley
       Eliminate recursion and the "yield stack" depth growing without bound.
       When calcuating the nth Fibbinary number the "yield stack" depth for
       A003714() is approximately the log base 2 of n.
   
       The algorithm used by A003714nr() is simple:  Begin with 0.  To calculate
       the next integer in the Fibbinary sequence, add 1 to the previous Fibbinary
       number.  Then skip all non-Fibbinary numbers by adding 2**n
       whenever the result contains ones in positions 2**n and 2**(n+1).  Because
       the previous Fibbinary number is guaranteed not to have consecutive one's
       in its binary representaion, the consecutive ones check can stop as soon
       as three consecutive binary digits are encountered that do not contain two
       consecutive ones.
   
       Generator context saving preserves local variables Last, LoopCnt, Mask1,
       and Mask2 between yield and continue from yield but only variable Last
       needs to be preserved.
       """
   
       Last = 0
       LoopCnt = 2
       while (1):
           if (LoopCnt > 1):
               yield Last
               Last += 1
               Mask1 = 1
               Mask2 = 2
               LoopCnt = 0
           if (Last & Mask1) and (Last & Mask2):
               Last += Mask1
               LoopCnt = 0
           else:
               LoopCnt += 1
           Mask1 *= 2
           Mask2 *= 2
   

3. 3. At 8:32 a.m. on 19 jan 2006, Bob Hossley said:

   A003714() and the zeroth Fibbinary number. A003714() skips the zeroth Fibbinary number, which is zero.

   I modified A003714()to make it return the zeroth Fibbinary number.

   This is an inelegant kludge:

   def A003714x():
       """
       Fibbinary numbers (no consecutive ones in binary representation).
       For more info see http://www.research.att.com/projects/OEIS?Anum=A003714
       http://www.research.att.com/~njas/sequences/A003714
   
       2006/01/17 Bob Hossley
       Change:  Return A(0) = 0.
       """
   
       try:
           A003714x.A0
       except AttributeError:
           A003714x.A0 = True
           yield 0
   
       yield 1
       for x in A003714x():
           yield 2*x
           if not (x & 1):
               yield 2*x+1
   

4. 4. At 10:13 a.m. on 20 jan 2006, Bob Hossley said:

   A003714x() Bug. A003714x() only includes A(0) in the first sequence it generates.

   This bug can be worked around in the code that uses A003714x() by deleting the

   control variable between each use of A003714x(). For example:

   loops = 0
   for seqVal in A003714x():
       print "Fibbinary(", loops, ")=", seqVal
       loops += 1
       if (loops > 10): break
   
   del A003714x.A0 # Kludge to delete control variable
   loops = 0
   for seqVal in A003714x():
       print "Fibbinary(", loops, ")=", seqVal
       loops += 1
       if (loops > 10): break
   

   But this does not a fix the bug. I don't know how to change A003714()

   to include A(0) in the sequence. I don't allow adding a function argument to

   A003714(). The "yield statement" magic hides the generator initialization.

   If I knew how to rewrite A003714() without yield statements, then I would use

   itertools and the generator initialization would be exposed. I would initialize

   a control variable in the generator initialization and this problem would solved.

   But at this time, I have no solution.

Sign in to comment

Tags

• algorithms