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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
public class FibRecursion { public static void main(String args[]){ int inputNum = 8; System.out.println("Fibonacci number at "+inputNum+" position is:"+computeFib(inputNum)); } public static int computeFib(int n){ if(n==0) return 0; if( n==1 || n ==2) return 1; /* * recursion call with previous number */ return computeFib(n-1)+computeFib(n-2); } } |
Output of above code:
|
1 2 3 4 5 |
Fibonacci number at 8 position is:21 Fibonacci number at 0 position is:0 Fibonacci number at 10 position is:55 |
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
public class FibMultiThreading extends Thread { private int x; public int answer; public FibMultiThreading(int x) { this.x = x; } public void run() { if (x == 0){ answer = 0; }else if( x == 1 || x == 2 ) { answer = 1; }else { try { /* * Below we are invoking 2 threads to compute separate values * This will for a tree structure */ FibMultiThreading f1 = new FibMultiThreading(x-1); FibMultiThreading f2 = new FibMultiThreading(x-2); f1.start(); f2.start(); f1.join(); f2.join(); answer = f1.answer + f2.answer; }catch(InterruptedException ex) { ex.printStackTrace(); } } } public static void main(String[] args){ try { int inputNum = 8; FibMultiThreading f = new FibMultiThreading(inputNum); f.start(); f.join(); System.out.println("Fibonacci number at "+inputNum+" position is:"+f.answer); } catch(Exception e) { e.printStackTrace(); } } } |
The output for the above is:
|
1 2 3 4 5 |
Fibonacci number at 8 position is:21 Fibonacci number at 0 position is:0 Fibonacci number at 10 position is:55 |
You can have above code from GIT.
https://github.com/Niravkumar-Patel/SnippetExampleRepo.git
PS: please ignore grammatical/spelling mistakes.