Рекурсия с использованием yield

84

Есть ли способ смешать рекурсию и 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

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

юлиомалегрия
источник
См. [Здесь] [1] для хорошего ответа на этот вопрос, который я задал некоторое время назад. [1]: stackoverflow.com/questions/5704220/…
sizzzzlerz
Примечание: правильный способ сделать это - использовать, itertools.countа не катить собственное решение, основанное на циклах или другое.
Петр Викторин
8
@PetrViktorin, это всего лишь пример, создание бесконечных чисел - вовсе не реальная проблема
juliomalegria

Ответы:

157

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

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выполняя ее, все, что вы делаете, это создаете новый генератор, фактически не выполняя тело функции и не возвращая ничего.

См. PEP 380 для получения дополнительной информации.

Свен Марнах
источник
13
Но, похоже yield from, еще есть предел рекурсии :(
Jo So
3
всегда будет предел рекурсии
Radio Controlled
12

В некоторых случаях может быть предпочтительнее использовать стек вместо рекурсии для генераторов. Должна быть возможность переписать рекурсивный метод, используя стек и цикл 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'])

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

t.888
источник
3
Хороший ответ! Yield в python 2.7 не может использоваться с рекурсией, но, управляя стеком вручную, вы можете получить тот же эффект.
00prometheus
0
def lprint(a):
    if isinstance(a, list):
        for i in a:
            yield from lprint(i)
    else:
        yield a

b = [[1, [2, 3], 4], [5, 6, [7, 8, [9]]]]
for i in lprint(b):
    print(i)
Юрий Блинков
источник
Что есть b? Старайтесь не оставлять ответы,
состоящие
for i in lprint (a): print (i)
Юрий Блинков
Почему бы не отредактировать ответ, чтобы он был более понятным? Вы можете сделать это, щелкнув небольшой editтег под своим ответом или щелкнув здесь . Также, как я уже сказал, попытайтесь добавить небольшое объяснение того, как и почему это решает проблему
Tomerikoo
-3

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

Пузырь пузырь пузырь кишка
источник
1
хотя этот ответ требует более подробной информации, на самом деле он соответствует принятому ответу Свена Марнака, см. его первый
фрагмент