Числа Фибоначчи

Подход

Реализуем три варианта: рекурсивный (базовый), рекурсивный с мемоизацией (оптимизированный) и итеративный (самый эффективный). Для рекурсии используем Map для кеширования результатов.

Решение

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

public class FibonacciSolver {
    
    /**
     * Метод 1: Наивная рекурсия (без оптимизаций)
     * Медленный для больших n из-за повторных вычислений.
     */
    public static long fibRecursive(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n не может быть отрицательным");
        }
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        return fibRecursive(n - 1) + fibRecursive(n - 2);
    }
    
    /**
     * Метод 2: Рекурсия с мемоизацией
     * Кеширует уже вычисленные значения.
     */
    public static long fibMemoized(int n) {
        return fibMemoized(n, new HashMap<>());
    }
    
    private static long fibMemoized(int n, Map<Integer, Long> memo) {
        if (n < 0) {
            throw new IllegalArgumentException("n не может быть отрицательным");
        }
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        // Проверяем, есть ли значение в кеше
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        // Вычисляем и сохраняем в кеш
        long result = fibMemoized(n - 1, memo) + fibMemoized(n - 2, memo);
        memo.put(n, result);
        
        return result;
    }
    
    /**
     * Метод 3: Итеративный подход (самый эффективный)
     * O(n) время, O(1) дополнительная память.
     */
    public static long fibIterative(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n не может быть отрицательным");
        }
        if (n == 0) return 0;
        if (n == 1) return 1;
        
        long prev2 = 0;   // fib(0)
        long prev1 = 1;   // fib(1)
        long current = 1;
        
        // Вычисляем от fib(2) до fib(n)
        for (int i = 2; i <= n; i++) {
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        
        return current;
    }
    
    public static void main(String[] args) {
        System.out.println("=== Примеры вычисления Фибоначчи ===");
        int[] testCases = {0, 1, 5, 10, 15, 20};
        
        for (int n : testCases) {
            long recursive = fibRecursive(n);
            long memoized = fibMemoized(n);
            long iterative = fibIterative(n);
            
            System.out.printf("fib(%2d): recursive=%3d, memoized=%3d, iterative=%3d%n",
                n, recursive, memoized, iterative);
        }
        
        // Проверка для больших значений
        System.out.println("\nБольшие значения (итеративный метод):");
        System.out.println("fib(50) = " + fibIterative(50));
        System.out.println("fib(100) = " + fibIterative(100));
        
        // Обработка исключений
        try {
            fibIterative(-5);
        } catch (IllegalArgumentException e) {
            System.out.println("\nОшибка: " + e.getMessage());
        }
    }
}

Сложность

• Рекурсия (наивная): O(2^n) время, O(n) память (стек вызовов)
• Рекурсия с мемоизацией: O(n) время, O(n) память (кеш)
• Итеративный подход: O(n) время, O(1) память (только две переменные)

Примеры и тест-кейсы

1. Базовые случаи: fib(0)=0, fib(1)=1, fib(2)=1
2. Средние значения: fib(5)=5, fib(10)=55
3. Большие значения: fib(50)=12586269025 (требует long)
4. Граничные случаи: fib(-1) выбросит исключение

Edge cases и типичные ошибки

1. Отрицательные индексы: Проверяем с помощью IllegalArgumentException.
2. Переполнение: Для очень больших n нужно использовать BigInteger или BigDecimal.
3. Повторные вычисления: Наивная рекурсия вычисляет одно число многократно — это худший подход.
4. Производительность: Мемоизация существенно ускоряет рекурсию, но итеративный метод все равно быстрее и экономнее по памяти.
5. Stack overflow: Глубокая рекурсия без мемоизации может переполнить стек вызовов.

Для собеседования лучше показать все три подхода, объяснив компромиссы между ними.