I'm no expert on the theory, and have never used lisp, but many algorithms I find far easier to think about in terms of recursion, which means the resulting code (when written in those terms) reads much more naturally and clearly to me.

Let's take that factorial example, and consider what happens if you memoize it - if you calculate factorial(100), you've done in passing the work required to calculate the factorials of 1 .. 99, and the recursive variant will memoize those results as well for no extra work, while the iterative one won't.

The thing is, recursion is a tool like any other, and I wouldn't refuse a better screwdriver simply because I've already got a good hammer.

S'fair enough:) Though I wasn't suggesting that recursion itself was non-useful. I agree that there are many algorithms which are naturally recursive and are much easier to both think of and implement using recursion. Almost anything to do with trees is a good example, but in all the cases I can think of where this is so, retaining state at intermediate points in the repetition is an integral part of the algorithm. Ie. Intrinsic to the delivery of the immediate final result. As opposed to a potential, future final result as can be delivered using the memoize case you cite.

I've not had the occasion to use Memoize in anger, but I read some of Dominus' arguments for it and Streams and stuff, and it is certainly a neat way of speeding up existing code (amongst other uses), but I was struck that it would be cheaper in memory and quicker to just re-code the original function to use a lookup table, though I can see this doesn't have the infinite list feature, but then I don't have infinite memory either:).

I very definately agree that dismissing any better screwdriver out-of-hand is silly. I was just hoping I might get some good counterpoints to the tail-recursion-is-a-hack -elevated-to-goodness argument that I was pretty much convinced by several years ago.

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

In a few languages, Scheme being one of them, there are no built-in iteration constructs. They all have to be built up from recursion. In that case it is impossible to recast them as iteration from the ground up, and so tail-recursion is clearly better than the non-existent alternative.

Of course that doesn't hold for most languages. (It doesn't even hold for Scheme if you are willing to ignore how certain iteration constructs are actually built.) In that case tail-recursion is just a way of having the compiler automatically rewrite recursive algorithms as iterative ones. What is done automatically for you by the compiler is perfectly doable by you by hand, so it is fundamentally impossible to come up with any tail-recursive solution which is not rewritable as an iterative one.

However there are problems which are easier to figure out by recursion than they are by iteration. This is generally not obvious in the simple cases where the translation is trivial and familiarity makes iteration always look cleaner, no matter what. But in more complex cases it may be easier to work out the recursive solution, and it is darned easier to take an existing recursive solution and have it automatically optimized for you than to go through and do the optimization by hand.

This is doubly true if (as often happens) you have a recursive solution some of whose callframes can be eliminated and some of which cannot. Trying to optimize by hand becomes a real bear as you start mixing different styles of code, recursion where iteration won't work and iteration where you can optimize the recursion and headaches (plus probably a few bugs) scattered everywhere.

I hadn't realised that tail-recursion optimisations could operate in a 'mixed environment'. That is to say, the last time I took the time to investigate the mechanisms involved, they seemed to only operate in an all-or-nothing manner. I remember several long articles/series in Byte, JoACM and others about techniques for ensuring that tail-recursion wasn't inhibited. That only goes to show how long I have been suffering under the delusion that TR wasn't a useful technique outside of those languages that make a virtue of it.

I'm long overdue taking the time to re-visit the issue I think. Thanks. Now I'm off in search of a nice self-contained example of a mixed recursion/TR algorithm to play with:)

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

In a few languages, Scheme being one of them, there are no built-in iteration constructs.

I think that this is the source of many people fascination with tail recursion. It appeals to the minimalist mentality very much so, (who needs iteration when you have an tail-recursion optimizing compiler). Personally I find such minimalism distateful, which is probably one of the reasons I like Perl.

I have to say that I think iterative solutions tend to have less suprise bugs than recursive. My experience is that recursive solutions often hide hard to find bugs in exceptional cases, but that the same bug in an iterative solution usually results in the algorithm failing completely. So personally I think that reducing recusrion as much as possible is a good thing. I am also perfectly ready to admit that many others who I hold in considerable respect diasgree. :-) I will grant though that as the code scale increases removing recursion becomes more and more difficult.


---
demerphq

_{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...}

Makeshifts last the longest.

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).

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller

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.