python递归中的LinkedLists

Question

我在python中有一个简单的LinkedList实现.如何在方法中使用递归？我知道递归是如何工作的,但我如何使用自我递归.如果有人可以修复我的代码,但我对解释更感兴趣,那么我可以在不同的方法中使用它.

LinkedList代码:

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next

class LinkedList:
    def __init__(self):
        self.head = None

    def add(self, item):
        self.head = Node(item, self.head)

    def remove(self):
        if self.is_empty():
            return None
        else:
            item = self.head.item
            self.head = self.head.next
            return item

    def is_empty(self):
        return self.head == None 

我的代码是:

def count(self, ptr=self.head):
    if ptr == None:
        return '0'
    else:
        return 1 + self.count(ptr.next)

它给了我一个错误:

def count(self, ptr=self.head):
NameError: name 'self' is not defined

任何帮助深表感谢.

Answer 1

在Python中,默认参数不是在运行时计算的表达式.这些是在评估def自身时评估的表达式.因此class通常在第一次读取文件时.

结果,在那一刻,没有self.self是一个参数.这样只有在调用函数时才可用.

您可以使用例如None默认值并执行检查来解决该问题.但是在这里我们不能使用None,因为你已经附加了一个特殊的含义.然而dummy,我们可以构造一个对象,并使用它:

dummy = object()

def count(self, ptr=dummy):
    if ptr is dummy:
        ptr = self.head
    if ptr == None:
        return '0'
    else:
        return 1 + self.count(ptr.next)

您的代码的另一个问题是您返回一个零字符串.由于您不能简单地添加整数和字符串,这将是错误的.所以你应该返回一个整数:

dummy = object()

def count(self, ptr=dummy):
    if ptr is dummy:
        ptr = self.head
    if ptr == None:
        return 0  # use an integer
    else:
        return 1 + self.count(ptr.next)