Fibonacci Sequence in Java taking too long?

Question

I'm trying to find the sum of the Fibonacci sequence in Java, but the run time is taking way too long (or is it suppose to?). This slows down anytime I use an integer past 40.

Note: At 50, a negative value is returned which boggles my mind.

Any advice?

public static void main(String[] args) {        
    //Find Fibonacci sequence
    int sum=getSum(50);
    System.out.println("Sum of Fibonacci Numbers is " + sum); 
}
static int getSum(int n){
    if (n==0) return 0;
    if (n==1 || n==2) return 1;
    else return getSum(n-1) + getSum(n-2);
}

Answer 1

For n > 2, an invocation of your getSum(n) recursively invokes itself twice. Each of those invocations may recurse further. The total number of method invocations scales as 2^n, and 2^50 is a very large number. This poor scaling reflects the fact that the simple-minded recursive approach ends up needlessly recomputing the same results (e.g. fib(4)) a great many times, and it is why your program slows down so rapidly as you increase n.

The negative return value you get after a certain point arises from exceeding the limits of data type int. You could get a larger limit with a wider data type, presumably long. If that's not enough then you would need to go to something like BigInteger, at a substantial performance penalty.

Answer 2

You need to use long instead of int if you want to calculate the 50th Fibonacci number. The 50th Fibonacci number is 12586269025 and exceeds the maximum value of int (see http://www.maths.surrey.ac.uk/hosted-sites/R.Knott/Fibonacci/fibtable.html).

A non-recursive algorithm is likely going to be faster, see http://planet.jboss.org/post/fibonacci_sequence_with_and_without_recursion for the different implementations.