Rekurencja z wydajnością

Question

Czy istnieje sposób na połączenie rekursji i instrukcji yield? Na przykład, nieskończona liczba generator (za pomocą rekurencji) byłoby coś jak:

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 chcę, pierwszy zatrzymał się po uzyskaniu start, a drugi wygenerował start, następnie generator, a następnie zatrzymał się.

UWAGA: proszę, wiem, można 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.

Answer 1

Tak, można to zrobić:

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

Będzie błędów raz zostanie osiągnięta maksymalna głębokość rekursji, choć.

Począwszy od Pythona 3.3, będziesz mógł korzystać

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

Jeśli po prostu zadzwonić do generatora funkcji rekursywnie bez zapętlenie nad nim lub yield from -ing go, wszystko co robisz jest zbudować nowy generator, bez faktycznego uruchamiania ciała funkcyjnego lub niczego.

Aby uzyskać więcej informacji, patrz PEP 380.

Answer 2

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

Oto przykład rekurencyjnej metody wykorzystującej zwrotnego i mogą być zapisane 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ższy sposób przechodzi drzewa węzeł, w którym każdy węzeł ma szereg children który może zawierać liczbę węzłów potomnych. Po napotkaniu każdego węzła wywoływane jest wywołanie zwrotne, a bieżący węzeł jest przekazywany do niego.

Metodę można zastosować w ten sposób, drukując niektóre właściwości w każdym węźle.

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

Użyj stos zamiast i napisać metodę przejścia 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 node.get('children', []): 
      stack.append(child) 

Teraz można uzyskać takie samo zachowanie jak traverse_tree powyżej, ale z generatorem:

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

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

Answer 3

Więc po prostu wystarczy dodać pętlę for przy , gdzie musisz wywołać swoją funkcję rekursywnie. Dotyczy to Pythona 2.7.