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.

This seems orthogonal. The issue with recursion in languages like python is that regardless of where the values in the function are WRT the stack / vs heap, each recursive function call adds a stack frame. If it’s a GCed language (python) there is exactly the same issue WRT accumulating garbage. In fact arguably it’s worse, since there is a live stack frame pointing to the value, whereas in Elixir those frames are replaced and you can garbage collect the value.

The BEAM implements not only tail recursion but actually “last call elimination” where if the last thing a function call does is call a local function, the stack frame of the new function replaces the current stack frame. This allows mutual recursion where two functions recursively call each other.

Therefore:

Yes, in fact it can be identical to the iterative version.

The thing though is, even non tail recursive versions can have the same space constraints. Consider the simple function:

def multiply_by_2([]), do: []
def multiply_by_2([ n | rest]), do: [n * 2 | multiply_by_2(rest)]

This is a body recursive function, and therefore it will accumulate stack frames. The space complexity of this is O(n). The thing is, the space complexity of the iterative version is… also O(n). Now, because of immutable data, the Elixir version may generate more garbage, but honestly that depends entirely on the underlying implementation of lists / arrays in the language.