Stack Overflow when computing n = ~11000 + fibonacci recursive method with memoization

Question

I have a program to compute the nth Fibonacci number with a recursive method and while using memoization.

I get up to around n = 11000 and I am getting a stackoverflow exception. Can someone help me fix this?

Here is my code:

public class BigInt {

static BigInteger[] fval;

public static void main(String[] args) {
    int index;
    Scanner input = new Scanner(System.in);
    index = input.nextInt();
    fval = new BigInteger[index + 1];

    System.out.println(fib_rec(index));
}

public static BigInteger fib_rec(int index) {
    BigInteger result = BigInteger.ONE;
    if (index <= 2) {
        return result;
    } else {
        if (fval[index] != null) {
            result = fval[index];
        } else {
            result = fib_rec(index - 1).add(fib_rec(index - 2));
            fval[index] = result;
        }
        return result;
    }
}

Answer 1

The reason you are getting a stackoverflow is because you are running out of memory. Increase the memory available and more specifically the stack size. Just add -Xss1024mb or whatever size you prefer.

The best way to handle this kind of situation is to actually have a better algorithm so that you dont need to consume alot of memory.