Fibonacci Numbers

Fibonacci numbers are 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, … where the first two numbers are either 0 and 1, or 1 and 1, and each subsequent number is the sum of the previous two:

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

The following Java example shows two ways to compute Fibonacci numbers: using recursion and using a for loop:

import java.time.Duration;
import java.time.LocalTime;

public class FibonacciExample {
    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("For loop: " + calculateWithFor(n));
        LocalTime localTime4 = LocalTime.now();
        Duration duration2 = Duration.between(localTime3, localTime4);
        System.out.println(", execution time: " + duration2);
    }

    /**
     * Time complexity: O(n)
     */
    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;
    }

    /**
     * Time complexity: O(2^n)
     */
    private static long recursive(int n) {
        if (n <= 1) {
            return n;
        }
        return recursive(n - 2) + recursive(n - 1);
    }
}

When you run the program and compare the execution time of both algorithms, you'll see that the recursive version is significantly slower. For example, setting n = 250 will cause the program to freeze due to the exponential complexity of the recursive approach.

Conclusion: Recursion is elegant but inefficient for large n. The iterative approach using a loop is much faster and more memory-efficient. For high-performance applications, consider using memoization or dynamic programming techniques.

This example helps Java learners understand the difference in performance and complexity between recursion and iteration when calculating Fibonacci numbers.