Рекурсия по доходности - PullRequest
Новая
       74

Рекурсия по доходности

54 голосов
/ 24 января 2012

Есть ли способ смешать рекурсию и оператор yield?Например, генератор бесконечных чисел (с использованием рекурсии) будет выглядеть примерно так: 

def infinity(start):
    yield start
    # recursion here ...

>>> it = infinity(1)
>>> next(it)
1
>>> next(it)
2

Я пытался: 

def infinity(start):
    yield start
    infinity(start + 1)

и 

def infinity(start):
    yield start
    yield infinity(start + 1)

Но ни один изони сделали то, что я хочу, первый остановился после того, как он дал start, а второй дал start, затем генератор и затем остановился.

ПРИМЕЧАНИЕ: Пожалуйста, я знаюВы можете сделать это, используя цикл while: 

def infinity(start):
    while True:
        yield start
        start += 1

Я просто хочу знать, можно ли это сделать рекурсивно.

Ответы [ 3 ]

115 голосов
/ 24 января 2012

Да, вы можете сделать это: 

def infinity(start):
    yield start
    for x in infinity(start + 1):
        yield x

Это приведет к ошибке, как только будет достигнута максимальная глубина рекурсии.

Начиная с Python 3.3, вы сможетеиспользуйте 

def infinity(start):
    yield start
    yield from infinity(start + 1)

Если вы просто вызываете функцию генератора рекурсивно, не зацикливая ее или yield from -ing, все, что вам нужно сделать, это создать новый генератор, фактически не запуская тело функции или ничего не получая.

Подробнее см. PEP 380 .

11 голосов
/ 13 июля 2015

В некоторых случаях может быть предпочтительнее использовать стек вместо рекурсии для генераторов. Должна быть возможность переписать рекурсивный метод, используя стек и цикл while.

Вот пример рекурсивного метода, который использует обратный вызов и может быть переписан с использованием логики стека: 

def traverse_tree(callback):
    # Get the root node from somewhere.
    root = get_root_node()
    def recurse(node):
        callback(node)
        for child in node.get('children', []):
            recurse(child)
    recurse(root)

Приведенный выше метод перебирает дерево узлов, где каждый узел имеет массив children, который может содержать дочерние узлы. При обнаружении каждого узла вызывается обратный вызов и ему передается текущий узел.

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

def callback(node):
    print(node['id'])
traverse_tree(callback)

Вместо этого используйте стек и напишите метод обхода в качестве генератора 

# A stack-based alternative to the traverse_tree method above.
def iternodes():
    stack = [get_root_node()]
    while stack:
        node = stack.pop()
        yield node
        for child in reversed(node.get('children', [])):
            stack.append(child)

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

Теперь вы можете получить то же поведение, что и traverse_tree выше, но с генератором: 

for node in iternodes():
    print(node['id'])

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

0 голосов
/ 29 декабря 2016

Таким образом, вам просто нужно добавить цикл for в , где вам нужно рекурсивно вызывать вашу функцию .Это относится к Python 2.7.

...