Calculate Fibonacci number in java using Recursion and Multi Threading

Calculate Fibonacci number in Java using recursion and also using multithreading in O(log n) steps in java.

Input: Index value of Fibonacci series.

Output: Fibonacci value

To solve above problem, the very basic definition of Fibonacci is that Fi = Fi-1 + Fi-2.

Each F is our function. So let’s look at the basic solution.

1. Simple Recursion:

Here at each recursive call to method computeFib(int n), you simple needs to compute sum of two previous number. So for ith step, you need to compute Fi-1 + Fi-2 . So each iteration we will have 2 recursive call one for Fi-1 and other one for Fi-2 . The ending of recursion is when your value of n is less or equal to 2.

So below is the screen shot of my project structure and code to achieve the same:


Code as follows:

Output of above code:

2. Multithreaded Version of above which will compute it in O(log n).

Here, we will spawn a new thread for each recursion call, which will create a tree. So each step you will be spawning new thread which will continue to spawn another threads till it reached its leaf (i.e n <=2) .

Multithreaded code is as below:

The output for the above is:

You can have above code from GIT.


PS: please ignore grammatical/spelling mistakes.

Leave a Reply

Your email address will not be published. Required fields are marked *