Recursive list sum not working

Hi! I just finished the recursion chapter on the CS with Python skill path and just trying to get some practice with some online -quite basic- problems.

On this one, i have to find the sum of the elements in a list, and some elements of the list are lists themselves.

This is where I got:

def sum_lst_rec(lst, lst_sum = 0):

  if len(lst) == 0:
    return lst_sum
  
  if isinstance(lst[0], list):
    sub_lst = lst[0]
    if len(sub_lst) == 0:
      return sum_lst_rec(lst[1:], lst_sum)
    lst_sum += sub_lst[0]
    return sum_lst_rec(sub_lst[1:], lst_sum)
  
  lst_sum += lst[0]

  return sum_lst_rec(lst[1:], lst_sum)

test_lst_2 = [1, 2, [3,4], [5, 6]]
print(sum_lst_rec(test_lst_2))

The code runs, but only sums until it encounters the first element that is a list. It sums the elements in that list, but doesn’t go on with the recursion. In this example, it returns 21

What am I missing?!

i had to run your code here:

http://www.pythontutor.com/visualize.html#mode=display

to step through it. I recommend you to do the same. The problem is that once [3, 4] is empty, this condition at the beginning of your function is true:

if len(lst) == 0:

so the function ends.

I don’t think i would use recursion here. You have lists, so you know the amount of iterations, so i would use loops instead, makes the code a lot easier to read

I can’t think of an easier way to do it, at least not one that doesn’t involve a lot more code…

I think you sort of understand what the logic of the problem ought to look like… but I don’t think you need quite so many returns in your function.

If you consider a very simple example, where every element in the list is simply an integer, you just want to iterate over them, test if they’re a list (which they’re not) and so simply calculate the sum.

If any given element is a list, that’s when you recursively call your function again to calculate the sum of that list.

You only need to return at the end of the function. This will serve the purpose of either handing back the final total, or handing back the sum of any sub-list found within the original set of input.

@stetim94 Hey! Thanks a lot for that viasualizer, it was extremely helpful and I’ll definitely use it in the future. Turns out the solution was a combination of loops AND recursion, as @thepitycoder suggested. Had to fight a bit but solved it!!

def sum_lst_rec(lst):
  lst_sum = 0
  
  for el in lst:
    if isinstance(el, list):
      lst_sum += sum_lst_rec(el)
    else:
      lst_sum += el

  return lst_sum

test_lst_2 = [1, 2, [3, 4], [5, 6]]
print(sum_lst_rec(test_lst_2))

Thanks lot!

2 Likes