Fibonacci

Although this is an extremely basic problem, I've come accross a solution that is pretty efficent.

First of all this is what a standard recursive fibonacci method would look like:

private static BigInteger fibonacci(int n)
    {
        if(n <= 1) return BigInteger.valueOf(n);

        BigInteger nthNumber = (fibonacci(n - 1).add(fibonacci(n - 2)));
        return nthNumber;
    }

For the most part this method works fine but once you start giving the parameter larger values it takes exponentially long to compute.

Primary reason for this is that for every number we have in the series, the values of the previous fibonacci numbers are also calculated.

To get around this we can implement caching of already computed values to avoid recalculating them.

And here is the solution that implements caching to finding fibonacci numbers.

private static BigInteger[] fibonacciNumbers;
    public static void main(String[] args)
    {
        int n = 500;
        fibonacciNumbers = new BigInteger[n + 1];
        System.out.println(fibonacci(n));
    }

    private static BigInteger fibonacci(int n)
    {
        if(n <= 1) return BigInteger.valueOf(n);

        if(fibonacciNumbers[n] != null)
            return fibonacciNumbers[n];

        BigInteger nthNumber = (fibonacci(n - 1).add(fibonacci(n - 2)));
        fibonacciNumbers[n] = nthNumber;
        return nthNumber;
    }

So to describe what's happening here line by line;

private static BigInteger[] fibonacciNumbers;

I've used BigInteger here as it virtually has no numerical limit. The array itself is declared before calling the fibonnaci numbers method first time.

fibonacciNumbers = new BigInteger[n + 1];

Since fibonnaci numbers are 'indexed' from 1 we make the array 1 element larger than the number we are trying to reach.

if(fibonacciNumbers[n] != null)
        return fibonacciNumbers[n];

This if tells us if the array's nth element exists, it should return that number and stop the method here.

BigInteger nthNumber = (fibonacci(n - 1).add(fibonacci(n - 2)));
    fibonacciNumbers[n] = nthNumber;

And this is the part where we actually calculate it just as we did in the conventional recursive implementation. After calculating the number we just plug it in the array, which allows us to use that number in other recursive branches.

And that's it. Just by using a simple caching calculated values into the memory we avoid an exponentially increasing CPU load.