Rekurencja z wydajnością

84

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.

juliomalegria
źródło
Zobacz [tutaj] [1], aby uzyskać dobrą odpowiedź na to pytanie, które zadałem jakiś czas temu. [1]: stackoverflow.com/questions/5704220/…
sizzzzlerz
Uwaga: właściwym sposobem na zrobienie tego byłoby użycie, itertools.counta nie rozwijanie własnego rozwiązania, opartego na pętli lub innego.
Petr Viktorin
8
@PetrViktorin to tylko przykład, generowanie nieskończonych liczb wcale nie jest prawdziwym problemem
juliomalegria

Odpowiedzi:

157

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 .

Sven Marnach
źródło
13
Ale wygląda na to, że yield fromnadal istnieje limit rekursji :(
Jo So
3
zawsze będzie limit rekursji
sterowane radiowo
12

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ą.

t.888
źródło
3
Niezła odpowiedź! Wydajność w Pythonie 2.7 tak naprawdę nie może być używana z rekurencją, ale ręcznie zarządzając stosem, można uzyskać ten sam efekt.
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)
Юрий Блинков
źródło
Co to jest b? Staraj się nie zostawiać odpowiedzi zawierających tylko kod ... Trochę wyjaśnień i wyjaśnień pomoże umieścić rzeczy w kontekście i lepiej zrozumieć twoją odpowiedź
Tomerikoo
for i in lprint (a): print (i)
Юрий Блинков
Dlaczego nie zmienić odpowiedzi, aby była bardziej przejrzysta? Możesz to zrobić, klikając mały edittag pod swoją odpowiedzią lub klikając tutaj . Ponadto, jak powiedziałem, spróbuj dodać trochę wyjaśnienia, jak i dlaczego to rozwiązuje problem
Tomerikoo.
-3

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

Bubble Bubble Gut
źródło
1
chociaż ta odpowiedź wymaga więcej szczegółów, w rzeczywistości jest zgodna z zaakceptowaną odpowiedzią Svena Marnacha, zobacz jego pierwszy fragment kodu ...
Coffee_Table,