I wasn't saying that recursion was not useful. Many, many algorithms that use divide-and-conquor strategies are not only much simpler implemented using recursion, in many cases the only way to avoid the recursion is to emulate the stack frames in order to retain state. This emulation is almost always more complex, usually slower and always more bug prone than the clean simplicity of the recursive version.

My question was, is there an algorithm that benefits from tail-recursion optimisation that isn't easily recast to an iterative solution. Tilly mentioned some that can benefit from TR at some iterations, but not others.

I think that QuickSort may be one such algorithm.

I'm pretty certain there is no strategy that would allow the QuickSort algorithm to benefit from all-or-nothing TR, as the pivot points are determined on the way in, but still required on the way out. However, whilst the pivot point is still required when returning from the first recursion to the Qsort call, the return from the second call could, in theory at least, return back two stack frames as the localised state information is no longer required. This is a situation where transparent TR would benefit the algorithm. (I think).

Right. An example that comes to mind (because I've implemented that iteratively in my Assembly days) is pre-order traversal of a binary tree. Descending to a left child node can be handled by tail recursion. When there is no right child node, this can be completely transparent as you won't need to return to the node in question.

Makeshifts last the longest.