Что такое числа Фибоначчи?

Числа Фибоначчи — это последовательность целых чисел, где каждое последующее число равно сумме двух предыдущих. Стандартная последовательность начинается с 0 и 1: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Наивная рекурсивная реализация на C++ (неэффективная):

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

Эта реализация имеет экспоненциальную временную сложность O(2ⁿ) из-за повторяющихся вычислений.

Оптимальная итеративная реализация с динамическим программированием (O(n)):

int fibonacci(int n) {
    if (n <= 1) return n;
    int a = 0, b = 1, c;
    for (int i = 2; i <= n; ++i) {
        c = a + b;
        a = b;
        b = c;
    }
    return b;
}

Применение в C++:

• Тестирование рекурсии и оптимизации хвостовых вызовов.
• Бенчмаркинг алгоритмов.
• Реализация алгоритмов, использующих золотое сечение (например, в хешировании).