How to create a generator with recursion?

Question

Algorithm from Hacker's Delight 2nd Edition

Ported to python

A simple Hilbert curve class.

class Hilbert():

    def __init__(self,order=1):
            
            self.x = -1 
            self.y = 0     
            self._step(0)
            self._hil(0, 1, order)
    
    def _hil(self, dirs, rot, order):
        if (order == 0): 
            return

        dirs += rot
        self._hil(dirs, -rot, (order-1))
        self._step(dirs)
        dirs -= rot
        self._hil(dirs, rot, (order-1))
        self._step(dirs)
        self._hil(dirs, rot, (order-1))
        dirs -= rot
        self._step(dirs)
        self._hil(dirs, -rot, (order-1))
         
        
    def _step(self, dirs):
        dirs %= 4
        
        if dirs == 0:
            self.x += 1
        elif dirs == 1:
            self.y += 1
        elif dirs == 2:
            self.x -= 1
        else:
            self.y -= 1 
        #prints all points 
        #print(self.x,self.y)
        #Could I "iterate" from here.

So what I want is something that gives a (x,y) every time next() is called. I tried doing this myself but can't get it to work so any help would be appreciated. Would I have to rewrite this to work with a generator? Source

Answer 1

I think at least part of what you're trying to do is to turn _hil into a generator function, which yields the x, y pairs after each call to _step? If so, that's pretty easy.

The hard part is those recursive calls. But that's not really hard at all. That's exactly what yield from is for:* Take some iterator (like a recursive call to a generator function) and yield each of its values.**

Then there's the easy part, the non-recursive yielding of the x, y pairs after each call to _step. You can do that with an explicit yield self.x, self.y after each call. Or you can change _step to add a return self.x, self.y, so you can just yield self._step(dirs). But you can also change _step to an iterator that only iterates one value, and then you can yield from it as well. (There's no real advantage to that here, but I think it's worth showing so you can think through how it works—especially since you asked "can I iterate from here?" in _step.)

def _hil(self, dirs, rot, order):
    if (order == 0): 
        return

    dirs += rot
    yield from self._hil(dirs, -rot, (order-1))
    yield from self._step(dirs)
    dirs -= rot
    yield from self._hil(dirs, rot, (order-1))
    yield from self._step(dirs)
    yield from self._hil(dirs, rot, (order-1))
    dirs -= rot
    yield from self._step(dirs)
    yield from self._hil(dirs, -rot, (order-1))

def _step(self, dirs):
    # existing code
    yield self.x, self.y

---

But now you've got that __init__ that just calls _hil and does nothing with the result. That's not very useful. Maybe you're trying to turn the Hilbert class itself into an iterator class?

In that case, the easiest thing to do is store the generator iterator and delegate to it:

def __init__(self, order=1):
    self.x = -1 
    self.y = 0     
    self._step(0)
    self.iter = self._hil(0, 1, order)

def __iter__(self):
    return self

def __next__(self):
    return next(self.iter)

---

However, at this point, I'm not sure why you need this to be a class at all. The x and y aren't really part of the object's state, they're part of the generator state, which Python would take care of magically if you just used local variables in _hil (and normal parameter-and-return passing in _step). And the only other state is self.iter, which is only necessary because you're writing a class instead of a function.

---

_{* Actually, it turns out to be good for a lot more than that, as Greg Ewing describes amazingly well; we wouldn't have asyncio without it. But the original reason for adding it to the language was as "Syntax for Delegating to a Subgenerator".}

** Note that this only works if you have yield from—meaning Python 3.3 or later. If you're still using Python 2.x, and yield from isn't enough to get you to upgrade, you can simulate some uses of it—including this one—by changing every yield from eggs into for egg in eggs: yield egg. It won't be as readable, and it will be significantly slower, but it will work.