Thread: Recursive Fibonacci sequence optimization

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");
	}	
}