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

5. Оптимизировать вычисление числа Фибоначчи

Условие задачи:
Дана рекурсивная реализация функции Фибоначчи:

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

    return fib(n - 1) + fib(n - 2);
}

Необходимо провести рефакторинг:

устранить повторные вычисления;
улучшить производительность;
корректно обработать отрицательные значения n;
оценить временную и пространственную сложность решения.

Последовательность Фибоначчи:

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

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

Подсказки

💡 В исходной рекурсии одни и те же значения вычисляются много раз.
💡 Например, при вычислении fib(5) значение fib(3) будет вычислено несколько раз.
💡 Если рекурсия не является требованием, проще всего заменить её итерацией.
💡 Для вычисления очередного числа достаточно хранить только два предыдущих значения.

Решение

Предпочтительный вариант — итеративное решение:

public static int fib(int n) {
    if (n < 0) {
        throw new IllegalArgumentException(
                "n должен быть неотрицательным"
        );
    }

    if (n <= 1) {
        return n;
    }

    int previous = 0;
    int current = 1;

    for (int i = 2; i <= n; i++) {
        int next = previous + current;

        previous = current;
        current = next;
    }

    return current;
}

Например:

System.out.println(fib(0));  // 0
System.out.println(fib(1));  // 1
System.out.println(fib(5));  // 5
System.out.println(fib(10)); // 55

В исходном варианте:

return fib(n - 1) + fib(n - 2);

строится дерево рекурсивных вызовов, в котором одни и те же значения вычисляются повторно.

Например:

fib(5)
├── fib(4)
│   ├── fib(3)
│   └── fib(2)
└── fib(3)

fib(3) уже вычисляется как минимум дважды, а с ростом n число повторных вызовов быстро увеличивается.

Временная сложность такой рекурсии экспоненциальная — O(φⁿ), где φ ≈ 1.618. Её также часто упрощённо оценивают сверху как O(2ⁿ).

Итеративный вариант выполняет один проход:

for (int i = 2; i <= n; i++)

и хранит только два предыдущих значения.

Сложность после рефакторинга:

время — O(n);
дополнительная память — O(1).

Если требуется сохранить рекурсивный подход, можно использовать мемоизацию:

public static int fib(int n) {
    if (n < 0) {
        throw new IllegalArgumentException(
                "n должен быть неотрицательным"
        );
    }

    Integer[] cache = new Integer[n + 1];

    return fib(n, cache);
}

private static int fib(int n, Integer[] cache) {
    if (n <= 1) {
        return n;
    }

    if (cache[n] != null) {
        return cache[n];
    }

    cache[n] = fib(n - 1, cache)
            + fib(n - 2, cache);

    return cache[n];
}

У варианта с мемоизацией:

время — O(n);
память — O(n) на кэш и стек рекурсии.

Для обычной задачи итеративная версия проще и экономнее по памяти.

Важно также учитывать диапазон типа int: F(46) ещё помещается в int, а F(47) уже приводит к переполнению. Для больших значений следует использовать long, а затем при необходимости BigInteger.