Improving Fibonacci recursion with BigIntegers I've been tasked with making a fast Fibonacci recursive method that uses BigInteger to calculate REALLY big numbers. However, to calculate numbers past 30 it takes almost a MINIMUM of 60 seconds each time. Unfortunately, I have to use some type of recursion in my method even though the iteration way is WAY faster. 

public static BigInteger theBigFib(int b) {
        BigInteger[] a = new BigInteger[100000];
        if(b &lt; 2) {
            return BigInteger.ONE;
        }

        if(a[b] != null) {
            return a[b];
        }

        a[b] = theBigFib(b - 1).add(theBigFib(b - 2));
        return a[b];
    }


I have a loop in my main that runs the the method from values 20 to 30. 

public static void main(String[] args) {
        final long start = System.nanoTime();
        for (int i = 20; i &lt;= 30; i++) {
            System.out.println(theBigFib(i));
        }
    //  System.out.println(theBigFib(35));  Takes way too long
        final long end = System.nanoTime();
        System.out.println("This program took " + ((end - start) / 1000000000) + " second(s) to run.");
    }


Here are the results from the console. This is from the 2nd time running it which the first time came out to be 443 seconds.

10946
17711
28657
46368
75025
121393
196418
317811
514229
832040
1346269
This program took 227 second(s) to run.


I find this topic of recursion and program efficiency to be super interesting so I'm open to all suggestions. Only thing I cannot use is external libraries. :)
Every time you call theBigFib, you allocate a new BigInteger[] a object.  As a result, you're not caching any previous results.