Applying Thread Pools - Java Concurrency in Practice - page 212

Loop parallelization can also be applied to some recursive designs; there are often sequential
loops within the recursive algorithm that can be parallelized in the same manner as Listing
8.10 . The easier case is when each iteration does not require the results of the recursive itera-
tions it invokes. For example, sequentialRecursive in Listing 8.11 does a depth-first
traversal of a tree, performing a calculation on each node and placing the result in a collec-
tion. The transformed version, parallelRecursive , also does a depth-first traversal, but
instead of computing the result as each node is visited, it submits a task to compute the node
result.
Listing 8.11. Transforming Sequential Tail-recursion into Parallelized Recursion.
When parallelRecursive returns, each node in the tree has been visited (the traversal
is still sequential: only the calls to compute are executed in parallel) and the computation
for each node has been queued to the Executor . Callers of parallelRecursive can