在python递归LinkedLists

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

的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

任何帮助深表感谢。

来源

2017-10-18 OmO Walker

我不会为此推荐使用递归。更新'ptr = ptr.next'并循环，而不是'None'更有效。 – Blorgbeard

看来你误解了'''self'''用于什么。不分析你的代码：'''返回1 + count（ptr.next）'''做什么？为什么在一种情况下返回0的字符串，另一种情况是1的数字... – sascha

请注意，有一个[递归限制]（https://stackoverflow.com/questions/3323001/what-is-the-maximum Python中的递归深度 - 在python中，以及如何增加它），所以你的列表不能超过这个长度，否则你的递归计数方法会崩溃！ – Blorgbeard

在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)

来源

2017-10-18 15:42:01

更确切地说，默认值是在'def'语句本身时进行评估的。 – chepner

哦，我明白了，我应该这样工作，为什么不呢。所以直到def被执行之前，自我才是已知的。非常感谢 –

@OmOWalker在'def count（self，ptr = self。头部）解释器在编译'def'行时必须为'ptr'设置默认值，所以它必须评估'self.head'。但是在那个时候，在范围内没有一个名为'self'的对象：没有LinkedList类的实例存在，实际上这个类本身还不存在。 –

你也可以把纯粹的递归调用的具体方法，并使用它周围的包装：

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

IMO，这比使用清洁剂虚拟对象和/或默认参数（顺便说一下，在递归函数中指定默认参数通常是一个好兆头，您应该考虑使用内部递归函数并使用正确的初始化从您的方法调用它）。

来源

2017-10-18 16:01:22 pills

这种方法也有一个缺点：每次调用外部函数时，都会重新定义内部函数，而不是在初始扫描脚本时定义一次。如果经常调用count，额外的开销可能会很大。当然，如果过度关心效率，那么在Python中实现链表可能不是一个好主意。 ;） –

如果这是一个问题，你可以把内部函数放在外面，并从适当的方法中调用它（这实际上是如何在Java中实现的，将它标记为私有的，以确保只有“正确的”方法才会调用它）。但我同意用Python做链表，然后在其上使用递归，在效率方面已经很糟糕了。 – pills

你不能只调用'self.next.count（）'并且不要使用内部函数和'ptr'参数吗？ – Blorgbeard

在python递归LinkedLists

回答

相关问题