当空间成为问题时,我无法确定递归函数何时与其迭代函数相比不是最优的。写递归函数的时候,如果不是尾递归,空间复杂度是否一定至少和递归调用的深度一样大?
例如,让我们使用递归从链表中删除重复项。这可以通过 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;
}
最佳答案
在上面的程序中,空间复杂度是O(n)
。
对于递归,在到达基本条件之前,对递归函数的每次调用,包括所有参数,局部变量都被放入调用堆栈。
对于上面的程序,当链表的所有元素都唯一时,函数调用次数最多。在这种情况下,将进行 n
次函数调用,空间复杂度将为 O(n)
。
关于javascript - 递归算法的空间复杂度是否一定至少与递归调用的深度一样大?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51576067/