14

在以下代码中：

def listSum(alist):
    """Get sum of numbers in a list recursively."""
    sum = 0
    if len(alist) == 1:
        return alist[0]
    else:
        return alist[0] + listSum(alist[1:])
    return sum

每次我这样做时都会创建一个新列表listSum(alist[1:])吗？

如果是，这是推荐的方式还是我可以做一些更有效的事情？（不是针对特定功能 - 这作为示例 - 而是当我想处理列表的特定部分时。）

编辑：

抱歉，如果我让任何人感到困惑，我对有效的sum实现不感兴趣，这是以这种方式使用切片的示例。

4

3 回答 3

9

是的，它每次都会创建一个新列表。如果您可以不使用可迭代对象，则可以使用itertools.islice, 或 juggle iter(list)（如果您只需要在开始时跳过一些项目）。但是当您需要确定参数是空的还是只有一个元素时，这会变得混乱 - 您必须使用try和 catch StopIteration。编辑：您还可以添加一个额外的参数来确定从哪里开始。与@marcadian 的版本不同，您应该将其设为默认参数，以免给调用者带来负担，并避免从外部传入错误索引的错误。

通常最好不要陷入这种情况 - 要么编写代码，以便可以for处理迭代（阅读：不要像那样使用递归）。或者，如果切片相当小（可能是因为整个列表很小），无论如何都要咬紧牙关切片 - 它更容易，虽然切片是线性时间，但常数因子确实很小。

于 2013-08-26T01:12:46.273 回答
3

我可以想到一些选择：

  1. 在这种特殊情况下使用内置函数 sum
  2. 如果您确实需要递归（出于某种原因），请将相同的列表传递给函数调用以及当前元素的索引，因此您不需要对列表进行切片（这会创建新列表）

选项 2 的工作方式如下：

def f_sum(alist, idx=0):
    if idx >= len(alist):
        return 0
    return alist[idx] + f_sum(alist, idx + 1)


f_sum([1, 2, 3, 4])
a = range(5)
f_sum(a)
于 2013-08-26T01:13:04.503 回答
-1

如果您必须使用递归（尾递归），这是另一种方式。在许多其他语言中，就空间复杂度而言，这比常规递归更有效。不幸的是，python 中并非如此，因为它没有内置支持优化尾调用。尽管如此，如果您正在学习递归，请注意这是一个很好的做法。

def helper(l, s, i):
    if len(l) == 0:
        return 0
    elif i < len(l) - 1:
        return helper(l, s + l[i], i + 1) 
    else:
        return s + l[i]


def listSum(l):
    return helper(l, 0, 0)
于 2013-08-26T01:23:46.633 回答