# Calculate Fibonacci number in java using Recursion and Multi Threading

Calculate Fibonacci number in java using recursion and also using multi-threading 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 is follows:

```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:

```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) .

```public class FibMultiThreading extends Thread {
private int x;

this.x = x;
}

public void run() {
if (x == 0){
}else if( x == 1 || x == 2 ) {
}else {
try {
/*
* Below we are invoking 2 threads to compute separate values
* This will for a tree structure
*/
f1.start();
f2.start();
f1.join();
f2.join();
}catch(InterruptedException ex) {
ex.printStackTrace();
}
}
}

public static void main(String[] args){
try {
int inputNum = 8;
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:

```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