Re: Recursion and efficiency

From: Major <major_at_dcd.wa.gov.au>
Date: Tue, 7 Feb 1995 15:23:40 +0800

Hilmar Lapp <hili_at_al-bundy.biologie.uni-freiburg.de> writes:

> Well, my point of interest is the efficiency of recursive definitions
> compared to that of a iterative definition, that yields the same result.
> I consider efficiency both in terms of memory usage and time usage (of
> the STk-interpreter, of course).

Idealy the language implimentation would convert between forms giving
the user the best of both worlds: programming simplicity of recursive
definition and the efficiency of iterative definition. STk goes this
some of the time, Erik may be able to provide more detail.

> Or in other words: while programming in SCHEME/STk, should I try to avoid
> recursive definitions whenever it's possible without making the code a
> lot more complicated ? Or, is it just better the opposite way ? Is there
> any rule of thumb ? Are there some certain things, that, if used, make
> recursion slow and inefficient ?

Remember the general rule of programming: 5% of the code gets 95% of
the cycles. Steps of optimization:
1. Write your whole program using the simplest forms
2. Get your program working correctly (its amazing how many people
   spend a whole lot of programmer time makeing programs which produce
   the wrong answer faster and faster)
3. See if your program is running fast enough for your purposes. If it
   is you can go on to other, more interesting, things rather than
   wasting time on optimization. Again it is amazing how many people
   spend their lives making a program which takes 5 seconds to run 10%
   faster.
4. If you really need to optimize, figure out which is the critical
   5%. If you have tools to do thus USE THEM. You intuitions as to
   which code is most critical to performance will often be wrong.
5. Make the 5% go faster. Convert to iterative, convert to C, convert
   to assembler, etc.

Major
Received on Tue Feb 07 1995 - 08:27:16 CET