Generate Fibonacci number in Java

problem

Given a number n, you wish to generate the nth Fibonacci element. The formula is as follows:

SOLUTION

One solution is by using recursion. Fibonacci sequence is recursive by its natural definition so it will suit best. For example:

				
					public class Fibonacci {

    public long calculate(int n) {
        if (n==0) {
            return 0;
        }else if(n==1) {
            return 1;
        }else
            return calculate(n-1) + calculate(n-2);
        }
}

running

To quickly execute, let’s put it in the main method:

				
					public class Main {
    public static void main(String[] args) {
        long fibo10 = new Fibonacci().calculate(10);
        System.out.println(fibo10);
    }
}

output

Correct, the 10th element is 55. You can see the first 20 elements in the Fibonacci sequence are as follow:

F₀	F₁	F₂	F₃	F₄	F₅	F₆	F₇	F₈	F₉	F₁₀	F₁₁	F₁₂	F₁₃	F₁₄	F₁₅	F₁₆	F₁₇	F₁₈	F₁₉	F₂₀
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181	6765

conclusion

This is a simple solution using Long as the return type and binary recursion (it’s calling twice the calculate() method). The downsides of this approach is that is limited to the return number and also quite slow. Can you try to execute this with n=40? It can be improved by using BigInteger as the return type and also dynamic programming to speed up the binary recursion.

Share it!

Tagged Fibonacci

0 0 votes

Article Rating