Java – multithreading and recursion together

I have recursive code that deals with tree structures in a depth first manner The code is basically as follows:

function(TreeNode curr) 
{
    if (curr.children != null && !curr.children.isEmpty()) 
    {
        for (TreeNode n : curr.children) 
    {
            //do some stuff
            function(n);
        }
    } 
    else 
    {
        //do some other processing
    }
}

I want to use threads to speed up completion Most of the time is spent on traversal, so I don't want to create only one thread to handle "other processing" because it doesn't take that long I think I want to fork threads when "doing something", but how does it work?

Solution

This is a good example of fork / join framework, which will be included in Java 7 As a separate library for use with Java 6, you can download it here

Something like this:

public class TreeTask extends RecursiveAction {
    private final TreeNode node;
    private final int level;

    public TreeTask(TreeNode node,int level) {
        this.node = node;
        this.level = leve;
    }

    public void compute() {
        // It makes sense to switch to single-threaded execution after some threshold
        if (level > THRESHOLD) function(node);

        if (node.children != null && !node.children.isEmpty()) {
            List<TreeTask> subtasks = new ArrayList<TreeTask>(node.children.size());
            for (TreeNode n : node.children) {
                // do some stuff
                subtasks.add(new TreeTask(n,level + 1));
            }
            invokeAll(subtasks); // Invoke and wait for completion
        } else {
            //do some other processing
        }
    }
}

...
ForkJoinPool p = new ForkJoinPool(N_THREADS);
p.invoke(root,0);

The key point of fork / join framework is work stealing - executing other tasks while waiting for the subtask thread to complete As a naive application of executorservice, it allows you to write algorithms directly while avoiding thread exhaustion