Rekursion mit Ausbeute

82

Gibt es eine Möglichkeit, Rekursion und yieldAnweisung zu mischen ? Zum Beispiel wäre ein Generator für unendliche Zahlen (unter Verwendung von Rekursion) ungefähr so:

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

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

Ich habe es versucht:

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

und

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

Aber keiner von ihnen hat getan, was ich will, der erste hat angehalten, nachdem er nachgegeben hat, startund der zweite hat nachgegeben start, dann der Generator und dann angehalten.

HINWEIS: Bitte, ich weiß, dass Sie dies mit einer while-Schleife tun können:

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

Ich möchte nur wissen, ob dies rekursiv möglich ist.

juliomalegria
quelle
Siehe [hier] [1] für eine gute Antwort auf diese Frage, die ich vor einiger Zeit gestellt habe. [1]: stackoverflow.com/questions/5704220/…
sizzzzlerz
Hinweis: Der richtige Weg, dies zu tun, besteht darin, itertools.countIhre eigene Lösung zu verwenden, anstatt sie zu rollen, schleifenbasiert oder anderweitig.
Petr Viktorin
8
@PetrViktorin dies ist nur ein Beispiel, unendliche Zahlen zu generieren ist überhaupt nicht das eigentliche Problem
Juliomalegria

Antworten:

154

Ja, das können Sie tun:

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

Dies tritt jedoch auf, sobald die maximale Rekursionstiefe erreicht ist.

Ab Python 3.3 können Sie verwenden

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

Wenn Sie Ihre Generatorfunktion nur rekursiv aufrufen yield from, ohne sie zu durchlaufen oder zu durchlaufen, müssen Sie lediglich einen neuen Generator erstellen, ohne den Funktionskörper tatsächlich auszuführen oder etwas zu liefern.

Siehe PEP 380 für weitere Details.

Sven Marnach
quelle
12
Aber es scheint, dass yield fromes immer noch ein Rekursionslimit gibt :(
Jo So
2
es wird immer eine Rekursion Grenze sein
Radio Controlled
12

In einigen Fällen ist es möglicherweise vorzuziehen, einen Stapel anstelle einer Rekursion für Generatoren zu verwenden. Es sollte möglich sein, eine rekursive Methode mit einem Stapel und einer while-Schleife neu zu schreiben.

Hier ist ein Beispiel für eine rekursive Methode, die einen Rückruf verwendet und mithilfe der Stapellogik neu geschrieben werden kann:

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)

Die obige Methode durchläuft einen Knotenbaum, in dem jeder Knoten ein childrenArray hat, das untergeordnete Knoten enthalten kann. Wenn jeder Knoten angetroffen wird, wird der Rückruf ausgegeben und der aktuelle Knoten an ihn übergeben.

Die Methode könnte auf diese Weise verwendet werden, indem einige Eigenschaften auf jedem Knoten ausgedruckt werden.

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

Verwenden Sie stattdessen einen Stapel und schreiben Sie die Traversal-Methode als Generator

# 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)

(Beachten Sie, dass Sie die Reihenfolge der untergeordneten Elemente umkehren müssen, wenn Sie dieselbe Durchlaufreihenfolge wie ursprünglich wünschen, da das erste an den Stapel angehängte untergeordnete Element das letzte ist, das angezeigt wird.)

Jetzt können Sie das gleiche Verhalten wie traverse_treeoben erzielen, jedoch mit einem Generator:

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

Dies ist keine Einheitslösung, aber für einige Generatoren erhalten Sie möglicherweise ein gutes Ergebnis, wenn Sie die Rekursion durch die Stapelverarbeitung ersetzen.

t.888
quelle
3
Gute Antwort! Der Ertrag in Python 2.7 kann nicht wirklich mit Rekursion verwendet werden, aber durch manuelles Verwalten des Stapels können Sie den gleichen Effekt erzielen.
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)
Юрий Блинков
quelle
Was ist b? Versuchen Sie, keine Nur-Code-Antworten zu hinterlassen ... Eine kleine Klarstellung und Erklärung hilft, die Dinge in einen Kontext zu bringen und Ihre Antwort besser zu verstehen
Tomerikoo
für i in lprint (a): print (i)
Юрий Блинков
Warum nicht die Antwort bearbeiten, damit sie klarer wird? Sie können dies tun, indem Sie auf das kleine editTag unter Ihrer Antwort klicken oder hier klicken . Versuchen Sie auch, wie gesagt, eine kleine Erklärung hinzuzufügen, wie und warum dies das Problem löst
Tomerikoo
-3

Im Grunde müssen Sie nur eine for-Schleife hinzufügen, an der Sie Ihre Funktion rekursiv aufrufen müssen . Dies gilt für Python 2.7.

Bubble Bubble Bubble Gut
quelle
1
Obwohl diese Antwort detaillierter sein muss, entspricht sie tatsächlich der akzeptierten Antwort von Sven Marnach, siehe sein erstes Stück Code ...
Coffee_Table