sumlist by divide and conquer algorithm

Question

i want use divide and conquer algorithm for sum but when i run my code i get the below message

Traceback (most recent call last): File ".py", line 8, in print(Sumlist([10,80,30,60,120,150])) File ".py", line 6, in Sumlist return Sumlist(thelist[:mid])+Sumlist(thelist[mid:]) File ".py", line 6, in Sumlist return Sumlist(thelist[:mid])+Sumlist(thelist[mid:]) File ".py", line 6, in Sumlist return Sumlist(thelist[:mid])+Sumlist(thelist[mid:]) [Previous line repeated 995 more times] File "***.py", line 2, in Sumlist if thelist==[]: RecursionError: maximum recursion depth exceeded in comparison

def Sumlist(thelist):
    if thelist==[]:
        return 0
    else:
        mid=len(thelist)//2
        return Sumlist(thelist[:mid])+Sumlist(thelist[mid:])
print(Sumlist([10,80,30,60,120,150]))

Answer 1

Your code is getting into infinite recursion because there is no base case for when there is 1 element in the list.

For len(thelist) == 1, it infinitely divides into 2 lists of lengths 0 and 1.

Following code should work:

def Sumlist(thelist):
    if not thelist:
        return 0
    if len(thelist) == 1:
        return thelist[0]
    
    mid=len(thelist)//2
    return Sumlist(thelist[:mid]) + Sumlist(thelist[mid:])
        
print(Sumlist([10,80,30,60,120,150]))

Answer 2

The base case can also check if "mid == 0" and terminate the recursive calls. The code could be;

def sum_list(the_list):
    if  the_list == []:
        return 0
    mid = int(len(the_list) / 2)
    if  mid == 0:
        return the_list[mid]
    else:
        return sum_list(the_list[:mid]) + sum_list(the_list[mid:])