为什么以这种方式递归，这意味着什么

Question

>我试图理解这段代码

def listSum(ls):
    if not ls:
        return 0
    return ls[0] + listSum(ls[1:])

有两件事让我有点烦恼

1. if not ls: - 这是什么意思？由于没有指定任何内容，它在寻找什么？
2. ls[0] + listSum(ls[1:]) - 我尝试仅使用listSum(ls[0:])，但运行错误。为什么？我为什么要坚持ls[0] + listSum(ls[1:])？

Answer 1

想象一下它被称为...

listSum([3, 5, 3, 7])

它归结为...

return ls[0] + listSum(ls[1:])

。评估为...

return 3 + listSum([5, 3, 7])

然后listSum([5, 3, 7]) 5 + listsum([3, 7]).

然后listSum([3, 7]) 3 + listsum([7]).

然后listSum([7]) 7 + listsum([])，这是not ls启动并返回0的地方。

因此，然后将完整的内容评估为...

3 + 5 + 3 + 7 + 0

笔记：

• listSum(ls[1:])每次都缩短列表 - 降低剩余问题的复杂性，直到调用listSum收到空列表：if not ls: return 0处理的琐碎情况

• 递归解决方案通常由两部分组成：一个是最简单的输入解决方案（或者有时是几个非常简单的情况），以及说明如何采用任意复杂的输入并将其简化为一个公式，进行一个或多个回避调用，每个调用至少简单一点，始终朝着最简单的输入移动

• "我试过使用listSum(ls[0:])" - ls[0:]返回ls的副本 - 它会要求无限期地处理相同的列表

• 可以说，显式处理一个元素的列表 - if len(ls) == 1: return ls[0] - 更直观，但如果有人调用listSum([])，您将尝试访问[0]（在if下面的其他代码中）并引发异常; 如果返回0对应用程序来说是合理的listSum([])，则处理空列表会使函数更易于使用， 但另一方面，listSum([])引发异常可能会发现列表意外为空的错误 - 您可以决定哪个对您更有用;很高兴，如果您确实处理了空列表情况，那么len(ls) == 1情况则使用相同的递归逻辑"正常工作"