如何通过递归方法对列表拆分的两半进行求和

问题代码缺陷 #

你提供的代码存在两个核心错误：

• 缺少递归终止条件，会无限触发递归调用，最终抛出递归深度超过上限的报错
• 中间位置计算逻辑错误，int(len(list)-1)//2会导致长度为1的列表拆分后仍存在非空的子列表，无法终止递归

正确实现代码 #

def merge_sum(lst):
    # 递归终止：空列表返回0，单元素列表直接返回元素值
    if len(lst) == 0:
        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]))

运行以上代码会输出正确结果21，符合预期。

实现说明 #

递归拆分的终止条件是列表长度小于等于1，不再继续拆分，直接返回对应值；中间位直接取列表长度整除2的结果，可以保证两个半区的元素数差值不超过1，拆分逻辑合理。

内容的提问来源于stack exchange，提问作者Shushue