Welcome, guest | Sign In | My Account | Store | Cart

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.

Python, 64 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64``` ```def A001511(): '''Sequence of moves to solve Towers of Hanoi; has many other interpretations. For more info see http://www.research.att.com/projects/OEIS?Anum=A001511''' yield 1 for x in A001511(): yield x+1 yield 1 def A003714(): '''Fibbinary numbers (no consecutive ones in binary representation). For more info see http://www.research.att.com/projects/OEIS?Anum=A003714''' yield 1 for x in A003714(): yield 2*x if not (x & 1): yield 2*x+1 def A005836(): '''Numbers with no 2 in their ternary representation; discrete Cantor set; lexicographically first arithmetic-progression-free sequence of integers. For more info see http://www.research.att.com/projects/OEIS?Anum=A005836''' yield 0 for x in A005836(): if x: yield 3*x yield 3*x+1 def A006068(): '''Inverse Gray code; each n occurs at position n^(n>>1) of the sequence. For more info see http://www.research.att.com/projects/OEIS?Anum=A006068''' yield 0 for x in A006068(): if x & 1: yield 2*x+1 yield 2*x else: if x: yield 2*x yield 2*x+1 def A010060(): '''Thue-Morse sequence; binary sequence with no triply-repeated block. For more info see http://www.research.att.com/projects/OEIS?Anum=A010060''' yield 0 omit = 1 for x in A010060(): if x: yield 1 yield 0 else: if not omit: yield 0 yield 1 omit = 0 def A036561(): '''Numbers of the form 2^i 3^j, sorted according to the order of the tuples (i+j,j). For more info see http://www.research.att.com/projects/OEIS?Anum=A036561''' yield 1 for x in A036561(): yield 2*x if x & 1: yield 3*x ```

The sequence names and reference URLs are all from Neil Sloane's online Encyclopedia of Integer Sequences. David Eppstein (author) 18 years, 2 months ago

Another one.

``````def A000069():
'''Odious numbers: numbers with an odd number of ones in their binary representation.
yield 1
for x in A000069():
if x &amp; 1 and x &gt; 1:
yield 2*x - 1
yield 2*x
if not (x &amp; 1):
yield 2*x + 3
`````` Bob Hossley 15 years, 10 months ago

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).
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
LoopCnt = 0
LoopCnt = 0
else:
LoopCnt += 1
`````` Bob Hossley 15 years, 10 months ago

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).
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 &amp; 1):
yield 2*x+1
`````` Bob Hossley 15 years, 10 months ago

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. Created by David Eppstein on Sat, 13 Sep 2003 (PSF)

### Required Modules

• (none specified)