如何在Python中正確使用遞歸和副作用

在樹結構中，我試圖找到分支的所有葉子。這是我寫的：如何在Python中正確使用遞歸和副作用

def leafs_of_branch(node,heads=[]): 
    if len(node.children()) == 0: 
     heads.append(str(node)) 
    else:  
     for des in node.children(): 
      leafs_of_branch(des) 
    return heads 


leafs_of_branch(node)

我不知道爲什麼，但對我來說感覺不對。它的工作原理，但我想知道是否有更好的方式來使用遞歸而不創建heads參數。

來源

2013-01-07 Lpmat

@closevoter - 雖然這將最終遭受這個經典問題中提出的問題，但這不是這個問題的關鍵。 – mgilson

...特別是因爲問題明確要求不使用該參數的方法。 – bgporter

我認爲這應該工作：

def leafs_of_branch(node): 
    if len(node.children()) == 0: 
     return [str(node)] 
    else: 
     x = [] 
     for des in node.children(): 
      x += leafs_of_branch(des) #x.extend(leafs_of_branch(des)) would work too :-) 
     return x

這不是很漂亮，很可能被冷凝有點多，但我試圖保持你原有代碼的形式，儘可能使其明顯發生了什麼事。

如果您多次調用它，您的原始版本將不會實際工作，因爲當您附加到heads列表時，該列表實際上將在調用之間保存。

來源

2013-01-07 16:00:19 mgilson

恐怕這是行不通的。如果樹有十層，會怎麼樣？您沒有任何遞歸，只返回節點的所有節點或所有* direct *子節點。 –

另外，在'else'語句中，您將追加所有子項，而不管它們是否實際上是葉節點。 – bogatron

@ThorstenKranz - 謝謝。我忘了在'else'部分遞減（噢！）。 – mgilson

這

def leafs_of_branch(node,heads=[]):

始終是一個壞主意。更好的是

def leafs_of_branch(node,heads=None): 
    heads = heads or []

否則你總是使用相同的列表leafs_of_branch。在你的具體情況下，它可能是o.k.，但遲早你會遇到問題。

我建議：

def leafs_of_branch(node): 
    leafs = [] 
    for des in node.children(): 
     leafs.extend(leafs_of_branch(des)) 
    if len(leafs)==0: 
     leafs.append(str(node)) 
    return leafs 

leafs_of_branch(node)

而不是做一個if len(node.children()==0，我降入所有的（可能是零）的孩子後檢查LEN（葉子）。因此我只調用一次node.children（）。

來源

2013-01-07 16:00:57

你刪除了兒童檢查，這將返回所有節點... –

你是對的，改變它。謝謝。 –

首先，使用可變對象（列表類型的字典等）作爲默認值不要，因爲默認值是全球性的和重複使用的函數調用：

def bad_func(val, dest=[]): 
    dest.append(val) 
    print dest 

>>> bad_func(1) 
[1] 
>>> bad_func(2) 
[1, 2] # surprise!

那麼，隨之而來的通話將東西完全意外。

至於遞歸問題，我就重新寫這樣的：

from itertools import chain 

def leafs_of_branch(node): 
    children = node.children() 
    if not children: # better than len(children) == 0 
     return (node,) 

    all_leafs = (leafs_of_branch(child) for child in children) 
    return chain(*all_leafs)

來源

2013-01-07 16:01:15 bereal

只要遞歸去，你是對IMO這樣做;你在遞歸調用tho時錯過了頭部參數。無論如何，它的工作原因是爲了別人的說法，默認參數是全局的，並在調用之間重用。

如果你想避免遞歸altogheter，在這種情況下，你可以使用一個隊列或堆棧和一個循環：

def leafs_of_branch(node): 
    traverse = [node] 
    leafs = [] 

    while traverse: 
     node = traverse.pop() 
     children = node.children() 

     if children: 
      traverse.extend(children) 
     else: 
      leafs.append(str(node)) 

    return leafs

來源

2013-01-07 16:05:11 asermax

您還可以遞歸定義一個迭代器這種方式。

def leafs_of_branch(node): 
    if len(node.children()) == 0: 
     yield str(node) 
    else:  
     for des in node.children(): 
      for leaf in leafs_of_branch(des): 
       yield leaf 

leafs = list(leafs_of_branch(node))

來源

2013-01-07 16:14:24 MatthieuW

如何在Python中正確使用遞歸和副作用

回答

相關問題