询问递归函数f(n)的空间复杂度为何是O(n)而非O(n!)

先看你给出的递归函数代码：

def f(n):
    sum = 0
    if n == 0:
        return 1
    else:
        for i in range(n):
            sum = sum + f(i)
    return sum

你之前误以为空间复杂度是O(n!)，核心误区是把递归总调用次数和递归栈同时存在的函数数量搞混了，这是两个完全不同的概念：

• 首先明确：递归的空间复杂度取决于递归栈的最大深度，也就是运行过程中同时在栈里的函数调用数量，而不是所有调用的总数。
• 递归栈的工作逻辑是「后进先出」：每调用一次函数就把它压入栈，函数执行完返回时就从栈里弹出。同一时间，栈里只会存在一条完整的调用链，不会同时容纳所有的函数调用。

举个具体例子，比如计算f(3)：

• 先调用f(3)，压入栈；
• f(3)进入循环，先调用f(0)，压入栈；f(0)直接返回，弹出栈，回到f(3)；
• 接着f(3)调用f(1)，压入栈；f(1)调用f(0)，压入栈；f(0)返回弹出，f(1)返回弹出，回到f(3)；
• 然后f(3)调用f(2)，压入栈；f(2)调用f(0)，压入栈；f(0)返回弹出，f(2)调用f(1)，压入栈；f(1)调用f(0)，压入栈；f(0)返回弹出，f(1)返回弹出，f(2)返回弹出，回到f(3)；
• 最后f(3)计算完sum返回，弹出栈。

整个过程中，栈的最大深度是4（对应f(3) → f(2) → f(1) → f(0)的调用链），也就是n+1个，和输入规模n成正比，所以空间复杂度是O(n)。

而你想到的调用总数（实际这个函数的总调用次数是指数级，并非阶乘级）属于时间复杂度的范畴——时间复杂度统计的是所有执行的操作次数，和空间复杂度没有直接关联。

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