Рефакторинг функции Фибоначчи

6. Рефакторинг функции Фибоначчи

Условие задачи:
🔥 Дана рекурсивная реализация функции Фибоначчи.
Необходимо провести рефакторинг, улучшить производительность и оценить сложность.

Исходный код:

// n: 0, 1, 2, 3, 4, 5, ...
// f: 0, 1, 1, 2, 3, 5, 8, 13, ...

int fib(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);
}

Спойлеры к решению

Подсказки

💡 Текущая реализация имеет экспоненциальную сложность O(2^n).
💡 Проблема — многократные повторные вычисления одинаковых значений.
💡 Можно использовать:

Итеративный подход (самый простой и эффективный).
Мемоизацию (кэширование).
💡 Итеративная версия имеет сложность O(n) и память O(1).
💡 Не забудь проверить входное значение n < 0.

Решение

1️⃣ Итеративное решение (оптимальное)

public class Fibonacci {

    public static int fib(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be >= 0");
        }
        if (n <= 1) {
            return n;
        }

        int prev = 0;
        int curr = 1;

        for (int i = 2; i <= n; i++) {
            int next = prev + curr;
            prev = curr;
            curr = next;
        }

        return curr;
    }

    public static void main(String[] args) {
        System.out.println(fib(5));  // 5
        System.out.println(fib(10)); // 55
    }
}

⏱ Сложность:

Время: O(n)
Память: O(1)

2️⃣ Вариант с мемоизацией (если нужен рекурсивный стиль)

import java.util.HashMap;
import java.util.Map;

public class FibonacciMemo {

    private static final Map<Integer, Integer> cache = new HashMap<>();

    public static int fib(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be >= 0");
        }
        if (n <= 1) {
            return n;
        }

        if (cache.containsKey(n)) {
            return cache.get(n);
        }

        int result = fib(n - 1) + fib(n - 2);
        cache.put(n, result);
        return result;
    }
}

⏱ Сложность:

Время: O(n)
Память: O(n) (кэш + стек рекурсии)

📌 Что важно помнить:

✅ Исходная версия имеет сложность O(2^n) — очень медленная.
✅ Итеративная реализация — самая практичная.
✅ Мемоизация убирает дублирующие вычисления.
✅ Для больших n лучше использовать long или BigInteger.
✅ На собеседовании важно уметь объяснить, почему исходный код неэффективен.