返回列表的元组递归函数

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传递到下一个级别;然后返回下一级的结果。但是，避免递归可能更好，而是有一个运行两次的循环。