Fibonacci numbers in Java – Algorithms for interview

Fibonacci numbers – elements of the numerical sequence 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, …, in which the first two numbers are either 1 and 1, or 0 and 1, and each subsequent number are equal to the sum of the two previous numbers:

F0=0, 
F1=1, 
Fn=Fn-1 + Fn-2

The following example implements two options for calculating Fibonacci numbers: using recursion (the recursive method) and a for loop (the calculateWithFor method):

public class Fibonacci {
        public static void main(String[] args) {
            int n = 25;
            LocalTime localTime1 = LocalTime.now();
            System.out.print("Recursion " + recursive(n));
            LocalTime localTime2 = LocalTime.now();
            Duration duration1 = Duration.between(localTime1, localTime2);
            System.out.println(", execution time - " + duration1);

            LocalTime localTime3 = LocalTime.now();
            System.out.print("Loop for " + calculateWithFor(n));
            LocalTime localTime4 = LocalTime.now();
            Duration duration2 = Duration.between(localTime3, localTime4);
            System.out.println(", execution time - " + duration2);
        }

        /**
         * Difficulty О(n)
         *
         * @param n
         * @return
         */
        private static long calculateWithFor(int n) {
            long first = 0;
            long second = 1;
            long result = n;
            for (int i = 1; i < n; i++) {
                result = first + second;
                first = second;
                second = result;
            }
            return result;
        }

        /**
         * Difficulty О(2^n)
         *
         * @param n
         * @return
         */
        private static long recursive(int n) {
            if (n <= 1) {
                return n;
            }
            return recursive(n - 2) + recursive(n - 1);
        }
    }

If you run this program and look at the execution time of both algorithms, you can see that the recursive version takes longer.
Try changing the value of the variable n to 250 and the program will hang. The problem is that the calculation speed of the recursive algorithm is extremely low.