递归函数的空间复杂度计算及调用栈是否计入的相关问题

1. 该算法的空间复杂度 #

你给出的递归代码修正语法错误后如下：

void print(int &N){
    if(N==0)
        return;
    cout << N << " ";
    N = N-1;
    print(N);
}

该算法的空间复杂度为 O(N)。
原因：该递归实现的最大调用栈深度和输入参数N的大小呈线性正相关。初始输入为N时，递归会依次执行print(N)、print(N-1)……直到print(0)触发终止条件，整个过程中调用栈最多会同时存在N+1个函数实例，没有其他额外的内存开销，因此整体空间复杂度为O(N)。

2. 递归调用栈是否纳入空间复杂度计算 #

需要分场景判断：

• 常规的算法空间复杂度计算，要求衡量算法运行的整体内存开销，必须将递归调用栈的占用纳入考量，这部分消耗直接决定了算法的内存成本，以及是否会出现栈溢出问题。
• 仅当题目或评估规则明确要求只统计显式申请的辅助空间（即开发者手动分配的堆、栈空间，排除程序运行默认的函数调用栈开销）时，才可以忽略递归调用栈的占用。

补充说明：你给出的这段代码属于尾递归结构，如果编译器开启了尾递归优化，会直接复用当前函数的栈帧，不会生成新的栈空间，这种情况下空间复杂度会降至O(1)。但绝大多数C/C++编译器默认不会开启尾递归优化，因此常规评估下该算法的空间复杂度还是按O(N)计算。

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