Python: recursion in Class declaration

Question

I am trying to implement a recursive function within a class declaration in Python. However, the function doesn't seem to accept parameters. If I declare a recursive function outside the Class, it works.

[A while loop][1] will also do the trick. (See "Traversing values). I've banged my head on the keyboard enough to permit an SO post, IMHO.

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None
    def traverse(self, node):
        print(node.data)
        if (node.next == None):
            return
        else:
            node.traverse(node.next)

            
>>> a = Node('a')
>>> b = Node('b')
>>> c = Node('c')
>>> a.next = b
>>> b.next = c
>>> Node.traverse(a)
Traceback (most recent call last):
  File "<pyshell#62>", line 1, in <module>
    Node.traverse(a)
TypeError: traverse() missing 1 required positional argument: 'node'


  [1]: https://medium.com/@kojinoshiba/data-structures-in-python-series-1-linked-lists-d9f848537b4d

If you call an unbound method (by class, not instance) you have to supply an instance for self as the first argument. — Klaus D.
– Klaus D., Commented Nov 8, 2020 at 21:36
You just want a.traverse() methods are meant to be called on the instance. This really has nothing to do with recursion — juanpa.arrivillaga
– juanpa.arrivillaga, Commented Nov 8, 2020 at 21:50

DarrylG · Accepted Answer · 2020-11-08 22:02:45Z

A more typical implementation of this would be.

Node Code

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None
        
    def traverse(self):               # instance method (no 2nd argument node)
        if self:                      # check if node
            print(self.data)          # output data
            if self.next:             # check for next node
                self.next.traverse()  # recursive call to next node if any

Test

a = Node('a')
b = Node('b')
c = Node('c')
a.next = b
b.next = c
a.traverse()     # Note: Node.traverse(a) also works
                 # This is because
                 # When you call an instance method (e.g. traverse) from an
                 # instance object (e.g. a), Python automatically passes 
                 # that instance object as the first argument (in addition
                 # to any other arguments) to the function call
                 # Thus: a.traverse() becomes Node.traverse(a)

Output

a
b
c

Guimoute · Accepted Answer · 2020-11-08 21:36:26Z

2

You need to make traverse a class method. Currently it says you're missing the node argument because in the line Node.traverse(a) you provided self=a and not node=a.

class Node:
    def __init__(self, value):
        self.data = value
        self.next = None

    @classmethod # This is the only addition needed :) 
    def traverse(self, node):
        print(node.data)
        if node.next is None:
            return
        else:
            node.traverse(node.next)

answered Nov 8, 2020 at 21:36

Guimoute

4,6743 gold badges17 silver badges34 bronze badges

2 Comments

user2864740 Over a year ago

While there is a Node.traverse, it’s at the at the outside call. So making this change would break the actual recursion call (which itself might be suspect).

juanpa.arrivillaga Over a year ago

Traverse should just be a normal method, the OP should learn to call methods. This likely just adds to the confusion

Pooya Kamranjam · Accepted Answer · 2020-11-08 21:59:12Z

In Python Cookbook, page 117, you will find this recipe which is a better solution for this problem:

class Node:
  def __init__(self, value):
    self._value = value
    self._children = []

  def __repr__(self):
    return 'Node({!r})'.format(self._value)

  def add_child(self, node):
    self._children.append(node)

  def __iter__(self):
    return iter(self._children)

  def depth_first(self):
    yield self
    for c in self:
      yield from c.depth_first()


if __name__ == '__main__':
  root = Node(0)
  child1 = Node(1)
  child2 = Node(2)
  root.add_child(child1)
  root.add_child(child2)
  child1.add_child(Node(3))
  child1.add_child(Node(4))
  child2.add_child(Node(5))
  for ch in root.depth_first():
    print(ch)

Try to use this.

Collectives™ on Stack Overflow

Python: recursion in Class declaration

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related