Re: Recursion Usage and Concepts - Newbie Question
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
Thanks, I added this to my Amazon wish list. I've been meaning to for a
while and you just reminded me.
I have a couple of algorithms I fall back on when I need faster tree
walks. One is Michael Abrash's algorithm from The Zen of Graphics
Programming. It uses a fixed length array of pointer allocated locally
(on the stack). Good if your tree can publish it's max depth in
advance. A simple alteration of Abrash can use a regular Java stack
structure to provide tree traversal up to the depth allowed my heap memory.
(Actually, I have no idea how the speed of these two compare. Hmmm,
goona need to test this.)
The other is J. M. Morris's simple tree walk. (Information Processing
Letters, Dec. 1979.) It uses no extra memory at all, but does transform
the tree as it walks. Good for limited memory devices where multiple
threads aren't an issue, but I've never had a chance to try it out in
You make good points. I hadn't thought about using multiple threads to
speed up a tree walk. It's something I should investigate.