The question has two answers, actually.
Can recursion be done in parallel? Would that make sense?
Yes, of course. In most (all?) cases, a recursive algorithm can be rewritten in a way without recursion, leading to an algorithm that is quite often easily parallelizable. Not always, but often.
Think Quicksort, or iterating through a directory tree. In both cases a queue could be used to hold all the intermediate results resp. sub-directories found. The queue can be processed in parallel, eventually creating more entries until the task has been completed successfully.
What about the
Unfortunately, the Fibonacci function is a bad choice, because the input values complety depend on previously calculated results. This dependency makes it hard to do it in parallel if you start every time with
However, if you need to do Fibonacci calculations more often, it could be a good idea to store (or cache) pre-calculated results in order to avoid all calculations up to that point. The concept behind is quite similar to rainbow tables.
Lets say, you cache every 10th Fibo number pair up to 10.000. Start this initialization routine on a background thread. Now, if someone asks for Fibo number 5246, the algorithm simply picks up the pair from 5240 and start calculation from that point forward. If the 5240 pair is not yet there, just wait for it.
This way the calculation of many randomly choosen fibo numbers could be done very efficiently and in parallel, because it is very unlikely that two threads will have to calculate the same numbers - and even then, it would not be much of a problem.