Should I use threading and recursion together?

Threads are great if some part of the processing is waiting on something external (user input, I/O, some other processing) - the thread that's waiting can continue to wait, while a thread that isn't waiting forges on ahead.

However, for processing-intensive tasks, more threads than processors actually creates overhead. It seems like your threads are doing all "CPU work", so I'd stick to one thread per core - test to find the optimal number, though.

The biggest overhead created is from context switching (freezing one thread and loading the execution context of the next one), as well as cache misses when threads are doing tasks with different memory (if your thread can use the CPU cache effectively).

your best bet would be to create a threadpool, and then use it 'transparently' to add nodes.

eg, create 2 threads at program start, have them wait on a semaphore or event. When you have nodes to add, you pop the data onto a queue then trigger the semaphore. This wakes one of the threads which pops the data off the queue and performs the processing. (make sure access to the queue is threadsafe - fully synchronised with a critical section is best).

The overall performance of your app is slower as you have more overhead, in copying data to the queue and running the extra threads, but if you used to run on a single core you will now be running on 2. It works best if the threaded processing is expensive.

Sure, for example, Quicksort can be programmed multithreaded quite easily and get some large performance gains on multi-core systems, and some small performance losses on non-multithreaded. Just remember that you're adding overhead twice now - once for the stack save on the recursion and once on the thread, so if you're doing a large number of recursions then it could overwhelm a system faster than a non-multithreaded approach.