递归地对列表的元素求和

Question

def sum(L):
    if len(L) == 1:
        return L[0]
    i = sum (len (L) // 2)
    if  len(L) > 1:
        return i + i

L=[2,4]

print (sum(L))

当我尝试运行时出现 TypeError: object of type 'int' has no len().

Answer 1

不要命名你的函数 sum，它会隐藏内置函数
实现你的函数，以便清楚地定义一个基本情况和一个递归情况。

对于基本情况，当长度为 1 时，return 该元素。你没看错。
对于递归情况，将您的列表分成两半并递归计算每一半的总和。

def sum_recursive(L):
    if len(L) == 1:
        return L[0]

    idx = len(L) // 2
    return sum_recursive(L[:idx]) + sum_recursive(L[idx:])

sum_recursive 必须始终接收一个列表和 return 一个整数。

一些试运行：

In [5]: sum_recursive([1, 2, 4, 8])
Out[5]: 15

In [6]: sum_recursive([2, 4])
Out[6]: 6

请记住，这将无法处理空列表作为输入。如果您也想考虑到这一点，请将您的基本案例更改为：

def sum_recursive(L):
    if len(L) <= 1:
        return sum(L)
    ...

我们在这里使用内置的 sum 函数，它通过 returning 0 优雅地处理空列表。对于单元素列表，第一个元素是 returned （这也是为什么不要隐藏这些实用函数很重要的原因）。

如果您不想在那里使用 sum，您需要将基本案例分成两部分：

def sum_recursive(L):
    if len(L) == 0:
        return 0
    elif len(L) == 1:
        return L[0]
    ...

Answer 2

在 sum (len (L) // 2) 中，您将整数（len(L) // 2 的结果）作为 L 参数传递给 sum() 函数。（请不要为函数提供与内置函数相同的名称。）递归调用的 sum() 然后尝试在此整数上计算 len(L) == 1，但整数不支持 len() , 所以你会得到有问题的错误信息。您到底想做什么？

Answer 3

我认为您的目标是编写一个递归 sum 函数，不断将列表拆分为更小的块。所以基本上你需要做的是计算中点的索引，然后使用列表切片将第一个子列表和第二个子列表递归地传递回函数，直到达到 0 或 [= 的基本情况剩余 13=] 个元素。

def add(values):
    if len(values) == 0:
        return 0
    elif len(values) == 1:
        return values[0]
    mid = len(values)//2
    return add(values[:mid]) + add(values[mid:])

>>> add([1,2,3,4,5])
15

Answer 4

在你的代码中

i = sum (len (L) // 2)

line 抛出错误，因为在第一次调用 sum() 之后的递归中，您传递的是整数而不是列表

def sum(L):
    if len(L) == 0:
        return 0
    elif len(L) == 1:
        return L[0]
    else:
        index = len(L)-1
        return L[index] + sum(L[0:index])

L=[2,4]

print (sum(L))

递归地对列表的元素求和

Summing the elements of a list recursively

python

algorithm

recursion

divide-and-conquer