LinkedLists in python recursion

Question

I have a simple implementation of LinkedList in python. How do I use recursion inside a method? I know how recursion works but how do I use self with recursion. It'd be nice if someone can fix my code but I am more interested in explanation so I can use it in different methods.

LinkedList code:

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 

My code is:

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

It gives me an error:

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

Any help is much appreciated.

Answer 1

In Python default arguments are not expressions that are evaluated at runtime. These are expressions that are evaluated when the def itself is evaluated. So for a class usually when the file is read for the first time.

As a result, at that moment, there is no self. self is a parameter. So that is only available when you call the function.

You can resolve that problem by using for instance None as default and perform a check. But here we can not use None, since you already attached a special meaning to it. We can however construct a dummy object, and use that one:

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)

Another problem with your code is that you return a string for zero. Since you can not simply add an integer and a string, this will error. So you should return an integer instead:

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)