Re: Re: Re: Re: Iterative vs Recursive Processes

Sometimes, no, and yes. :-)

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.

Comment on Re: Re: Re: Re: Iterative vs Recursive Processes

Replies are listed 'Best First'.
Re: Re: Re: Re: Re: Iterative vs Recursive Processes by BrowserUk (Patriarch) on May 13, 2003 at 00:45 UTC
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	[reply]
Re: Re: Re: Re: Re: Iterative vs Recursive Processes by demerphq (Chancellor) on May 13, 2003 at 09:47 UTC
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...}	[reply] [d/l]