Какие знаешь проблемы при рекурсивном вычислении миллионного числа Фибоначчи?

Какие знаешь проблемы при рекурсивном вычислении миллионного числа Фибоначчи?

Рекурсивное вычисление чисел Фибоначчи — классический пример неэффективного алгоритма. При попытке вычислить миллионное число Фибоначчи возникают серьёзные проблемы, которые критичны для backend-разработки.

Экспоненциальная сложность времени

Проблема: Наивный рекурсивный алгоритм имеет временную сложность O(2^n), что абсолютно неприемлемо:

long long fib_naive(int n) {
    if (n <= 1) return n;
    return fib(n-1) + fib(n-2);  // Каждый вызов раздваивается!
}

Для n=50 потребуется более 1 квадриллиона операций. Для n=1,000,000 это вычисляется в течение астрономического времени (дольше, чем существует Вселенная).

Почему так происходит? Функция вычисляет одни и те же значения миллионы раз:

• fib(n) = fib(n-1) + fib(n-2)
• fib(n-1) = fib(n-2) + fib(n-3)
• fib(n-2) уже вычислено дважды!

Дерево рекурсии растёт экспоненциально, и подавляющее большинство вычислений — дублирование.

Переполнение стека (Stack Overflow)

Проблема: Каждый рекурсивный вызов добавляет кадр на стек вызовов. Для n=1,000,000 стек переполнится.

fib(1000000)  // 1 кадр стека
  -> fib(999999)  // 2 кадра
    -> fib(999998)  // 3 кадра
      -> ...  // Стек обычно ~8MB, рушится после ~10,000-100,000 вызовов

Результат: Программа вылетит с std::bad_alloc или сегментацией ошибке.

Типичный размер стека:

• Linux: 8-16 MB
• Windows: 1-2 MB
• Embedded: 64-256 KB

Даже если переписать на итеративный алгоритм, для миллионного числа потребуется специальная обработка.

Переполнение целого числа (Integer Overflow)

Проблема: Числа Фибоначчи растут экспоненциально. Даже F(100) уже больше типа long long:

// Числа Фибоначчи:
F(90) ≈ 2.88 × 10^18   // Почти переполняет long long (макс ~9.2 × 10^18)
F(93) ≈ 1.2 × 10^19    // Переполнение!
F(1,000,000) — это число с миллионами цифр

Для хранения F(1,000,000) потребуется big integer библиотека:

#include <boost/multiprecision/cpp_int.hpp>
using bigint = boost::multiprecision::cpp_int;

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

Сложность хранения: Число F(1,000,000) имеет примерно 200,000 цифр. Его хранение требует ~200 KB памяти на одно число.

Неэффективность работы памяти

Проблема: Каждый рекурсивный вызов создаёт новый кадр стека с параметрами и локальными переменными. Это генерирует огромное количество контекстных переключений и кэш-промахов.

Мониторинг производительности:

// Наивный подход: O(2^n) времени, O(n) стека
auto start = std::chrono::high_resolution_clock::now();
auto result = fib_naive(40);  // Уже 20+ секунд!
auto duration = std::chrono::high_resolution_clock::now() - start;
std::cout << "Duration: " << duration.count() << " ns" << std::endl;

Правильные решения

1. Мемоизация (кэширование результатов):

std::map<int, bigint> memo;
bigint fib_memo(int n) {
    if (n <= 1) return n;
    if (memo.find(n) != memo.end()) return memo[n];
    return memo[n] = fib_memo(n-1) + fib_memo(n-2);
}
// Сложность: O(n) времени, O(n) памяти

2. Итеративный подход (лучший выбор):

bigint fib_iterative(int n) {
    if (n <= 1) return n;
    bigint a = 0, b = 1;
    for (int i = 2; i <= n; ++i) {
        bigint temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}
// Сложность: O(n) времени, O(1) дополнительной памяти

3. Матричное возведение в степень (O(log n)):

// Использует матрицу [[1,1],[1,0]]^n
// Даёт результат за O(log n) операций с big integers
// Наиболее эффективный метод

Практические выводы для backend-разработки

• Никогда не используйте наивную рекурсию для вычисления Фибоначчи в production
• Всегда профилируйте алгоритмы с реальными размерами входных данных
• Помните о ограничениях стека при рекурсии (максимум 10-100k вызовов)
• Используйте big integer библиотеки для работы с большими числами
• Выбирайте между итеративностью (O(n)) и матричным методом (O(log n)) в зависимости от требований

Этот пример демонстрирует важность анализа алгоритмической сложности и выбора правильного подхода перед реализацией.