CODEWITHSUNDEEP
pythonrecursionlinked-list
DanielDDD
DanielDDD

Reputation: 31

Count the number of nodes in a linked list recursively

Problem: Return the number of nodes in the linked list.

I am learning recursion recently. I know how to use iteration to solve this problem but I am stick by the recursion way. The following is my code and it always return 1 instead of the real count of the linked list. I cannot figure out the problem and hope someone can help me. How can I fix the problem?

def numberOfNodes(head):
   total_node = 0
   return __helper(total_node, head)


def __helper(total_node, head):
   if not head:
      return total_node += 1
   __helper(total_node, head.next)
   return total_node

Upvotes: 2

Views: 821

Answers (1)

ggorlen
ggorlen

Reputation: 56965

Recursion is a poor choice for this sort of thing (adds overhead and risks blowing the call stack for no good reason), but if you do use it for educational purposes, it's easiest to pass the total up the call stack, not down:

def linked_list_len(head):
   return linked_list_len(head.next) + 1 if head else 0

Basically, add 1 per frame where the head node exists, then call the function again with the next node. The base case is when head is None.

In some languages that offer tail call optimization, you can avoid the + 1 work that happens to the variable returned by the child recursive call per frame. This allows the compiler or interpreter to convert recursion to a loop, avoiding stack overflows. The code would look like (similar to your approach, with the difference that the + 1 is added in the recursive call):

def linked_list_len(head, total=0):
    return linked_list_len(head.next, total + 1) if head else total

But Python doesn't support TCO so you may as well write it the simpler way shown above.

Upvotes: 4

Related Questions