It is easy to eliminate tail recursion.
There are few curious cases where the not-tail recursion can also be eliminated.
Exhibit 1: Fibonacci numbers.
A naive recursive solution
fib(n) if (n < 2) return n return fib(n-1) + fib(n-2)
leads to exponential complexity. An iterative solution
fib(n) f_0 = 0 f_1 = 1 for i = 2; i < n; ++i f = f_0 + f1 f_0 = f1 f_1 = f return f
is linear. I know I can have a logarithmic one, but it's besides the point.
Exhibit 2: merge sort
A recursive solution
merge_sort(begin, end) mid = begin + (end - begin) merge_sort(begin, mid) merge_sort(mid, end) merge(begin, mid, end)
(which is not as bad as Exhibit 1, but still) also allows an iterative version:
merge_sort(begin, end) for stride = 2; stride < end - begin; stride *= 2 for start = begin; start < end; start += stride merge(start, start + stride/2, start + stride)
These seemingly unrelated exhibits share a common trait: there is no job done on the way down1.
The real questions are,
does this trait warrant that elimination is possible,
is it possible to identify it, and
once identified, is there a mechanical way to actually eliminate the recursion.
Disclaimer: I am only interested in elimination without using a stack. I know it is always possible to eliminate recursion introducing a stack like shown in General way to convert a loop (while/for) to recursion or from a recursion to a loop?
 Nobody is going to rob us going down the mountain. We have got no money going down the mountain. When we have got the money, on the way back, then you can sweat.