"Michael S. Davis" wrote:
> On Thu, 22 Jun 2000, Charles Rezsonya wrote:
>
> > i keep hearing recursion should be avoided whiled devin' up an app. what
> > exactly does this mean? don't call too many loops or repeated functions?
> > any extra details or specs on what and what not to do would be appriciated.
> > brief is ok =)
>
> This has always puzzeled me also. Recursion means a routine that calls
> itself. Computing a factorial is a classic example.
>
> But what confuses me is that a routine that recurses 3 times generally
> takes up no more stack than a routine that calls another routine, which
> calls a third routine.
The overall problem with recursion in my experience isn't the utility of it, but its
often poor implementation. With heavy nesting of
functions, you know that a function will be called only once and the stack use is
called in a consistent manner. With recursion,
suddenly the stack use becomes data driven instead of code driven and unknowns are
introduced.
>
> It seems that the operative warning hers should be "don't nest
> routines" too deep rather than "don't use recursion". Each time you
> call a new function, you place a lot of data on the stack AND the stack
> space is limited.
>
> In fact, it is quite possible that a routine that recurses 4 times may
> use less stack that 3 separate routines that are nested.
>
> Anyone care to explain why there is a warning against "recursion" rather
> than a warning against "nesting" of functions.
It is almost a prejudice against academic coding styles and the AI community in
general. I did recursion on an piece of software to
operate image processing for equipment that was focusing automatically upon an image a
few years ago. It was a very nice, iterative
application and it worked fine. Each time the function was called, the image became
progressively more in focus 'til it terminated
when the desired resolution was attained.
However, when code review came up, the "senior" software guys screamed bloody murder
when they saw how I did it. Even though I was
monitoring stack size in the loop, I was forced to rewrite the control function in a
traditional iterative for-loop because "we don't
do that". Before I knew it, they were dramatizing about stories of system crashes in
mission critical projects in the early 80's when
all of this stuff was just starting. They were not willing to listen to how it could
be done right. Since I was the new guy, they
won over management.
My attitude toward recursion is that if you do it, watch the use of stack space every
call and find a graceful way to exit just before
you blow stack. Also, if it can be done in a regular iterative loop, do it since the
memory to hold the loop progression is usually
just a single integer and no memory is used every iteration.
Steve
--
For information on using the Palm Developer Forums, or to unsubscribe, please see
http://www.palmos.com/dev/tech/support/forums/
