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

Числа Фибоначчи — это элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …, в которой первые два числа равны 0 и 1, а каждое следующее число равно сумме двух предыдущих. В этом уроке разберём, как вычислить n-е число Фибоначчи в Java двумя способами — итеративно через цикл for и рекурсией — и сравним их скорость.

Формула ряда Фибоначчи

Математически последовательность задаётся рекуррентной формулой: первые два члена фиксированы, а каждый следующий — сумма двух соседних слева:

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2), при n > 1

Из этой формулы напрямую вытекают два подхода к реализации: итеративный (идём снизу вверх в цикле, храня два последних значения) и рекурсивный (буквально повторяем формулу, вызывая функцию для n-1 и n-2).

Числа Фибоначчи через цикл for

Итеративный способ — самый быстрый и практичный. Мы храним только два предыдущих числа и на каждом шаге сдвигаем «окно» вперёд. Сложность алгоритма линейная — O(n).

private static long calculateWithFor(int n) {
    if (n <= 1) {
        return n;
    }
    long first = 0;   // F(0)
    long second = 1;  // F(1)
    long result = 0;
    for (int i = 2; i <= n; i++) {
        result = first + second;
        first = second;
        second = result;
    }
    return result;
}

Цикл выполняется ровно n-1 раз, память под массив не нужна — достаточно трёх переменных. Именно так стоит вычислять числа Фибоначчи в реальном коде.

Числа Фибоначчи через рекурсию

Рекурсивный вариант дословно повторяет математическую формулу: метод вызывает сам себя для n-1 и n-2, пока не дойдёт до базовых случаев F(0) = 0 и F(1) = 1. Выглядит элегантно, но за эту элегантность приходится дорого платить — сложность экспоненциальная, O(2^n).

private static long recursive(int n) {
    if (n <= 1) {
        return n;
    }
    return recursive(n - 1) + recursive(n - 2);
}

Почему так медленно? Потому что одни и те же значения пересчитываются снова и снова. Например, при вызове recursive(5) значение F(2) вычисляется три раза, F(1) — пять раз. Дерево вызовов растёт экспоненциально, и уже при n = 45–50 программа начинает заметно «тормозить», а при n = 250 практически зависает.

Сравнение скорости и сложности

Чтобы увидеть разницу вживую, замерим время обоих алгоритмов. Для замера используем System.nanoTime() — это правильный инструмент для бенчмарков (в отличие от LocalTime, у которого низкое разрешение):

public class FibonacciExample {
    public static void main(String[] args) {
        int n = 45;

        long start1 = System.nanoTime();
        long r1 = recursive(n);
        long time1 = System.nanoTime() - start1;
        System.out.println("Рекурсия: " + r1 + ", время: " + time1 / 1_000_000 + " мс");

        long start2 = System.nanoTime();
        long r2 = calculateWithFor(n);
        long time2 = System.nanoTime() - start2;
        System.out.println("Цикл for: " + r2 + ", время: " + time2 / 1_000_000 + " мс");
    }

    private static long calculateWithFor(int n) {
        if (n <= 1) {
            return n;
        }
        long first = 0;
        long second = 1;
        long result = 0;
        for (int i = 2; i <= n; i++) {
            result = first + second;
            first = second;
            second = result;
        }
        return result;
    }

    private static long recursive(int n) {
        if (n <= 1) {
            return n;
        }
        return recursive(n - 1) + recursive(n - 2);
    }
}

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

Рекурсия: 1134903170, время: 4300 мс
Цикл for: 1134903170, время: 0 мс

Итеративный вариант выдаёт ответ мгновенно, а рекурсивный при n = 45 уже думает несколько секунд. Сравним оба подхода:

Большие числа и переполнение long

Числа Фибоначчи растут очень быстро, поэтому тип данных быстро становится тесным. F(92) = 7540113804746346429 — это последнее число ряда, которое ещё помещается в long. Начиная с F(93) происходит переполнение, и метод молча вернёт неверный (в том числе отрицательный) результат — исключение при этом не выбрасывается.

Если нужно считать числа Фибоначчи для больших n, используйте BigInteger — он поддерживает целые числа произвольной длины:

import java.math.BigInteger;

private static BigInteger fibonacci(int n) {
    BigInteger first = BigInteger.ZERO;
    BigInteger second = BigInteger.ONE;
    for (int i = 2; i <= n; i++) {
        BigInteger next = first.add(second);
        first = second;
        second = next;
    }
    return n == 0 ? BigInteger.ZERO : second;
}

Частые ошибки

• Использование чистой рекурсии для больших n. При n около 45–50 программа заметно тормозит, а при 250 — фактически зависает из-за экспоненциальной сложности. Берите цикл или мемоизацию.
• Переполнение long. После F(92) результат в long становится некорректным. Для больших значений нужен BigInteger.
• Замер времени через LocalTime. Для бенчмарков используйте System.nanoTime(): у него высокое разрешение, и он не зависит от системных часов и перехода через полночь.
• Путаница в нумерации. Договоритесь заранее, с чего начинается ряд — с F(0) = 0 или с F(1) = 1. От этого зависит, какое число считается «первым».