Clever streams-based python program doesn't run into infinite recursion

Question

I was playing around with clever ways to create a python generator for sequence A003602

This appears to work, but I can't figure out why. It seems to me like it should hit infinite recursion. Is python doing some lazy evaluation somewhere that I don't recognize?

def N():
    i=1
    while True:
        yield i
        i+=1

def interleave(a,b):
    def result():
        x=a()
        y=b()
        while True:
            yield next(x)
            yield next(y)
    return result

def RZ():
    return interleave(N,RZ)()

gen=RZ()

To me it seems like since RZ instantly calls the method returned by interleave which in turn calls b which is RZ (before the first call to yield), this should be infinite recursion. But this actually seems to work. Can anyone explain why?

Answer 1

Generators (any function with a yield statement) are lazy. This means that result() will not start processing until you request the first value from it, which you don't do.

The root cause here is that you ask for a value from x first. This means that the generator never gets to asking it's child generator until at least the second value asked for. Consider the simpler example:

def test():
    yield 1
    a = test()
    while True:
        yield next(a)

a = test()
for i in range(10):
    print(next(a))

This works, just as yours does. It has the potential for infinite recursion, but will only get that far if you ask for that many values. All you have to do is remove the yield 1 to get the expected behaviour. In yours, just switch N and RZ and ask for the next value - you will get the expected recursion.