递归求和函数的辅助空间复杂度是O(n)还是theta(n)？

你为练习递归编写的前n个数字求和函数实现如下：

int sum(int n)
{
   if (n==0)
     return 0;
   
   return n + sum(n-1);
}

针对你疑问的辅助空间复杂度是O(n)还是Θ(n)的问题，结论是：两个表述都成立，其中Θ(n)是更精准的描述。日常交流中很多人习惯用大O符号泛指所有渐进复杂度，但从严格的渐进符号定义出发，两个标记的适用场景有明确区别：

• 首先看该函数的实际空间开销：这个递归写法不属于可优化的尾递归形式——递归调用sum(n-1)返回后，还需要和当前层的参数n做加法运算才能得到最终结果，因此无论编译器是否开启尾递归优化，每一层递归调用都必须在程序调用栈上保留独立的栈帧，存储当前参数、返回地址等运行时信息。从输入n触发第一次调用，一直递归到基准情形n=0，总共会产生n+1层栈帧，除此之外没有其他随输入规模变化的额外内存开销，整体辅助空间占用和输入n呈严格线性关系。
• 对应两个渐进符号的判定规则：
  • O(n)描述的是算法空间开销的渐进上界，即空间增长速度不会超过线性级别，这个描述对该函数完全成立，但精度较低。
  • Θ(n)描述的是算法空间开销的渐进紧确界，即空间增长既不会超过线性级别，也不会低于常数倍的线性级别，不存在“最好情况仅需常数空间、最坏情况才需要线性空间”的波动。对这个固定递归深度的实现来说，只要输入是合法的非负整数n，栈深度就固定为n+1，空间占用稳定落在线性区间，因此完全符合Θ(n)的判定标准。

补充说明：如果将函数改写为尾递归形式（把累加值通过函数参数透传，递归调用作为函数最终的返回操作），在支持尾递归优化的编译环境下，辅助空间可以降到O(1)，但你当前的练习写法不满足尾递归的要求，不适用这个优化场景。

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