javascript - 递归算法的空间复杂度是否一定至少与递归调用的深度一样大？

Question

当空间成为问题时，我无法确定递归函数何时与其迭代函数相比不是最优的。写递归函数的时候，如果不是尾递归，空间复杂度是否一定至少和递归调用的深度一样大？

例如，让我们使用递归从链表中删除重复项。这可以通过 O(n^2) 时间和 O(1) 空间的迭代方法轻松完成。但是递归变体也是 O(1) 空间吗？

removeDuplicatesRecursive() {
    let current = this.head;

    while (current.next) {
      if (this.head.data === current.next.data) {
        current.next = current.next.next
      } else {
        current = current.next;
      }
    }

    if (this.head.next) {
      removeDuplicatesRecursive(this.head.next);
    }

    return head;
  }

Answer 1

在上面的程序中，空间复杂度是O(n)。

对于递归，在到达基本条件之前，对递归函数的每次调用，包括所有参数，局部变量都被放入调用堆栈。

对于上面的程序，当链表的所有元素都唯一时，函数调用次数最多。在这种情况下，将进行 n 次函数调用，空间复杂度将为 O(n)。