CODEWITHSUNDEEP
pythonrecursion
Al Capone
Al Capone

Reputation: 17

Python function to split and add lists recursively

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!

Upvotes: 0

Views: 3842

Answers (3)

Mitchell Chu
Mitchell Chu

Reputation: 137

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

Upvotes: 1

Frerich Raabe
Frerich Raabe

Reputation: 94489

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)

Upvotes: 0

Kevin
Kevin

Reputation: 76254

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)

Upvotes: 3

Related Questions