I've written an algorithm for finding terms in a Fibonacci Sequence using a recursive method. It's fairly quick until around the 45th term which takes roughly 5 seconds to calculate using a primitive type; it goes until the 42nd term using the BigInteger class in about 10 seconds. I need to find the first term that contains 1000 digits. Which also means I have to use the BigInteger class which slows it down. Is there anyway I can speed up my algorithm short of hard-coding all the terms in the sequence up to a specific point?

public static BigInteger fibSeq(int x) { if( x <= 2) { return BigInteger.ONE; } else { return fibSeq(x-1).add(fibSeq(x-2)); } } public static long fibSeqL(long x) { if( x <= 2) { return 1; } else { return fibSeqL(x-1)+(fibSeqL(x-2)); } } public static void main(String[] args) { long start = System.currentTimeMillis(); System.out.println(fibSeq(42)); long end = System.currentTimeMillis(); System.out.println("Elapsed time: " + (end - start) + "ms"); } }