递归函数返回列表的元组

Question

我正在学习Python中的递归。 我定义了一个链表，每个节点都有一个项目和一个指向下一个节点的指针。 我想写一个递归函数，把奇数和偶数放到不同的集合里。

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\Wing IDE 101 4.1\src\debug\tserver_sandbox.py"，第19行，在odd_or_even中 builtins.UnboundLocalError: 本地变量'odd_num'在赋值前被引用

我应该在哪里初始化odd_num和even_num，以免它们被覆盖呢？

谢谢。

Answer 1

    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（偶数），但不会同时设置两个。然后它试图返回这两个值，这样就会出现错误，因为其中一个没有被设置。如果你在那个 if 语句之前把这两个值都初始化为 None（空值），就可以避免这个错误。不过，为了让逻辑更通顺，你可能需要给你的函数加一个参数，也就是上一级的结果；在递归调用的时候，把刚计算出来的 odd_num 或 even_num 传递到下一层；然后返回下一层的结果。不过，其实不使用递归，改用一个循环运行两次可能会更好。

Answer 2

我觉得你可以尝试几种不同的方法。

其中一种是使用全局变量。我并不太推荐这种方法，但因为它比较简单易懂，所以我先讲这个：

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的列表来存放偶数和奇数值。我上面提到的第二和第三种解决方案都可以工作，不过如果你愿意让偶数和奇数值以反向顺序返回，第三种方法会更自然。