Very slow recursive Fibonacci method, what is the cause?

Question

I made a program with recursiveness, but when the user type 50, the processing to generate the Fibonacci sequence is now over extremely slow.

Is it due to data input/output processing on the console? There is a mode that is faster in Java than Scanner, BuffererReader or OutputStream?

CODE: subclass:

package Fib;

public class Fibonacci {
    public int calculaFibonacci(int n) {  
           if (n == 0)  
              return 0;  
           if (n == 1)  
              return 1;  
           return calculaFibonacci(n-1) + calculaFibonacci(n-2);  
    }
}

Classeprincipal:

package TesteFibo;

import java.util.Scanner;

import Fib.Fibonacci;

public class chamaFibo {
    public static void main(String[] args){ 

        Scanner sc = new Scanner(System.in);
        System.out.println("Enter one number integer:");
        int tes = sc.nextInt();
        System.out.println();


        Fibonacci fibo = new Fibonacci();
        int i = fibo.calculaFibonacci(tes);
        //System.out.println(i);
        System.out.println("Fibonacci number: ");
        System.out.println(i);


        sc.close();
        }
    }

Answer 1

As explained in this answer, the problem is the recursion itself, and not the input and output of the data (up because you only use the Scanner and the println few times and outside the recursive function, so they are not the cause of the slowness). Even, follows a translation/ adaptation of the explanation that has there:

If F for its recursive function, call F(10) does the following:

 F(10) = F(9)                           +   F(8)
 F(10) = F(8)          +   F(7)         +   F(7)          +  F(6)
 F(10) = F(7) + F(6)   +   F(6) + F(5)  +   F(6) + F(5)   +  F(5) + F(4)
 ....

Notice that F(8) is calculated twice, F(7) 3 times, and so on. The higher the initial number, the more recursive calls - and in this case, redundant - will be made, and this grows exponentially according to the initial value.

Not to mention that all these calls are "hung up", waiting for recursive calls to return below them, until they arrive at F(1) and F(0) (which is when the function stops making new recursive calls and returns a value). Depending on the initial value and the configuration of your JVM, this may burst the stack, generating a StackOverflowError.

---

I’ve modified its functions to give us an idea of what’s going on.

I created a counter to see how many calls are made to the function, and I changed the types of int for long, since the results were bursting the maximum value that a int supports (which is about 2 billion):

public class Fib {

    static long CONTADOR;

    public static long calculaFibonacci(long n) {
        CONTADOR++;
        if (n == 0)
            return 0;
        if (n == 1)
            return 1;
        return calculaFibonacci(n - 1) + calculaFibonacci(n - 2);
    }

    public static void main(String[] args) {
        CONTADOR = 0;
        calculaFibonacci(50);
        System.out.println(CONTADOR);
    }
}

The result was:

40730022147

That is, more than 40 billions recursive calls. No wonder it got slow.

If we calculate for 25, the result is:

242785

That is, doubling the initial number (from 25 to 50), the number of recursive calls increases from 242 thousand to another 40 billion (in fact an exponential increase, as already explained).

---

Why not do no recursion? Regardless of the starting number, it’s just a function call with a loop simple. This is the solution I would use (unless you are studying recursion, of course).

public long fib(long n) {
    long a = 0;
    long b = 1;
    long c = 1;
    for (long i = 0; i < n; i++) {
        a = b;
        b = c;
        c = a + b;
    }
    return a;
}

The complexity of this algorithm grows linearly - and no longer exponentially - according to the initial value, not counting that iterative methods are much less costly compared to recursive methods.

---

Remarks

• If you want, it is also possible to use recursion, but keeping the results already computed (thus preventing them to be recalculated), using techniques of memoization - which already greatly decreases the number of calls.
• That doesn’t mean that println will never cause performance issues. In fact, if you use it within the recursive function (to print the intermediate values, for example), this will slow her down too. But in this particular case, as I/O is done only outside the function, it is not the cause of slowness.