This is why TCO (Tail call optimization) exists... but of course not all recusion is tail recursion, but I think it can always be written this way, and should always be for arbitrary depth recursion.
Elimination, not Optimization. Either you can rely on it as part of the spec (Elimination) or you can't (Optmization)
Yes, you can always convert direct style code to continuation passing style code. And continuation passing only uses tail calls. This is one of the big advantages of CPS. Of course if you don't have a tail call optimization, then you overflow the stack pretty quick.