If you have exponential run times, I don't think tail call optimization would help you.

Of course, that claim with the exponential run time in the first place is ludicrous: sure, you'll have a hard time implementing the Ackermann function with loops. But that's a problem with loops, not with function calls.

I say function calls here, because recursion in function is just a special case of function calls. You gotta have functions in a modern language in any case, so recursion comes for free. No need to introduce another concept like loops and clutter up your language.