Rekurencja z wydajnością

Czy jest jakiś sposób na połączenie rekurencji i yieldinstrukcji? Na przykład generator liczb nieskończonych (wykorzystujący rekurencję) wyglądałby tak:

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

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

Próbowałem:

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

i

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

Ale żaden z nich nie zrobił tego, co chciałem, pierwszy zatrzymał się po tym, jak ustąpił, starta drugi ustąpił start, potem generator i zatrzymał się.

UWAGA: Proszę, wiem, że możesz to zrobić za pomocą pętli while:

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

Chcę tylko wiedzieć, czy można to zrobić rekurencyjnie.

Tak, możesz to zrobić:

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

Spowoduje to jednak błąd po osiągnięciu maksymalnej głębokości rekurencji.

Począwszy od Pythona 3.3, będziesz mógł używać

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

Jeśli po prostu wywołujesz swoją funkcję generatora rekurencyjnie, bez zapętlania się nad nią lub yield from-ingiem, wszystko, co robisz, to budowanie nowego generatora, bez faktycznego uruchamiania treści funkcji lub tworzenia czegokolwiek.

Więcej szczegółów w PEP 380 .

W niektórych przypadkach lepiej jest użyć stosu zamiast rekurencji dla generatorów. Powinno być możliwe przepisanie metody rekurencyjnej przy użyciu stosu i pętli while.

Oto przykład metody rekurencyjnej, która używa wywołania zwrotnego i może zostać przepisana przy użyciu logiki stosu:

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)

Powyższa metoda przechodzi przez drzewo węzłów, gdzie każdy węzeł ma childrentablicę, która może zawierać węzły potomne. Po napotkaniu każdego węzła wywoływane jest wywołanie zwrotne i przekazywany jest do niego bieżący węzeł.

Metodę można wykorzystać w ten sposób, wypisując jakąś właściwość w każdym węźle.

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

Zamiast tego użyj stosu i zapisz metodę przechodzenia jako 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)

(Zwróć uwagę, że jeśli chcesz mieć taką samą kolejność przemierzania, jak pierwotnie, musisz odwrócić kolejność elementów potomnych, ponieważ pierwsze dziecko dołączone do stosu będzie ostatnim pobranym).

Teraz możesz uzyskać to samo zachowanie, co traverse_treepowyżej, ale z generatorem:

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

To nie jest uniwersalne rozwiązanie, ale w przypadku niektórych generatorów możesz uzyskać niezły wynik zastępując przetwarzanie stosu rekurencją.

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)

W zasadzie wystarczy dodać pętlę for w miejscu, w którym należy rekurencyjnie wywołać funkcję . Dotyczy to Pythona 2.7.