Space complexity of recursive algorithms

It depends on the values being recursed over and if they can be stored on the stack. Some values may be stored in the heap. So, even though there is no stack frame pointing to it, because of the frame being replaced, the value on the heap is still there until it gets garbage collected. Stuff that can be allocated on the stack are usually small values, like small strings and numbers.

1 Like