How do i sum up 2 halves of a list recursively-CodePudding

I need to first split the list in 2 halves then sum up those 2 with recursion

def merge_sum(list):
    
    middle = int(len(list)-1)//2
    first_half = merge_sum(list[:middle])
    second_half = merge_sum(list[middle:])
    return first_half   second_half

print(merge_sum([1,2,3,4,5,6]))

CodePudding user response：

Consider adding a couple of base cases for when the length of lst is 1 or 0:

def merge_sum(lst):
    if not lst: return 0
    if len(lst) == 1: return lst[0]
    middle = len(lst) // 2
    first_half = merge_sum(lst[:middle])
    second_half = merge_sum(lst[middle:])
    return first_half   second_half

print(merge_sum([1, 2, 3, 4, 5, 6]))

Output:

CodePudding user response：

Your recursive function needs base cases for when the list gets adequately small, and you need to make sure that each time the base case isn't hit, the list gets smaller. The midpoint should be half the length, not half (the length minus one) -- otherwise when the list reaches 2 elements long, your midpoint will be 0 ((2-1)//2 == 0), and you'll never be able to divide it further.

>>> def merge_sum(arr):
...     if len(arr) == 1:
...         return arr[0]
...     if len(arr) == 0:
...         return 0
...     middle = len(arr)//2
...     return merge_sum(arr[:middle])   merge_sum(arr[middle:])
... 
>>> merge_sum([1, 2, 3, 4, 5, 6])
21

Note that calling a parameter list is troublesome because list is already the name of the list type in Python, and overwriting it can break your code (or at least make it confusing to read).

CodePudding user response：

Those list[middle:] are needlessly expensive copies of the list. Recursion is a control structure, a loop, you can do it with just moving counters along the same list structure:

def merge_left(numbers, index, total=0):
  if index < 0:
    return total
  else:
    return merge_left(numbers, (index-1), (total numbers[index]))

def merge_right(numbers, index, total=0):
  if index == len(numbers):
    return total
  else:
    return merge_right(numbers, (index 1), (total numbers[index]))

 
def merge_sum(numbers):
  
    middle = len(numbers)//2
    return merge_left(numbers, middle-1)   merge_right(numbers, middle)

print(merge_sum([1,2,3,4,5,6]))

This is a lot more code than the other answers, but I think that makes the left/right distinction more clear. All it passes is an index and a running total each time through the loops.

It's quite possible to combine them both into one function, but it then needs a way to indicate the direction and adjust the index, which makes it less nice.