Как создать генератор с рекурсией?

Question

Алгоритм от восторга Хакера 2-е издание

Портирован на питон

Простой класс кривой Гильберта.

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.

Так что мне нужно что-то, что дает (x,y) каждый раз, когда вызывается next(). Я пытался сделать это сам, но не могу заставить его работать, поэтому любая помощь будет оценена. Должен ли я переписать это для работы с генератором? Источник

Answer 1

Я думаю, по крайней мере, часть того, что вы пытаетесь сделать, это повернуть _hil в функцию генератора, которая дает x, y пары после каждого звонка _step? Если так, то это довольно просто.

Трудная часть - это те рекурсивные вызовы. Но это совсем не сложно. Это именно то, что yield from предназначен для:* Возьмите некоторый итератор (например, рекурсивный вызов функции генератора) и выведите каждое из его значений.**

Тогда есть легкая часть, нерекурсивная сдача x, y пары после каждого звонка _step, Вы можете сделать это с явным 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 на самом деле не являются частью состояния объекта, они являются частью состояния генератора, которое Python позаботится о волшебстве, если вы просто используете локальные переменные в _hil (и обычная передача параметров и возврата в _step). И единственное другое государство self.iter, что необходимо только потому, что вы пишете класс вместо функции.

---

_{* На самом деле, это хорошо для гораздо большего, как замечательно описывает Грег Юинг; у нас не было бы} asyncio _{без этого. Но первоначальная причина для добавления его в язык заключалась в следующем: "Синтаксис для делегирования подгруппе".}

** Обратите внимание, что это работает только если у вас есть yield from Означает Python 3.3 или более поздней версии. Если вы все еще используете Python 2.x, и yield from недостаточно, чтобы заставить вас обновить, вы можете смоделировать некоторые его применения, в том числе это, изменяя каждый yield from eggs в for egg in eggs: yield egg, Он не будет таким читаемым и будет значительно медленнее, но он будет работать.