Jeff Cunningham  <jeffrey@cunningham.net> wrote:
+---------------
| Duane Rettig wrote:
| > [Assuming "tail recursion" -> "tail merging"]:
| > This is the wrong motiviation for tail-merging.  You will sometimes
| > get speedups, but you will also sometimes get slower code.
| 
| So what criterion do you use when deciding how to write a recursion?
| Is it purely for clarity? Or are there performance reasons you can
| rely upon? 
+---------------

You write recursive algorithms when the data you're traversing or
the algorithm you're performing are expressed naturally in a
recursive fashion, e.g., walking a tree or graph.

You write iterative algorithms when the data you're traversing or
the algorithm you're performing are expressed naturally in a
iterative fashion, e.g., counting, summing, searching arrays,
successive approximation, etc.

OCCASIONALLY you may want [for simplicity] or need [to avoid stack
explosion] to write an iterative algorithm for a "naturally recursive"
problem or vice versa [e.g. a recursive paritition sort instead of
a linear insertion sort], but by & large it's generally best to stick
to the natural "shape" of the data or the mathematics at hand.


-Rob

p.s.  Even though it uses Scheme for its examples [and thus tends to
put much more weight on the recursive side], "How To Design Programs"
<http://www.htdp.org/> provides a good introduction to data- or problem-
directed software design, especially the sections on "design recipes"
<http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-5.html#node_sec_2.5>
and <http://www.htdp.org/2003-09-26/Book/curriculum-Z-H-16.html#node_sec_12.1>
"designing complex programs".

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607