递归调用计入空间复杂度吗？

Question

当一个算法没有使用超过一个固定数量的辅助存储器但是有递归调用（每个调用在堆栈上占用一些额外的空间）时，算法的空间复杂度是O(1)还是O(log(N))？

Answer 1

如果递归算法不利用尾递归，那么，是的，一个简单的实现将使用O（log（N））空间。这是因为运行时必须将O（1）大小的O（log（N））堆栈帧一次保存在内存中。