2

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
ggorlen
  • 44,755
  • 7
  • 76
  • 106
DanielDDD
  • 31
  • 4
  • 1
    just needs basic debugging. Ask yourself when do you add 1 to the total? – Kenny Ostrom May 24 '20 at 23:21
  • 1
    To learn recursion, debugging this problem yourself will teach you a great deal more than looking at a solution you didn't come up with yourself. Try debugging step by step and keep an eye on the value of `total_node` and where your code is at. – Grismar May 24 '20 at 23:48
  • I know whats going on now..I simply changed the total_node as a List then return the len(total_node). Thanks for all helps – DanielDDD May 24 '20 at 23:52
  • Creating a list just to take its length is a poor solution to the problem. This is like grilling a zucchini with a space shuttle. Please use an integer. – ggorlen May 24 '20 at 23:54
  • you are right. I am wasting a O(n) space by using a list. But i cannot come up a solution by an int. Its very easy to solve by iteration but i wanna practice recursion. – DanielDDD May 25 '20 at 00:02
  • 1
    Yeah, it's good to practice recursion with simple problems like this, and now you can convert your list solution to use an int. Keep in mind that `total_node` is totally local to the call frame, not a reference, so `total_node += 1` only changes the value local to that frame. Likely, the list version worked because it is a reference to the original object. – ggorlen May 25 '20 at 00:06

1 Answers1

4

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.

ggorlen
  • 44,755
  • 7
  • 76
  • 106