Linked List Recursive Value Sum

October 31, 2022

I am trying to recursively determine the sum of the values in a linked list.

I am aware of one recursive solution that works:

def sum_list_rec1(head_node: Node):
   if head_node == None:
       return 0

   return head_node.value + sum_list_rec1(head_node.next)

However, I am trying to use the pattern where a variable is passed to the recursive function initially which will store the total sum.

Here is the code:

def sum_list_rec2(head_node: Node):
   val_sum = 0
   calc_sum_rec(head_node, val_sum)
   return val_sum

def calc_sum_rec(head_node: Node, val_sum: int):
   if head_node == None:
      return

   val_sum += head_node.value
   calc_sum_rec(head_node.next, val_sum)

If I try to print out the output of the sum_list_rec2() function with a linked list (e.g. (1) -> (2) -> (3) -> (4)), I get an output of 0.

>Solution :

You can make your second snippet work by returning the new value:

def sum_list_rec2(head_node: Node):
   return calc_sum_rec(head_node, 0)

def calc_sum_rec(head_node: Node, val_sum: int):
   if head_node == None:
      return val_sum

   val_sum += head_node.value
   return calc_sum_rec(head_node.next, val_sum)

Actually the second function is better like this:

def calc_sum_rec(head_node: Node, val_sum: int):
   if head_node == None:
      return val_sum

   return calc_sum_rec(head_node.next, val_sum + head_node.value)