该递归函数的时间复杂度与空间复杂度是否均为O(log n)？

首先纠正函数的笔误，正确的带参数版本应为：

function logN(n) {
    if (n === 0) return;
    logN(n / 2);
}

空间复杂度：确实为O(log n) #

递归的空间复杂度由调用栈的最大深度决定。每次递归调用都会在调用栈中保存栈帧（包含函数参数、局部变量等），直到递归终止才会释放。题目中提到递归最大深度是O(1 + log n)，去掉常数项后就是O(log n)，因此空间复杂度为O(log n)。

时间复杂度：同样为O(log n) #

时间复杂度衡量的是所有执行操作的总次数：

• 每次递归调用内部只有n === 0的条件判断和下一次递归调用，这些都是O(1)级别的操作；
• 递归调用的总次数等于递归深度，也就是O(log n)次（从初始n开始，每次除以2直到等于0，调用次数约为log₂n + 1，去掉常数项后即为O(log n)）。
  就算把函数调用本身的开销纳入考量，每次调用是O(1)，总次数是O(log n)，因此总时间复杂度也是O(log n)。

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