My apologies, I interpreted "running out of space" as meaning running out of memory, rather than meaning overflowing the stack.
The tail recursion part isn't right though. If it isn't optimised into a loop, then tail recursion makes no difference at all, you will overflow the stack just as rapidly, not later. If it is optimised into a loop, then you will not overflow the stack at all.
An algorithm that uses an amount of stack proportional to the input N is said to require O(N) space. If it is rewritten to explicitly allocate the storage instead of using stack, it still uses O(N) space.
Not necessarily. If you are computing an aggregation for instance, if your computation is recursive and not tail call optimized, it may overflow the stack but the fixed version will not use additional memory for each iteration.
Otherwise, indeed stack is memory, but the memory in general is usually way less limited than the stack and also running out of memory doesn't have the same security implications as overflowing an unprotected stack.
And, unless you manage to encode everything in the stack, your iterative version will probably take the same amount of memory as your non-optimized recursive version, minus the space used for the stack.
