求和分治算法

Question

我希望对和使用分而治之的算法，但是当我运行我的代码时，我得到以下消息

跟踪(最近一次调用)：文件".py"，第8行，打印( Sumlist (10，80，30，60,120,150))文件".py"，第6行，在Sumlist返回Sumlist(thelist:mid)+ Sumlist (thelistmid:) File ".py"，第6行，在Sumlist返回Sumlist(thelist:mid)+Sumlist(thelist：) File ".py"，第6行，在Sumlist返回Sumlist(thelist:mid)+Sumlist(thelistmid:)前面重复了995次"***.py"，第2行，在Sumlist中，如果thelist==[]：RecursionError:比较超过最大递归深度

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

您的代码正在进入无限递归，因为在列表中有一个元素时，没有基本的大小写。

对于len(thelist) == 1，它无限地分为两个长度为0和1的列表。

以下代码应该有效：

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

基本大小写还可以检查是否“中间== 0”并终止递归调用。守则可能是；

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:])