递归函数递推关系中列表切片的时间复杂度项是否合理？

最近几周一直在学习时间复杂度，重点研究递归函数的相关内容，基本概念已经理解，但遇到一个场景还是有点困惑，拿下面这个Python递归函数举例：

def foo(l):
    if len(l) == 0:
        return 0
    return 1 + foo(l[1:])

我纠结的点是l[1:]这个列表切片操作的开销该怎么算进递推关系里。我知道创建子列表（也就是列表切片）的时间复杂度是O(M)，M是子列表的长度，那写递推式的时候该怎么把这部分开销加进去？

我自己推的递推式是这样的：

T(n) = T(n-1) + n - 1 + 4    

T(0) = 4

推导逻辑：

• 常数项4代表每次递归调用的固定开销，比如判断列表长度、返回值这些操作，具体数值可以是任意常数；
• n-1是因为把长度为n的列表切片成n-1长度的子列表，开销等于子列表长度，也就是n-1；
• T(n-1)表示输入规模为n时，会递归调用一次输入规模为n-1的自身。

想请教下这个逻辑对不对？递推式里的n-1项是不是确实对应创建长度为n-1的子列表的开销？

你的推导逻辑是完全正确的。

首先，Python的列表切片l[1:]确实需要创建一个新列表，并且要把原列表中从索引1到末尾的所有元素复制到新列表里，这个复制操作的次数正好等于新列表的长度，也就是n-1（当原列表长度为n时），所以这部分的时间开销就是O(n-1)，完全对应你递推式里的n-1项。

我们可以把递推式展开验证：
将递推式中的常数4替换为通用常数C，得到：

T(n) = T(n-1) + (n-1) + C
T(n-1) = T(n-2) + (n-2) + C
...
T(1) = T(0) + 0 + C

将所有式子累加后：
T(n) = T(0) + Cn + (0+1+2+...+(n-1))
其中0到n-1的和为n(n-1)/2，T(0)=C，代入后可得：
T(n) = C + Cn + n(n-1)/2
其时间复杂度为O(n²)，这也符合实际：这个递归函数本质是计算列表长度，但每次递归都要复制子列表，总开销是1+2+...+(n-1)，确实是平方级别的，和直接调用len(l)的O(1)效率差很多，这也侧面印证了你的递推式是正确的。

额外补充：如果想优化这个递归的时间复杂度，可以通过传递索引参数避免切片，比如修改为：

def foo(l, idx=0):
    if idx >= len(l):
        return 0
    return 1 + foo(l, idx+1)

这样就省去了每次复制列表的开销，时间复杂度会降到O(n)。

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