Python function for generating the nth number of Stern's diatomic series recursively

readme.md

See The oddest numbers

Sanity check:

In [1]: print [fusc(x) for x in range(92)]
[0, 1, 1, 2, 1, 3, 2, 3, 1, 4, 3, 5, 2, 5, 3, 4, 1, 5, 4, 7, 3, 8, 5, 7, 2, 7, 5, 8, 3, 7, 4, 5, 1, 6, 5, 9, 4, 11, 7, 10, 3, 11, 8, 13, 5, 12, 7, 9, 2, 9, 7, 12, 5, 13, 8, 11, 3, 10, 7, 11, 4, 9, 5, 6, 1, 7, 6, 11, 5, 14, 9, 13, 4, 15, 11, 18, 7, 17, 10, 13, 3, 14, 11, 19, 8, 21, 13, 18, 5, 17, 12, 19]

matches the Encyclopedia of Integer Sequences A002487 Stern's diatomic series (or Stern-Brocot sequence)

Sanity check:

a = calkin_wilf()
print([a.next() for x in range(50)])
[(1, 1), (1, 2), (2, 1), (1, 3), (3, 2), (2, 3), (3, 1), (1, 4), (4, 3), (3, 5), (5, 2), (2, 5), (5, 3), (3, 4), (4, 1), (1, 5), (5, 4), (4, 7), (7, 3), (3, 8), (8, 5), (5, 7), (7, 2), (2, 7), (7, 5), (5, 8), (8, 3), (3, 7), (7, 4), (4, 5), (5, 1), (1, 6), (6, 5), (5, 9), (9, 4), (4, 11), (11, 7), (7, 10), (10, 3), (3, 11), (11, 8), (8, 13), (13, 5), (5, 12), (12, 7), (7, 9), (9, 2), (2, 9), (9, 7), (7, 12)]

Maybe it should output using fractions module?

Similar: Python implementation of the Gibbons-Lester-Bird algorithm[1] for enumerating the positive rationals

fusc.py

def fusc(n):
    """Return the nth number of Stern's diatomic series recursively"""
    
    if n == 0 or n == 1:
        return n
    elif n > 0 and n % 2 == 0: # even
        return fusc(n // 2)
    elif n > 0 and n % 2 == 1: # odd
        return fusc((n - 1) // 2) + fusc((n + 1) // 2)
    else:
        raise ValueError ('Input must be a positive integer')


def calkin_wilf():
    """Generate the Calkin-Wilf sequence of rational numbers
    
    Output is tuples of (numerator, denominator)

    """
    n = 1
    d = 1
    yield (n, d)
    while True:
        n, d = d, 2 * (n // d) * d + d - n
        yield (n, d)

Any idea why your generator for the Calkin-Wilf sequence is so much faster than mine here?

The millionth rational number in the sequence is [191, 1287], and it takes mine about 15 seconds to find that out, while yours is sub-second. I'm confused because both seem to be based on:

Would use of the fractions module slow down performance that significantly?

@rosemichaele i think the issue is division, I didn't use Fractions but my was also slow until i eliminated division operation.