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.

4 comments

David Eppstein (author) 20 years, 7 months ago  # | flag

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
Bob Hossley 18 years, 3 months ago  # | flag

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
Bob Hossley 18 years, 3 months ago  # | flag

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
Bob Hossley 18 years, 3 months ago  # | flag

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)
Python recipes (4591)
David Eppstein's recipes (14)

Required Modules

  • (none specified)

Other Information and Tasks