我们应该把递归调用堆栈作为辅助空间吗？

Question

我们应该把递归调用堆栈作为程序使用的辅助空间吗？我认为只应在计算空间复杂度时考虑这一点，而不应在计算辅助空间时加以考虑。

辅助空间是算法使用的额外空间或临时空间。算法的空间复杂度是算法相对于输入大小所占的空间总数。

Answer 1

如果您实际上依赖于外部调用中的变量--如果在最内部的调用返回之后还需要它们--那么是的，它们应该包含在辅助空间中。

但是，如果您拥有的只有尾呼叫，并且您的堆栈正在增长的唯一原因是编译器不支持尾调用优化，那么我不认为我会在(抽象)算法的辅助空间中考虑这一点，即使您的实际实现最终会占用这个空间。