Stack Overflow error occurs when using recursive fibonacci function

Question

Here's my code and it runs well with values of 400 to 4000 but once it's about 4mil, I get stack overflow errors.

Thanks in advance!

public class Fib {
static int c=1,b=2;
static long sum1=0,sum2=0;

static long fib(long a){
if(a==1){
    return 1;
}
if(a==2){
    return 2;
}
else{
    return fib(a-1)+fib(a-2);
}

    }


    public static void main(String[] args){
sum2= fib(4000000);
    System.out.println("Sum %f" +sum2);
}
    }

Answer 1

Yes - you're running out of stack space. It's far from infinite, and you're using it up on each recursive call. You're trying to end up with a stack with 4 million stack frames - that's not going to work.

I suggest you consider an iterative approach. Even if you had an infinite amount of stack, that code would probably not complete before the heat death of the universe. (Think about the complexity of this code...)

Answer 2

You can increase the stack size of Java programs. Example:

java -Xss4m YourProgram

Reference

Nevertheless I would also recommend an iterative method.