Are there algorithms that would benefit from tail recursion optimisation -- which I have always taken to mean that they left nothing in the stack frame by way of intermediate data or state that was required when unwinding -- that aren't readily and easily re-cast as interative algorithms in the first place?

Factorial isn't a great example, but it is a common one

sub factorial { 
    my ($f,$n) = (1,shift); 
    $f *= $n-- while( $n ); 
    $f; 
}
[download]

To my eyes, even with 1-char variable names and no comments, this is so much clearer than the equivalent recursive routine that I can't understand why I would do it any other way.

The big hole in my language experience is any serious use of the lisp-ish branch of the family. To my shame, I never got passed the 'Loads of Infuriatingly Stupid Parenthesis' (and rediculously terse and meaningless keywords), state-of-mind. I tried a couple of times to go back and address this ommision, but I encounter the same Aaaaarg! sensations every time.

The whole tail-recursion debate seems to stem from those languages where recursion is used almost exclusively (it's an exageration I know, but not so much of one) to perform any form of repetition. Early on, they found that using recursion for essentially iterative algorithms caused explosive memory usage to little benefit, so they invented tail-recursion. The invention was very successful in decreasing the inefficiencies of this practice, and so the original bug-fix-hack, has taken on the status of an, algorithmically, 'fundementally good idea'⁺.

So my question is: Can anyone educate me, by showing me an algorithm that is better (by some definition) implemented using a tail-recursive method than an iterative method.

⁺ I am not the originator of these notions, but I couldn't find an authoratative quote anywhere, and as I am no longer in contact with the person who expressed them, convincingly, to me, I'm quite happy to take the rap for them.