CODEWITHSUNDEEP
javac++crecursionspace-complexity
Adi agarwal
Adi agarwal

Reputation: 178

Should we consider recursive call stack as auxiliary space?

Should we consider recursive call stack as auxiliary space used by the program? I think it should be considered only when calculating space complexity, but not in calculating the auxiliary space.

Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size.

Upvotes: 0

Views: 1178

Answers (1)

ruakh
ruakh

Reputation: 183456

If you're actually relying on variables in outer calls — if you'll need them again after your innermost call returns — then yes, they should be included in the auxiliary space.

But if all you have are tail calls, and the only reason your stack is growing is that your compiler doesn't support tail call optimization, then I don't think I would consider that in the auxiliary space of the (abstract) algorithm, even though your actual implementation will end up taking up that space.

Upvotes: 1

Related Questions