递归算法的空间复杂性是否必须至少与递归调用的深度相同?

当空间是一个问题时,我很难确定递归函数何时比迭代函数次优。在编写递归函数时,如果空间的复杂性不是尾部递归的,那么它是否至少与递归调用的深度一样大?

例如,让我们使用递归从链接列表中删除重复项。这可以用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;
  }