Xref: utzoo comp.edu:3724 uw.general:1965
Path: utzoo!attcan!uunet!cs.utexas.edu!news-server.csri.toronto.edu!neat.cs.toronto.edu!mdhutton
From: mdhutton@theory.toronto.edu (Mike Hutton)
Newsgroups: comp.edu,uw.general
Subject: Re: Recursion Summary
Message-ID: <90Oct26.142612edt.6786@neat.cs.toronto.edu>
Date: 26 Oct 90 18:26:35 GMT
References: <1990Oct23.211651.10227@contact.uucp> <9868@milton.u.washington.edu> <9882@milton.u.washington.edu> <9893@milton.u.washington.edu> <9898@milton.u.washington.edu> <9917@milton.u.washington.edu>
Distribution: na
Organization: Department of Computer Science, University of Toronto
Lines: 52


In article <9917@milton.u.washington.edu> iho@akbar.UUCP (Il Oh) writes:
>If you accept my claim that there's no recursion at the fundamental
>logic level, you must agree that, theoretically, a recursive solution
>can never be more efficient than an iterative one.

Why does efficiency always seem to imply run-time cost?  The 
dominant cost in most (educated guess) applications is the programmer
time, not computer time---not everybody is doing combinatorial problems
or number crunching.

Why not consider space efficiency:  
1. How long is the program.   The recently posted 5 or 6 line quicksort 
is a perfect example of how concise and explicit a recursive program can be.
For big applications, a smaller solution can be much faster time-wise too.
Somebody tell this to the Xwindows people; X is probably thrashing 
as we speak.
2. What is the run-time space.  It is not true in general (consider for
example a recursive factorial function), but many uses of recursion
involve searching a data structure or the input, and would add only 
a constant factor to the space (since you can only search what you have
available to search, and this bounds the recursion stack)

Or programmer efficiency directly:
3. Recursive programs are easier to write, both conceptually and
from (1) above (i.e. typing time), and easier to debug (as a function
of size and complexity).
4. Some people attribute 90% of application cost to maintenance, and
maintenance is a function of readability and size/complexity.  Recursive
programs should be easier to maintain and understand than the 
corresponding iterative versions.


Iteration and recursion are *both* high-level concepts; they belong to
the programmer, not the machine.  Just as translating iteration into
gotos is the job of the compiler, translating recursion into stack operations
and gotos should also be.  In the rare cases where absolute time efficiency is
required, the code is written in high-level, then hand optimized; and
so should be recursion, when necessary.  

>Even though I believe my last statement, I also believe that recursive
>solutions are more elegant and prefer to use them.  They just make more
>logical sense to me.

And hence make you a more efficient programmer...

You seem to imply that recursive programs are a tradeoff of elegance
for (time) efficiency.  I would suggest instead they are a tradeoff
of programmer time and effort, maintenance and correctness for a 
small constant factor of time which is probably not needed anyway.

Mike