Python function to split and add lists recursively

Question

I'm having trouble writing a function in python that will take a list, split it into 2 equal sides and then recursively add each element in each half. In the end returning the sum of both halves.

def sumLists(aList):
    half = len(aList)//2
    leftHalf = aList[half:]
    rightHalf = aList[:half]
    if len(aList) == 1:
        return aList[0]
    else:
        sumOfLeft = sumLists(leftHalf[1:])
        resultLeft = leftHalf[0] + sumOfLeft
        sumOfRight = sumLists(rightHalf[1:])
        resultRight = rightHalf[0] + sumOfRight
        return resultLeft + resultRight

Any tips are appreciated, thanks!

Mathematically there is no difference to direct sum(aList). For example, the list [0,1,2,3]: (0+1)+(2+3) = 0+1+2+3 = 6. — Chickenmarkus
– Chickenmarkus, Commented Mar 16, 2016 at 13:57

Kevin · Accepted Answer · 2016-03-16 13:52:09Z

3

You're overcomplicating the else block. You don't need to call sumLists on leftHalf[1:] and rightHalf[1:] and manually add the first respective elements; it suffices to call sumLists on the complete lists.

This slicing is what's causing your RuntimeError. A leftHalf with length one will have a leftHalf[1:] of length zero. But your function recurses forever for lengths of length zero because you didn't write an if case for that scenario.

You could rewrite your else so that it doesn't require slicing:

def sumLists(aList):
    half = len(aList)//2
    leftHalf = aList[half:]
    rightHalf = aList[:half]
    if len(aList) == 1:
        return aList[0]
    else:
        return sumLists(leftHalf) + sumLists(rightHalf)

... Or you could add a special case for empty lists:

def sumLists(aList):
    half = len(aList)//2
    leftHalf = aList[half:]
    rightHalf = aList[:half]
    if len(aList) == 0:
        return 0
    elif len(aList) == 1:
        return aList[0]
    else:
        sumOfLeft = sumLists(leftHalf[1:])
        resultLeft = leftHalf[0] + sumOfLeft
        sumOfRight = sumLists(rightHalf[1:])
        resultRight = rightHalf[0] + sumOfRight
        return resultLeft + resultRight

Or both:

def sumLists(aList):
    half = len(aList)//2
    leftHalf = aList[half:]
    rightHalf = aList[:half]
    if len(aList) == 0:
        return 0
    if len(aList) == 1:
        return aList[0]
    else:
        return sumLists(leftHalf) + sumLists(rightHalf)

answered Mar 16, 2016 at 13:52

Kevin

76.5k13 gold badges141 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Al Capone Over a year ago

Thanks for the quick answer. I see what you mean about over complicating the else block. I used the line return sumLists(leftHalf) + sumLists(rightHalf) as you suggested and works perfect. Thanks again!

Mitchell Chu · Accepted Answer · 2016-03-16 14:13:43Z

1

I think aList[half:] is the right side, and aList[:half] is the left side, is it right? the follow code will sum the list left and right side, hope this can solve your problem.

def sumlist(l):
    if not l or not isinstance(l, list):
        return 0  # or return other default value.
    if len(l) == 1:
        return l[0]
    half = len(l) // 2
    left = l[:half]  # left
    right = l[-half:]  # right
    return sumlist(left) + sumlist(right)

test:

l = [1,2,3,4,5,6,7,8,9]
result = sumlist(l)
print(result)  # 40

answered Mar 16, 2016 at 14:13

Mitchell Chu

1375 bronze badges

Comments

Frerich Raabe · Accepted Answer · 2016-03-16 13:58:24Z

0

Maybe I misread your question, but do you actually need to do both things in one function?

To sum a list recursively, you could define that the empty list (your base case) has the sum 0. Any non-empty list has the sum of the first element plus the sum of the remainder (the "tail") of the list:

def sumList(a):
  return 0 if not a else a[0] + sumList(a[1:])

To split a list recursively, you could keep track of the "left" and "right" list. The left list starts out being your input, the right list is empty. You then recursively prepend the last element of the left list to the right list until the right list is no longer shorter than the left:

def splitList(a, b=None):
  b = b or []
  return (a, b) if len(a) <= len(b) else splitList(a[:-1], [a[-1]] + b)

I suspect that passing around slices of lists is very inefficient in Python, so it might be better to rather pass around indices, e.g.

def sumList(a, idx=None):
  idx = idx or 0
  return 0 if idx >= len(a) else a[idx] + sumList(a, idx+1)

answered Mar 16, 2016 at 13:58

Frerich Raabe

95.2k20 gold badges127 silver badges216 bronze badges

1 Comment

Al Capone Over a year ago

Thanks for the reply. I know I could have done it perhaps easier using 2 functions however, it was a requirement that one function handled both things.

Collectives™ on Stack Overflow

Python function to split and add lists recursively

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related