Fibonacci Recursion not working for Java

Question

Please forgive my ignorance, I'm still a noob. Whenever I input a moderately big number it does not give me any output because it is stuck in the fibCalculate method. An example of a number that does not give any output would be 40.

package fib;

import java.math.BigInteger;
import java.util.Scanner;


public class FibonacciCalculator {
    private static BigInteger TWO = BigInteger.valueOf(2);

    public static BigInteger fibCalculate(BigInteger num) {
        if (num.equals(BigInteger.ONE) || num.equals(BigInteger.ZERO)) {
            return num;
        } else {
            return (fibCalculate(num.subtract(BigInteger.ONE)).add(fibCalculate(num.subtract(TWO))));
        }
    }

    public static void main(String[] args) {
        @SuppressWarnings("resource")
        Scanner input = new Scanner(System.in);
        long n = 10;

        System.out.println(
                "Please input a fibonacci placeholder to see what fibonacci number it holds,\nor input 0 to end program. (The count starts at 0):  ");
        n = input.nextLong();
        System.out.println("Answer: "+fibCalculate(BigInteger.valueOf(n)));

    }
}

Answer 1

Your code does produce output for n>40, it just takes a lot of time, since it's very slow.

For example, testing your code for all values of n between 0 and 50, using the following code:

long start = System.currentTimeMillis ();
for (int fib=0;fib<50;fib++) {
  System.out.println("Answer: "+ fib + ": "+fibCalculate(BigInteger.valueOf(fib)) + " after " + (System.currentTimeMillis ()-start)/1000 + " seconds from the beginning");
}

produces the following output (I didn't wait enough for it to end):

Answer: 0: 0 after 0 seconds from the beginning
Answer: 1: 1 after 0 seconds from the beginning
Answer: 2: 1 after 0 seconds from the beginning
Answer: 3: 2 after 0 seconds from the beginning
Answer: 4: 3 after 0 seconds from the beginning
Answer: 5: 5 after 0 seconds from the beginning
Answer: 6: 8 after 0 seconds from the beginning
Answer: 7: 13 after 0 seconds from the beginning
Answer: 8: 21 after 0 seconds from the beginning
Answer: 9: 34 after 0 seconds from the beginning
Answer: 10: 55 after 0 seconds from the beginning
Answer: 11: 89 after 0 seconds from the beginning
Answer: 12: 144 after 0 seconds from the beginning
Answer: 13: 233 after 0 seconds from the beginning
Answer: 14: 377 after 0 seconds from the beginning
Answer: 15: 610 after 0 seconds from the beginning
Answer: 16: 987 after 0 seconds from the beginning
Answer: 17: 1597 after 0 seconds from the beginning
Answer: 18: 2584 after 0 seconds from the beginning
Answer: 19: 4181 after 0 seconds from the beginning
Answer: 20: 6765 after 0 seconds from the beginning
Answer: 21: 10946 after 0 seconds from the beginning
Answer: 22: 17711 after 0 seconds from the beginning
Answer: 23: 28657 after 0 seconds from the beginning
Answer: 24: 46368 after 0 seconds from the beginning
Answer: 25: 75025 after 0 seconds from the beginning
Answer: 26: 121393 after 0 seconds from the beginning
Answer: 27: 196418 after 0 seconds from the beginning
Answer: 28: 317811 after 0 seconds from the beginning
Answer: 29: 514229 after 0 seconds from the beginning
Answer: 30: 832040 after 0 seconds from the beginning
Answer: 31: 1346269 after 0 seconds from the beginning
Answer: 32: 2178309 after 0 seconds from the beginning
Answer: 33: 3524578 after 1 seconds from the beginning
Answer: 34: 5702887 after 1 seconds from the beginning
Answer: 35: 9227465 after 2 seconds from the beginning
Answer: 36: 14930352 after 4 seconds from the beginning
Answer: 37: 24157817 after 6 seconds from the beginning
Answer: 38: 39088169 after 10 seconds from the beginning
Answer: 39: 63245986 after 17 seconds from the beginning
Answer: 40: 102334155 after 28 seconds from the beginning
Answer: 41: 165580141 after 45 seconds from the beginning
Answer: 42: 267914296 after 74 seconds from the beginning
Answer: 43: 433494437 after 120 seconds from the beginning

You can see that the running time grows exponentially.

Answer 2

The computation as you implemented it will looks as following:

                          fibCalculate(40)
                         /                \
                fibCalculate(39)       fibCalculate(38)   
               /            \           /             \
fibCalculate(38)  fibCalculate(37)  fibCalculate(37)   fibCalculate(36)
     /     \           /     \         /     \            /     \
 ....     ....      ....   ....      ....   ....       ....    ....

and so forth until it will reach either fibCalculate(0) or fibCalculate(1), leading to 2^40 (O(2^n) running time complexity) computations overall, most of which are repetitions of the same computed value, hence almost immidiate optimization will be to cache intermediate values to avoid computing them for the second time, this will reduce the running time complexity down to O(n).

package fib;

import java.math.BigInteger;
import java.util.Scanner;


public class FibonacciCalculator {
   private static Map<BigInteger, BigInteger> cache = new HashMap<>() {{
       put(BigInteger.ONE);
       put(BigInteger.valueOf(2));
   }}

public static BigInteger fibCalculate(BigInteger num) {
       BigInteger result = cache.get(num);
       if (result != null) {
           return result
       }
       result = (fibCalculate(num.subtract(BigInteger.ONE)).add(fibCalculate(num.subtract(TWO))));
       return result;
    }
}

public static void main(String[] args) {
    @SuppressWarnings("resource")
    Scanner input = new Scanner(System.in);
    long n = 10;

    System.out.println(
            "Please input a fibonacci placeholder to see what fibonacci number it holds,\nor input 0 to end program. (The count starts at 0):  ");
    n = input.nextLong();
    System.out.println("Answer: "+fibCalculate(BigInteger.valueOf(n)));

   }
}