Java ExecutorService to solve Recursive Fibonacci Series?

This recursion will overflow the stack very fast. This is because you are computing lower fibonacci numbers over and over again - exponentially many number of times.

This recursion will overflow the stack very fast. This is because you are computing lower fibonacci numbers over and over again - exponentially many number of times. One effective way to avoid that is to use memoized recursion (a dynamic programming approach) Basically use a static array to hold the already computed fibonacci numbers and whenever you need one, take it from the array, if it's already computed.

If not, then compute it and store it in the array. This way each number will be computed only once. (You can use other data structure instead of array, of course, i.e.

Hashtable).

Got it to work! Thanks! :) – Shankar Jul 2 at 5:03 But still the recursive multithreaded procedure takes much longer than the memoized recursive non-multithreaded one.. any tip to improve performance?

– Shankar Jul 2 at 5:04 Well, that's the point - plain recursion would never finish (even multithreaed), because the number of iterations grow exponentially – Petar Ivanov Jul 2 at 5:10 If you want even faster, you can do the memoized recursion multi threaded (just need to synchronize the arrray). – Petar Ivanov Jul 2 at 5:10 Yes, will try that. Thanks – Shankar Jul 2 at 5:40.

What you are doing is replacing simple recursion with recursion via threads / tasks. Until you get to the fib(0) and fib(1) cases, each task submits two more tasks, and then waits for them to complete. While it is waiting, it is still using a thread.

Since the thread pool is bounded, you soon get to the point where calls to submit block ... and the whole computation locks up. In addition to that, you've got a bug in indexMinusTwo which would result in the computation giving the wrong answer. But still the recursive multithreaded procedure takes much longer than the memoized recursive non-multithreaded one.. any tip to improve performance?

Even assuming that you "fixed" the above problem (e.g. By using an unbounded thread pool) there is no way that you will be able to do a multi-threaded version of fibonacci that performs better than a single-threaded version that uses memoization. The computation is simply not suited to parallelization.

Thank you for the clarification. However, please let me know where exactly is the bug in that code – Shankar Jul 2 at 5:39 You've fixed it. – Stephen C Jul 2 at 5:59.

Threads work best when you have independant tasks to perform. The fibonacci series by definition does not have any degrees of parallelism. Each f(n) depends on the previous two values.As such it is not possible to calculate f(n) faster using multiple threads than using one (unless you have an inefficient algo) The only thing you could make parallel potentially the + operation for large numbers, however this is likely to be a) complex b) difficult to make faster than the single threaded solution.

The fastest/simplest way to calculate fibonacci numbers is to use a loop in one thread. You don't need to use recusrion or memorize values.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.