пытаясь понять рекурсивный запуск генераторов

Question

Я пытаюсь выяснить, как отобразить прогон этого кода в дереве рекурсии, потому что я не совсем уверен, как он работает, даже когда я отлаживаю. что делает каждый урожай и зачем мне оба?

Я пытался создать какое-то дерево, которое рекурсивно связывает каждый прогон с его следующим, но я не знаю, что следует за yield.data, где заголовок равен 'c'

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


def get_reverse_iterator(head):
    if head.next:
        for datum in get_reverse_iterator(head.next):
            yield datum
    yield head.data


lst = Node('a', Node('b', Node('c')))
for x in get_reverse_iterator(lst):
    print(x)

результат должен быть: с б а

Answer 1

Чтобы понять, как это работает, вам нужно понять основную идею рекурсии.Давайте предположим, что мы не имеем дело с генераторами;мы просто хотим напечатать все узлы списка в обратном порядке, учитывая головной узел.Мы вызываем функцию print_reverse , передавая узел в качестве аргумента.Если поле узла next пусто, мы просто выводим значение поля data .Но если next не пусто, оно указывает на узел, который должен быть напечатан до того, как будет напечатан текущий узел.Поэтому мы рекурсивно вызываем print_reverse снова, чтобы сначала напечатать этот узел.Когда print_reverse вернется, мы можем напечатать текущий узел.Конечно, когда мы вызываем print_reverse рекурсивно для печати следующего узла, он может обнаружить, что существует еще один узел, на который он указывает, который должен быть сначала напечатан, и мы будем вызывать print_reverse рекурсивно еще раз.Таким образом, мы имеем:

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


def print_reverse(head):
    if head.next:
        print_reverse(head.next)
    print(head.data)


lst = Node('a', Node('b', Node('c')))
print_reverse(lst)

Приведенный выше код должен быть понят до понимания проблемы генератора.Вместо создания функции print_reverse , которая печатает поле узла data , мы хотим вместо этого создать функцию генератора, которая возвращает значение.Таким образом, имеет смысл переименовать функцию и заменить функцию печати на оператор yield, а рекурсивный вызов на оператор yield from:

class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next


def get_reverse_iterator(head):
    if head.next:
        #print_reverse(head.next)
        yield from get_reverse_iterator(head.next)
    #print(head.data)
    yield head.data

lst = Node('a', Node('b', Node('c')))

Теперь мы можем использовать генератор, как в:

for x in get_reverse_iterator(lst):
    print(x)

или:

l = [x in get_reverse_iterator(lst)]

Но альтернативой использованию рекурсии, позволяющей избежать создания нескольких объектов-генераторов, будет:

def get_reverse_iterator(head):
    stack = []
    while head.next:
        stack.append(head)
        head = head.next
    yield head.data
    while len(stack):
        head = stack.pop()
        yield head.data

Answer 2

Каждый раз, когда вы вызываете метод как генератор (например, for x in get_reverse_iterator()), python начинает выполнять этот метод построчно.Всякий раз, когда он достигает yield, он останавливается и возвращает это.Когда на следующей итерации цикла for его запрашивают значение next(), он продолжает выполняться.

Это выглядит как довольно простая идиома обхода связанного списка, где каждый элемент списка содержит данные, которые сами являются списком (или некоторым другим итеративным значением, например строкой):

list[0].data = [1, 2, 3, 4]
list[1].data = [5, 6, 7, 8]
...
list[9].data = [37, 38, 39, 40]

Итак, что делает код здесь печатает эти подсписки от задней части основного списка до передней части основного списка.Вывод должен выглядеть примерно так:

37 38 39 40 33 34 35 36 ... 5 6 7 8 [1, 2, 3, 4]

, что становится очевидным, когда вы смотрите на то, как выполняется код.Я перепишу это словами:

func get_reverse_iterator(head) {
    if head isn't the last element of the list, then
        call this function on the next element of the list (head.next)
        for every element in the return value of that,
            yield that element
    yield this element's data

«Базовый регистр» - это последний элемент списка, который не имеет .next.Таким образом, его data, который является итеративным, возвращается ко второму-последнему элементу.Второй по порядку элемент возвращает по очереди каждый элемент этих данных, а затем возвращает свои собственные данные третьему элементу.Элемент с третьего по последний возвращает по очереди каждый элемент этих данных и так далее, пока, наконец, вы не доберетесь до первого элемента списка.До сих пор каждый отдельный оператор yield проходил один элемент вверх по цепочке, и поэтому внутренний цикл for для первого элемента дал 36 значений.Наконец, все более поздние элементы в списке завершаются, пропуская значения, и поэтому первый элемент попадает в последний оператор функции и возвращает свои собственные данные.

Но ничего не осталось, чтобы поймать эти полученные данные ипроанализируйте его по отдельному элементу, чтобы он печатался как list, как это было на первом месте.Или, по крайней мере, для моего примера, представленного выше.

---

В вашем случае это более просто, потому что, когда вы перебираете string, каждый элемент по-прежнему равен string.Но это то же самое в меньшем масштабе:

1. get_reverse_iterator() вызывается в корневом узле lst
2. Корневом узле (я назову его NodeA) имеет .next
3. get_reverse_iterator(), вызываемый на следующем узле, который я буду называть NodeB
4. NodeB имеет .next
5. get_reverse_iterator() вызывается на следующем узле, который я назову NodeC
6. NodeC не имеет .next
7. get_reverse_iterator(NodeC) пропускает цикл for ивыдает NodeC.data, то есть 'c'`
8. get_reverse_iterator(NodeB) ловит 'c' внутри цикла for и возвращает его
9. get_reverse_iterator(NodeA) ловит 'c' внутри for loop и возвращает его
10. 'c' присваивается x и печатается.
11. Происходит следующая итерация внешнего цикла, и выполнение возвращается к get_reverse_iterator(NodeB)
12. Цикл for заканчивается, потому что get_reverse_iterator(NodeC) перестал давать вещи
13. get_reverse_iterator(NodeB) завершает цикл for, выходит из блока if и, наконец, возвращает NodeB.data, то есть 'b'
14. get_reverse_iterator(NodeA) захватывает 'b' внутри цикла for и возвращает его
15. 'b' присваивается x и печатается.
16. Проходит следующая итерация внешнего цикла, и выполнение возвращается к get_reverse_iterator(NodeA)
17. for цикл заканчивается, потому что get_reverse_iterator(NodeC) прекратил приносить вещи
18. get_reverse_iterator(NodeA) заканчивает цикл for, выходит из блока if и, наконец, выдает NodeA.data, то есть 'a'
19. 'a' присваивается x и печатается
20. Внешний цикл for завершается, так как get_reverse_iterator(NodeA) перестает давать результаты.