Clash Royale CLAN TAG

Is the space complexity of a recursive algorithm necessarily at least as large as the depth of the recursive call?

I am having trouble determining when recursive functions are sub-optimal to their iterative counterparts when space is an issue. When writing recursive functions, is the space complexity necessarily at least as large as the depth of the recursive call if it is not tail recursive?

For example, lets remove duplicates from a linked list using recursion. This can be done trivially with an iterative approach in O(n^2) time and O(1) space. But is the recursive variant also O(1) space?

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;
}


removeDuplicatesRecursive()

1 Answer
1

In the above program, the space complexity is O(n).

O(n)

For recursion, until you reach the base condition, every call to the recursive function including all the arguments, local variables are put into call stack.

For the above program, the most number of function calls happens, when all the elements of the linked list are unique. In that case, n function calls will be made and space complexity will be O(c * n) ~ O(n).

n

O(c * n) ~ O(n)

the worst case of space complexity happens, when all the elements of the linked list are unique.

O(n)

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.