CODEWITHSUNDEEP
javascriptalgorithmrecursionlinked-list
Marc Fletcher
Marc Fletcher

Reputation: 1082

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

Upvotes: 3

Views: 251

Answers (1)

Kaidul
Kaidul

Reputation: 15885

In the above program, the space complexity is 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 will happen 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(n).

Upvotes: 3

Related Questions