Đệ quy sử dụng năng suất

Question

Có cách nào để kết hợp đệ quy và tuyên bố yield không? Ví dụ, một máy phát điện số vô hạn (sử dụng đệ quy) sẽ là một cái gì đó như:

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

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

tôi đã cố gắng:

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

và

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

Nhưng không ai trong số họ đã làm những gì tôi muốn, người đầu tiên dừng lại sau khi nó mang lại start và cái thứ hai mang lại start, sau đó máy phát điện và sau đó dừng lại.

LƯU Ý: Xin vui lòng, tôi biết bạn có thể làm điều này bằng cách sử dụng vòng lặp while:

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

Tôi chỉ muốn biết nếu điều này có thể được thực hiện một cách đệ quy.

Answer 1

Vâng, bạn có thể làm điều này:

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

này sẽ lôi ra một lần độ sâu đệ quy tối đa đạt được, mặc dù.

Bắt đầu từ Python 3.3, bạn sẽ có thể sử dụng

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

Nếu bạn chỉ cần gọi chức năng máy phát điện của bạn một cách đệ quy mà không cần lặp qua nó hoặc yield from -ing nó, tất cả các bạn cần làm là xây dựng một máy phát điện mới, mà không thực sự chạy chức năng cơ thể hoặc năng suất bất cứ điều gì.

Xem PEP 380 để biết thêm chi tiết.

Answer 2

Trong một số trường hợp, có thể thích hợp hơn khi sử dụng ngăn xếp thay vì đệ quy cho máy phát. Nó có thể viết lại một phương thức đệ quy bằng cách sử dụng một chồng và một vòng lặp while.

Dưới đây là một ví dụ về một phương pháp đệ quy trong đó sử dụng một callback và có thể được viết lại sử dụng ngăn xếp logic:

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) 

Các phương pháp trên đi qua một cây nút trong đó mỗi node có một mảng children có thể chứa các nút con. Khi mỗi nút gặp phải, cuộc gọi lại được phát hành và nút hiện tại được truyền cho nó.

Phương pháp này có thể được sử dụng theo cách này, in ra một số thuộc tính trên mỗi nút.

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

Sử dụng một chồng thay vào đó và viết phương pháp traversal như một máy phát điện

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

Bây giờ bạn có thể nhận được các hành vi tương tự như traverse_tree trên, nhưng với một máy phát điện:

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

Đây không phải là giải pháp một kích thước phù hợp nhưng đối với một số máy phát điện, bạn có thể nhận được kết quả tốt đẹp thay thế chế độ xếp chồng cho recursi trên.

Answer 3

Vì vậy, về cơ bản bạn chỉ cần thêm vòng lặp for tại số nơi bạn cần gọi hàm theo cách đệ quy. Điều này áp dụng cho Python 2.7.