关于递归与空间复杂度

一般递归会算进空间复杂度吗？
例如：
public int zero1(int n) {
    while (n > 0) {
        n--;
    }
    return 0;
}
zero1 的空间复杂度是 O(1)

但是。。
public int zero2(int n) {
    if (n <= 0) return 0;
    return zero(n - 1);
}
zero2 的空间复杂度是 O(n) 还是 O(1) ？

（额外）空间复杂度是在程序中除了输入输出以外所需要用的内存空间大小，无论这个内存如何分配，分配到哪里，不应该影响空间复杂度的取值。所以，递归的空间复杂度至少是O(递归深度)。否则，如果zero2的空间复杂度是O(1)，那么很多其他算法：比如二叉树普通先序遍历和快排等的空间复杂度也都是O(1)了。这个逻辑就好比说，因为我们“看不见这个内存分配的过程，所以这个内存分配不存在”。至少我认为这个逻辑是不能接受的。

当然，或许你的面试官会有不同意见，所以你可以说：“The program takes O(N) space on the call stack. So if that counts, the space complexity should be ... ”。这样既不会给出错误答案，又表示你确实知道这个内存分配发生在什么地方。

不过，像zero2这种尾递归，有可能编译器能够自动识别并优化成zero1的形式（比如gcc可以，Java我就不太清楚）。这点如果你了解的话也可以跟面试官提。

space complexity 主要是指的是在内存上额外开辟的空间，比如DP的一维二维数组。 recursive call因为是系统自行去分配和释放内存，这个过程一般面试不太会问，问起了因为这是一个动态的过程所以你也不好回答。如果真的遇见了要问recursive的空间复杂度，你自己在白板上画一下递归树好了。

stellari 发表于 2015-7-17 13:42
（额外）空间复杂度是在程序中除了输入输出以外所需要用的内存空间大小，无论这个内存如何分配，分配到哪里 ...

tail call么? 听说8有, 具体就没听过有人说怎么优化了, 这种优化局限性很大....

每一次调用函数,形参就需要开辟存储空间,所以回答O(n)比较靠谱