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:

PackageStructure

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.

GitHub-Mark-32px https://github.com/Niravkumar-Patel/SnippetExampleRepo.git

 

PS: please ignore grammatical/spelling mistakes.

Leave a Reply

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