Recursive Fibonacci using BigInteger in Java

Question

I'm trying to solve a project euler 25 problem in java and since I need something to store numbers with 10000 digits, I'm using BigInteger classes.

So I'm working in some recursive fibonacci sequence using BigIntegers and I'm trying to convert this code:

public int fibonacci(int n)  {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

from this link: Java recursive Fibonacci sequence

to the same code, but using BigIntegers.

So, this is what I have so far:

public static BigInteger fibonacci(BigInteger index) {
    if (index.compareTo(BigInteger.ZERO) == 0)
        return BigInteger.ZERO;
    else if (index.compareTo(BigInteger.valueOf(1)) == 1)
        return BigInteger.ONE;
    else
        return fibonacci(index.subtract(BigInteger.ONE)).add(fibonacci(index.subtract(BigInteger.valueOf(2))));
}

public static int numberOfDigits(BigInteger fibonacci) {
    return Integer.valueOf(fibonacci.toString().length());
}

public static void main(String[] args) {
    long startTime = System.nanoTime();
    for (BigInteger i = new BigInteger("1"); numberOfDigits(fibonacci(i)) <= 1000; i = i.add(BigInteger.ONE))
        System.out.println(" " + i + "  -  " + fibonacci(i) + "  -  " + numberOfDigits(fibonacci(i)));
    long endTime = System.nanoTime();
    long duration = (endTime - startTime);
    System.out.println("Duration: " + duration/1000000 + " ms");
}

When I run it, I get a StackOverFlowError, like this:

Exception in thread "main" java.lang.StackOverflowError
    at java.math.BigInteger.subtract(BigInteger.java:1423)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)
    at Problem25Part2.fibonacci(Problem25Part2.java:19)

And it repeats I think 1000 times. Well, I have no idea what is wrong, so please can you guys help me? Thank you!

Answer 1

When you use compare() it returns 1 if argument is higher than actual.

So you should change this piece of code:

else if (index.compareTo(BigInteger.valueOf(1)) == 1)

for this:

else if (index.compareTo(BigInteger.valueOf(1)) == 0)

Answer 2

I think You have standard problem with recursion... It's a problem with method fibonacci, because You have no places, when this method must return final result, so please check your condition and more about compare in BigInteger. Recommends also read about tail recursion

Answer 3

Java doesn't deal too well with deep recursion. You should convert to using a loop instead.

Also see this thread on tail recursion: https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all

Answer 4

You could try to use dynamic programming to reduce space complexity. Something like this should work:

public static BigInteger fibonacci(BigInteger n) {
    if (n.compareTo(BigInteger.valueOf(3L)) < 0) {
        return BigInteger.ONE;
    }
    //Map to store the previous results
    Map<BigInteger, BigInteger> computedValues = new HashMap<BigInteger, BigInteger>();
    //The two edge cases
    computedValues.put(BigInteger.ONE, BigInteger.ONE);
    computedValues.put(BigInteger.valueOf(2L), BigInteger.ONE);
    return fibonacci(n, computedValues);
}

private static BigInteger fibonacci(BigInteger n, Map<BigInteger, BigInteger> computedValues) {
    if (computedValues.containsKey(n))
        return computedValues.get(n);
    BigInteger n1 = n.subtract(BigInteger.ONE);
    BigInteger n2 = n.subtract(BigInteger.ONE).subtract(BigInteger.ONE);
    computedValues.put(n1, fibonacci(n1, computedValues));
    computedValues.put(n2, fibonacci(n2, computedValues));
    BigInteger newValue = computedValues.get(n1).add(computedValues.get(n2));
    computedValues.put(n, newValue);
    return newValue;
}