Python递归列表复制算法的空间复杂度分析咨询

先看你给出的递归实现代码：

def list_copy_rec(list_1, i):
    if i == len(list_1):
        return []  
    return [list_1[i]] + list_copy_rec(list_1, i + 1)

你的判断方向是对的，这个算法的空间复杂度确实是O(n)，下面拆解两部分核心影响因素：

1. 递归调用栈的空间占用 #

递归的深度等于列表的长度n——因为每次调用i递增1，从0到len(list_1)一共会产生n+1层递归调用（最后一次调用i == len(list_1)返回空列表）。每一层递归调用都会在栈中保存函数的上下文（比如参数list_1、i，以及返回地址等），这部分的空间开销是O(n)。

2. 列表拼接产生的临时列表 #

每次执行[list_1[i]] + list_copy_rec(...)时，都会创建新的临时列表：

• 当递归走到最深层（返回空列表），上层调用会创建一个包含1个元素的列表；再往上一层，会把当前元素和这个1元素列表拼接成2元素列表，以此类推，直到最上层生成完整的n元素列表。
• 这些临时列表的总空间开销也是O(n)：因为每一层的临时列表长度从1到n累加，但实际上，当上层的拼接完成后，下层的临时列表就会失去引用，会被垃圾回收机制回收。不过在复杂度分析中，我们通常关注的是峰值内存占用——这里的峰值是最终生成的n长度列表，加上递归栈的O(n)，总空间量级仍然是O(n)（O(n)+O(n)归并后还是O(n)）。

简单总结：不管是递归栈的开销，还是拼接产生的临时列表，它们的空间量级都是O(n)，所以整体空间复杂度是O(n)。

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