I agree with your post up until the point about tail recursion. Tail recursion is *easily* eliminated by reducing the recursion to a simple loop. This is much friendlier on your stack, and much more efficient! Other forms of recursion are harder to eliminate, but the refactoring of tail recursion is well known.
That being said, tail recursion often serves as as decent way to design an algorithm originally, but it should be eliminated when you get the chance.
In his case, assume the program is a "C" program implemented as a state machine that will run for years. Tail recursion would chew up a tremendous amount of stack and lead to program termination. Refactored as a simple while loop, the program would run forever.
This is one (not so rare) example where the reality of how a computer works oversteps the theory of basic "computer science". What appears to be logically equivalent is not once you put it on real hardware.
edit: darn, it looks like I'm turning into a CS professor now... run away! run away!