1

我正在学习 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: local variable 'odd_num' referenced before assignment

我应该在哪里初始化奇数，偶数，这样它就不会被覆盖？

谢谢。

4

2 回答 2

0 
    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_numand even_num，这会为其中一个或另一个产生错误。如果您None在该语句之前将两者都初始化if，您将避免发生的错误。但是，为了使语义起作用，您可能需要在函数中添加另一个参数，即上一级的结果；在递归调用中，将刚刚计算的odd_num或even_num向下传递到下一个级别；然后返回下一级的结果。但是，最好避免递归，而是使用一个运行两次的循环。

于 2013-03-04T02:01:38.790 回答
0

我认为您可以使用几种不同的方法。

一种是使用全局变量。我不是很推荐这个，但它很容易理解，所以我先介绍它：

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语句。我确实对selfbeing进行了初始检查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 列表来保存偶数和奇数值。我上面展示的第二种和第三种解决方案都可以工作，但如果您愿意以相反的顺序返回偶数和奇数值，第三种方法会最自然地工作。

于 2013-03-04T03:05:41.550 回答