Re: Recursion Usage and Concepts - Newbie Question
Patricia Shanahan wrote:
Can anyone suggest a simple problem that is both best solved by
recursion?
Martin Gregorie wrote:
Mark Space wrote:
I actually might have to disagree with you here. CPUs have a physical
limit regarding stack use. Several use local stacks (internal cache) to
implement call and return stacks. Go beyond that limit and you incur a
significant performance penalty.
AMD explicitly recommends implementing tree walks with a loop and a
local stack data structure, not using recursion.
Brian Goetz's superb /Java Concurrency in Practice/ has an example of a
recursive, sequential tree-walk algorithm (Listing 8.15), which is stack
bound, transformed to a thread-based concurrent algorithm (Listing 8.16). The
concurrent version is also recursive, but puts its intermediate state on the
heap, not the stack, so goes much, much deeper. This is an interesting case
of a parallel algorithm providing benefits even on a single-processor system.
It shows that part of the problem is not with recursion, but with use of the
stack to support recursion.
Of course, heap is finite, too. Recursion must maintain state proportionate
to problem size, versus a loop's summary state like a running total, with no
intermediate state to unwind. The state required by recursive algorithms
supports a certain economy of algorithmic expression, but often is too high a
price to pay.
I think the afore mentioned directory tree walk should probably be
implemented the same way. Hmmm, although maybe the IO involved would
make stack performance a moot issue.
CPUs use cache for heap memory, too. Locality of reference is something to
think about, but for a cross-platform (and evolving-platform) world like
Java's, I suggest we not get too hung up on the specifics of how a CPU
implements program stack vs. program heap. The real issue is the depth of
that memory. Java's execution model has logically separate stack and heap,
and heap is (nearly?) always much larger. (I'm explicitly disclaiming JME here.)
The parallel algorithm suggested in /Concurrency/ not only shifts state to the
heap from the stack, thus buying larger capacity, it is inherently scalable to
more processor threads.
I assess that the recursive expression of Goetz's example directly lends
itself to parallelization. A loop idiom might have been more difficult to
render as multithreaded.
--
Lew