返回列表的元組遞歸函數

Question

我學習Python的遞歸。我定義了一個鏈接列表，其中每個節點都有item和next。我想寫一個遞歸來把奇數和偶數放在一個單獨的集合中。

class LinkNode(object): 
"""A node in a linked list.""" 

def __init__(self, item, next=None): 
    """(LinkNode, object, LinkNode) -> NoneType 
    Initialize this node to store item and next. 
    """ 
    self.item = item 
    self.next = next 

def odd_or_even(self): 
    """(LinkNode) -> ([object], [object]) 
    Return a pair of lists: (odd number, even number. 
    """ 
    if self is None: 
     return ([], []) 
    else: 
     if (self.item % 2 == 1): 
      odd_num = odd_num.append(self.item) 
     else: 
      even_num = even_num.append(self.item) 
    if self.next is not None: 
     self.next.odd_or_even() 
    return (odd_num, even_num) 

當我運行它，我得到了以下錯誤：

文件 「C：\ Program Files文件\永IDE 4.1 101的\ src \調試\ tserver_sandbox.py」 19行，在odd_or_even builtins.UnboundLocalError：分配之前引用局部變量「odd_num」

我應該在哪裏初始odd_num，even_num所以它不會被覆蓋？

謝謝。

Answer 1

我認爲有，你可以用幾種不同的方法。

其中之一是使用全局變量。我真的不建議這一點，但它很容易理解，所以我先介紹它：

even_num = [] # these should be at module level, but I'm not showing the class 
odd_num = [] # so you'll have to imagine the indentation being correct 

def odd_or_even(self): 
    """(LinkNode) -> ([object], [object]) 
    Return a pair of lists: (odd number, even number. 
    """ 
    if self.item % 2 == 1: 
     odd_num.append(self.item) 
    else: 
     even_num.append(self.item) 

    if self.next is not None: 
     self.next.odd_or_even() 

的代碼改變是次要的，大多隻是刪除return語句。我確實拿出了self的初始檢查號爲None，因爲這在方法中是不可能的（除非呼叫者非常努力地實現）。另外值得一提的是，我們並不試圖向直接odd_num或even_num，因爲這將創建一個局部變量，而不是訪問已存在的全局變量。此解決方案的缺點是您只能撥打odd_or_even一次，並使其正常工作。如果你想再次調用它（也許在另一個列表中），你需要重新初始化全局變量。

這裏有一個更好的辦法，創建奇數和偶數表爲局部變量，然後在年底返回它們。這可能是你在代碼中瞄準的目標，但是你錯過了將遞歸調用的結果添加到列表中的步驟。

def odd_or_even(self): 
    even_num = [] 
    odd_num = [] 

    if self.item % 2 == 1: 
     odd_num.append(self.item) 
    else: 
     even_num.append(self.item) 

    if self.next is not None: 
     next_even, next_odd = self.next.odd_or_even() 
     even_num.extend(next_even) 
     odd_num.extend(next_odd) 

    return even_num, odd_num 

該代碼的問題是創建和擴展列表是浪費。在遞歸的每個級別上，都會創建兩個新列表，即使只有一個值將在該級別處理。更好的方法可以只使用兩個列表總，整個遞歸過程：

def odd_or_even(self, lists=None): 
    if lists is not None: 
     even_num, odd_num = lists 
    else: 
     even_num = [] 
     odd_num = [] 

    if self.item % 2 == 1: 
     odd_num.append(self.item) 
    else: 
     even_num.append(self.item) 

    if self.next is not None: 
     return self.next.odd_or_even((even_num, odd_num)) 
    else: 
     return even_num, odd_num 

這比以前的版本更有效，因爲它使用的遞歸的所有級別相同的列表。在其他一些編程語言中，這種遞歸方式（在遞歸調用運行之前完成所有工作）比其他類型的遞歸效率高得多。這是因爲編譯器可以優化功能的return步驟（並重新使用堆棧幀）。然而，Python不會做這樣的「尾部調用優化」（因爲它會弄亂堆棧跟蹤），所以它的好處不會那麼大。

另一件需要考慮的事情是：您可以使用自己的鏈表，而不是Python列表來保存偶數和奇數值。我上面顯示的第二個和第三個解決方案都可以工作，但如果您願意以相反順序返回偶數和奇數值，第三個解決方案的工作最自然。

Answer 2

if (self.item % 2 == 1): 
     odd_num = odd_num.append(self.item) 
    else: 
     even_num = even_num.append(self.item) 
... 
return (odd_num, even_num) 

上面的代碼段設置要麼odd_num或even_num，但不能同時的值。然後它會嘗試返回odd_num和even_num，這會產生一個或另一個錯誤。如果您在if聲明之前初始化爲None，則可避免發生的錯誤。但是，爲了使語義工作，您可能需要爲您的函數添加另一個參數，即上一級的結果;在遞歸調用中，將剛剛計算的odd_num或even_num傳遞到下一個級別;然後返回下一級的結果。但是，避免遞歸可能更好，而是有一個運行兩次的循環。