虽然我看了很多教程和课本读物，但在计算递归空间复杂性方面，我无法得到一个明确的答案.
大多数解释利用非常简单的递归函数，例如下面的阶乘函数:
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
在上面的例子中，实际函数本身占用O(1)个辅助空间.然而，由于这是一个递归函数，我们还必须考虑这样一个事实，即调用将同时占用调用堆栈上的堆栈框架.当我们处于最大递归深度时，执行此函数所需的最大堆栈帧数量就达到了.在这种情况下，如果我们认为n是第0级的初始函数调用，那么我们的最大深度将在第n-1级达到，这意味着总共有n个级别.因此，所需堆栈帧的数量与n成正比；空间复杂度为O(N).
虽然这些例子既有教育意义又有帮助，但我找不到实际函数的空间复杂度不是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).那么，在这样的情况下，我们如何最终计算递归函数的总空间复杂性，并将调用堆栈也计算在内呢？
我们是否将每个级别(从级别0到级别n-1)上的单个递归函数占用的空间相加，并对其应用大O记法？
在这种情况下，第0级上的单个函数调用需要n个空间，第1级上的单个函数调用需要n-1个空间，第2级上的单个函数调用需要n-2个空间，依此类推.
因此，总空间可以用以下n个术语总和来表示:
N+n-1+n-2+....+2+1=n(n+1)/2
因此，使用大O记数法，空间复杂度将简化为O(n^2).这样对吗？更广泛地说，我想知道如何计算递归空间复杂性，特别是当我们的函数本身没有O(1)辅助空间时.