递归空间复杂度计算咨询：含非O(1)辅助空间场景

问题示例 #

你给出的阶乘函数如下：

def factorial(n):
  cool = [i for i in range(n)]
  if n == 1:
    return 1
  return n * factorial(n - 1)

该函数每次调用都会创建长度为n的列表，自身辅助空间复杂度为O(n)，你疑惑此时总空间复杂度是否需要累加各递归层级的空间，最终得到O(n²)。

结论：总空间复杂度确实为O(n²) #

递归调用采用栈式执行逻辑：每一层函数调用的局部变量（包括这里的cool列表）都会被保存在独立的栈帧中，直到该层调用执行完成并返回。对于这个阶乘函数，递归深度为n（从factorial(n)到factorial(1)共n层），第k层调用（对应factorial(k)）的辅助空间为O(k)，因此总空间开销是1+2+...+n = n(n+1)/2，用大O表示即为O(n²)。

递归空间复杂度通用计算方法 #

1. 确定递归栈最大深度D：即同一时刻存在的递归栈帧的最大数量。比如线性递归（如阶乘、线性求和）的D等于输入规模n；二叉树递归遍历的D等于树的高度（平衡树为O(logn)，退化为链表则为O(n)）。
2. 计算单个栈帧的辅助空间S(k)：这里的k代表递归层级对应的输入规模，S(k)是该层调用中除了栈帧固定开销（如返回地址、参数存储）之外，额外开辟的辅助空间（比如列表、哈希表、临时对象等）的空间复杂度。
3. 总空间复杂度计算：
   • 若所有栈帧的S(k)均为O(1)，总空间复杂度等于递归栈深度的复杂度，即O(D)；
   • 若S(k)随输入规模变化，则需要累加所有同时存在的栈帧的S(k)，再取其大O表示；
   • 特殊情况：如果是尾递归且语言支持尾递归优化（比如Scheme、部分编译型语言），所有递归调用会复用同一个栈帧，此时总空间仅需考虑当前栈帧的辅助空间，即O(S(n))。但Python默认不支持尾递归优化，因此尾递归在Python中仍按普通递归计算空间。

补充示例 #

• 示例1：每层辅助空间固定O(1)的递归

def factorial_simple(n):
    if n == 1:
        return 1
    return n * factorial_simple(n-1)

总空间复杂度为O(n)，因为每层仅需固定空间，累加后为O(n*1)=O(n)。

• 示例2：每层辅助空间与输入规模正相关的递归

def sum_recursive(n):
    temp = [0] * n  # 辅助空间O(n)
    if n == 0:
        return 0
    return n + sum_recursive(n-1)

递归深度n，每层辅助空间依次为O(n)、O(n-1)...O(1)，总空间复杂度为O(n²)。

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