使用收益遞歸

有什麼方法可以將遞歸和yield語句混合使用？舉例來說，一個無限數發生器（使用遞歸），會是這樣的：使用收益遞歸

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

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

我想：

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

和

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

但他們沒有做我想要的東西，第一個在產生start後停止，第二個產生start，然後發電機停止。

注：拜託，我知道你可以使用while循環做到這一點：

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

我只是想知道這是否可以完成遞歸。

來源

2012-01-24 juliomalegria

請參閱[這裏] [1]對於這個問題的回答，我提出了一段時間。 [1]：http://stackoverflow.com/questions/5704220/python-generator-vs-callback-function – sizzzzlerz

注：這樣做正確的方法是使用['itertools.count' ]（http://docs.python.org/dev/library/itertools.html#itertools.count），而不是滾動您自己的解決方案，基於循環或othersise。 –

@PetrViktorin @PetrViktorin這只是一個例子，生成無限數字根本就不是真正的問題 – juliomalegria

是的，你可以這樣做：

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

這將報錯了，一旦達到最大遞歸深度，雖然。

在Python 3.3開始，你就可以使用

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

如果你只是打電話給你生成的函數遞歸循環沒有在它或yield from -ing它，你要做的就是建立一個新的發電機，而沒有真正運行函數體或產生任何東西。

請參閱PEP 380瞭解更多詳情。

來源

2012-01-24 18:14:08

但是''yield''似乎仍然存在遞歸限制:( –

在某些情況下，最好使用堆棧而不是遞歸生成器。應該可以使用堆棧和while循環重寫遞歸方法。

下面是其中使用回調，並且可以使用堆邏輯被重寫的遞歸方法的一個例子：

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)

上述方法遍歷節點樹，其中每個節點具有children陣列，其可含有子節點。在遇到每個節點時，會發出回調並將當前節點傳遞給它。

該方法可以這樣使用，打印出每個節點上的一些屬性。

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

使用堆棧，而不是寫的遍歷方法作爲發電機

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

現在，你可以得到相同的行爲與上述traverse_tree，但發電機：

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

這不是一個通用的解決方案，但對於某些生成器，您可能會得到一個很好的結果，將棧處理替換爲recursi上。

來源

2015-07-12 23:58:55

好的答案！python 2.7中的yield不能真正用於遞歸，但通過手動管理堆棧，你可以得到相同的效果。 – 00prometheus

-1

所以基本上你只需要添加一個for循環在你需要遞歸調用你的函數。這適用於Python 2.7。

來源

2016-12-28 21:45:38 Ding

爲遞歸添加一個循環似乎是錯誤的... –

我同意，這似乎很糟糕，而不僅僅是在Python 2.7中... – ppovoski

使用收益遞歸

回答

相關問題