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.

I wouldn't recommend using recursion for this. It's more efficient to just update `ptr = ptr.next` and loop while it's not `None`. — Blorgbeard, Oct 18 '17 at 15:40
It seems you are misinterpreting what ```self``` is used for. Without analyzing your code: what does ```return 1 + count(ptr.next)``` do? And why return a string of 0 in one case and a number 1 in the other... — sascha, Oct 18 '17 at 15:40
Note that there is a [recursion limit](https://stackoverflow.com/questions/3323001/what-is-the-maximum-recursion-depth-in-python-and-how-to-increase-it) in python, so your list cannot be any longer than that, or your recursive count method will crash! — Blorgbeard, Oct 18 '17 at 15:43
@Blorgbeard Unfortunately I had to use recursion for this one. — OmO Walker, Oct 18 '17 at 15:51

Willem Van Onsem · Accepted Answer · 2017-10-18T15:45:44.730

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)

More precisely, the default value is evaluated when the `def` statement itself is. — chepner, Oct 18 '17 at 15:44
Oh I see, I was like this should work, why isn't it. So self is not known until def is executed. Thanks a lot — OmO Walker, Oct 18 '17 at 15:50
@OmOWalker In `def count(self, ptr=self.head)` the interpreter has to set the default value for `ptr` while it's compiling that `def` line, so it has to evaluate `self.head`. But at that point in time there isn't an object named `self` in scope: no instance of the `LinkedList` class yet exists, and in fact the class itself doesn't yet exist. — PM 2Ring, Oct 18 '17 at 16:02

score 0 · Answer 2 · answered Oct 18 '17 at 16:01

0

You can also put the purely recursive call in a specific method, and use a wrapper around it:

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, this is cleaner than using a dummy object and/or default parameters (btw, specifying a default parameter in a recursive function is often a good sign that you should consider an internal recursive function and call it from your method with the correct initialization).

answered Oct 18 '17 at 16:01

pills

656
1
5
10

There is a downside to this approach too: the inner function gets redefined each time the outer function is called, rather than being defined once, when the script is scanned initially. The extra overhead may be significant if `count` is called often. Of course, if one is overly concerned about efficiency, then implementing a linked list in Python's probably not a good idea. ;) – PM 2Ring Oct 18 '17 at 16:07
1

If this is an issue you can put the inner function outside and call it from the proper method (this is actually how you would implement it in Java for instance, marking it private to make sure only the "proper" method calls it). But I agree that doing linkedlists in Python, and then using recursion on top of that, is already pretty bad in terms of efficiency. – pills Oct 18 '17 at 16:11
Can you not just call `self.next.count()` and do away with both the inner function and the `ptr` parameter? – Blorgbeard Oct 18 '17 at 17:11
@Blorgbeard: that was my initial thought but `self.next` is not a `LinkedList`, it's a `Node`. That would mean defining `count()` for `Node`, which doesn't really make sense and would probably break when you try to call it for an empty list (where `next` is `None`). – pills Oct 19 '17 at 08:47

score 0 · Answer 3 · answered Jan 16 '22 at 18:05

self is a simple representation for an object. To use self in your function as an object, you have to specify the class.

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

LinkedLists in python recursion

3 Answers3