**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 **F _{i} = F_{i-1} + F_{i-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 i^{th} step, you need to compute **F _{i-1} + F_{i-2} . **So each iteration we will have 2 recursive call one for

**F**and other one for

_{i-1}**F**. The ending of recursion is when your value of n is less or equal to 2.

_{i-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) .

Multithreaded code is as below:

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:

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.