# 三、给定一个整数列表 L，输出一个列表 S，其中 S[i]为 L[0] 到 L[i]的和。例如 L=[1,2,4,2], 则输出 S=[1,3,7,9]。 # 用简单递归方式和二分法递归实现此程序。

使用简单递归方式实现：

def prefix_sum(L):
    if not L:
        return []
    elif len(L) == 1:
        return [L[0]]
    else:
        S = prefix_sum(L[:-1])
        S.append(S[-1] + L[-1])
        return S

使用二分法递归实现：

def prefix_sum(L):
    if not L:
        return []
    elif len(L) == 1:
        return [L[0]]
    else:
        mid = len(L) // 2
        left = prefix_sum(L[:mid])
        right = prefix_sum(L[mid:])
        return merge(left, right)

def merge(left, right):
    S = []
    i = 0
    j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            S.append(left[i])
            i += 1
        else:
            S.append(right[j])
            j += 1
    S += left[i:]
    S += right[j:]
    return S

其中，merge函数用于将两个有序列表合并成一个有序列表。二分法递归的思路是将原列表分成两个子列表，分别递归求解并合并。