如何使用递归创建生成器？

Question

黑客之乐第二版算法

移植到python

一个简单的希尔伯特曲线类。你知道吗

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.

所以我想要的是每次调用next（）时都给出a（x，y）的东西。我试着自己做这个，但无法让它工作，所以任何帮助将不胜感激。我需要重写这个才能和发电机一起工作吗？ Source

Answer 1

我想至少你要做的一部分是把_hil转换成一个生成函数，在每次调用_step之后生成x, y对？如果是这样，那就很容易了。你知道吗

最困难的部分是那些递归调用。但这一点也不难。这正是^{}的目的：*使用一些迭代器（比如对生成器函数的递归调用）并生成它的每个值。**

然后是简单的部分，在每次调用_step之后，x, y对的非递归产生。您可以在每次调用后使用显式的yield self.x, self.y来实现这一点。或者您可以更改_step来添加return self.x, self.y，这样您就可以yield self._step(dirs)。但是您也可以将_step更改为只迭代一个值的迭代器，然后您也可以yield from它。（这里没有什么真正的优势，但我认为值得展示，这样您就可以仔细思考它是如何工作的，特别是当您问“我可以从这里迭代吗？”在_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

---

但是现在你得到了__init__，它只调用_hil，对结果不做任何处理。那不是很有用。也许你想把Hilbert类本身变成迭代器类？你知道吗

在这种情况下，最简单的方法是存储生成器迭代器并委托给它：

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)

---

然而，在这一点上，我不知道为什么你需要这是一个类在所有。x和y实际上不是对象状态的一部分，它们是生成器状态的一部分，如果您在_hil中使用局部变量（以及正常参数和返回传入_step），Python会神奇地处理这些状态。唯一的另一个状态是self.iter，这是必要的，因为您正在编写类而不是函数。你知道吗

---

_{*事实上，它的好处远不止这些，比如Greg Ewing describes amazingly well；没有它，我们就没有^{}。但将其添加到语言中的最初原因是“委托给子生成器的语法”。}

**请注意，这仅在具有yield from即Python3.3或更高版本时有效。如果您仍在使用Python2.x，并且yield from不足以让您升级，那么您可以通过将每个yield from eggs更改为for egg in eggs: yield egg来模拟它的一些用法，包括这个用法。它的可读性不会那么好，速度也会慢很多，但它可以工作。你知道吗