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.

Курс 'Java для начинающих' на Udemy