Числа Фибоначчи на C: цикл, рекурсия и почему простой рекурсивный вариант медленный

Последовательность Фибоначчи задаётся рекуррентным соотношением: F(0) = 0, F(1) = 1, а каждое следующее число равно сумме двух предыдущих. Это классический пример, на котором удобно разбирать разницу между итеративным и рекурсивным подходами, оценивать сложность и ловить переполнение.

Итеративный расчёт за O(n)​

Самый прямой способ — идти от нуля до n, храня только два последних значения. Памяти нужно O(1), времени — O(n).

#include <stdio.h>

int fib_iter(int n) {
    if (n < 0) return -1;
    int a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        int tmp = a + b;
        a = b;
        b = tmp;
    }
    return a;
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("F(%d) = %d\n", i, fib_iter(i));
    }
    return 0;
}

Вывод:

F(0) = 0
F(1) = 1
F(2) = 1
F(3) = 2
F(4) = 3
F(5) = 5
F(6) = 8
F(7) = 13
F(8) = 21
F(9) = 34
F(10) = 55

Здесь a на каждой итерации сдвигается вперёд: после n итераций a содержит F(n). Это подтверждается и в cp-algorithms.com: линейное решение с O(1) дополнительной памяти.

Наивная рекурсия и её проблема​

Прямое следование определению выглядит элегантно:

#include <stdio.h>

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

int main(void) {
    printf("F(10) = %d\n", fib_rec(10));
    return 0;
}

Код корректен, но при n = 40 время выполнения становится заметным, а при n = 50 — неприемлемым. Причина — экспоненциальный рост числа вызовов.

Почему вызовов так много​

Дерево вызовов fib_rec(5) выглядит так:

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

fib(3) вычисляется дважды, fib(2) — трижды. В общем случае количество вызовов растёт как O(φⁿ), где φ ≈ 1.618 — золотое сечение. Точная формула для числа вызовов: T(n) = 2·F(n+1) − 1. Для n = 40 это уже более 300 миллионов вызовов.

n	Число вызовов	Примерное время (однопоток)
10	177	мгновенно
20	21 891	мгновенно
30	2 692 537	~10 мс
40	331 160 281	~1–2 с
50	~40 млрд	минуты

Время зависит от процессора и компилятора, но порядок величин сохраняется.

Мемоизация: рекурсия с кэшем​

Если сохранять уже вычисленные значения в массиве, повторные вызовы исчезают. Сложность падает до O(n) по времени и O(n) по памяти.

#include <stdio.h>
#include <string.h>

#define MAX_N 93

long long memo[MAX_N];

long long fib_memo(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    if (memo[n] != -1) return memo[n];
    memo[n] = fib_memo(n - 1) + fib_memo(n - 2);
    return memo[n];
}

int main(void) {
    memset(memo, -1, sizeof(memo));
    printf("F(50) = %lld\n", fib_memo(50));
    printf("F(90) = %lld\n", fib_memo(90));
    return 0;
}

Вывод:

F(50) = 12586269025
F(90) = 2880067194370816120

Здесь используется long long (64-битное знаковое целое), потому что int переполняется уже на F(47). Максимальный индекс для long long без переполнения — 92: F(92) = 7540113804746346429, а F(93) = 12200160415121876738 уже превышает LLONG_MAX.

Ограничение по глубине рекурсии​

Мемоизация сохраняет рекурсивную структуру. Для n = 92 глубина стека вызовов составляет около 92 фреймов — это безопасно. Но если бы n было порядка десятков тысяч, стек мог бы переполниться. В таких случаях лучше использовать итеративный вариант или увеличивать размер стека.

Переполнение: где граница для int и long long​

Тип	Максимальное значение	Максимальный n без переполнения
int (32 бит, знаковый)	2 147 483 647	46
unsigned int (32 бит)	4 294 967 295	47
long long (64 бит, знаковый)	9 223 372 036 854 775 807	92
unsigned long long (64 бит)	18 446 744 073 709 551 615	93

Если нужно F(n) для n > 93, придётся использовать библиотеку произвольной точности (например, GMP) или реализовывать длинную арифметику вручную.

Быстрое возведение матрицы: O(log n)​

Существует способ вычислить F(n) за логарифмическое время. Идея основана на матричном представлении рекуррентности:

| F(n+1)  F(n)   |   | 1  1 |^n
| F(n)    F(n-1) | = | 1  0 |

Возведение матрицы 2×2 в степень n выполняется бинарным возведением за O(log n) умножений. Ниже — реализация на чистом C:

#include <stdio.h>

typedef struct {
    long long m[2][2];
} Mat;

Mat mat_mul(Mat a, Mat b) {
    Mat c;
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            c.m[i][j] = 0;
            for (int k = 0; k < 2; k++) {
                c.m[i][j] += a.m[i][k] * b.m[k][j];
            }
        }
    }
    return c;
}

Mat mat_pow(Mat base, long long exp) {
    Mat result = {{ {1, 0}, {0, 1} }};
    while (exp > 0) {
        if (exp & 1) {
            result = mat_mul(result, base);
        }
        base = mat_mul(base, base);
        exp >>= 1;
    }
    return result;
}

long long fib_fast(int n) {
    if (n <= 0) return 0;
    Mat base = {{ {1, 1}, {1, 0} }};
    Mat res = mat_pow(base, n);
    return res.m[0][1];
}

int main(void) {
    printf("F(10) = %lld\n", fib_fast(10));
    printf("F(50) = %lld\n", fib_fast(50));
    printf("F(92) = %lld\n", fib_fast(92));
    return 0;
}

Вывод:

F(10) = 55
F(50) = 12586269025
F(92) = 7540113804746346429

Время работы — O(log n) умножений матриц 2×2, каждое из которых выполняется за константу. На практике для n ≤ 92 разница с итеративным подходом незаметна, но при работе по модулю (например, в задачах конкурентного программирования) этот метод незаменим.

Ограничение: переполнение при умножении​

В mat_mul промежуточные произведения a.m[i][k] * b.m[k][j] могут переполнить long long ещё до того, как результат будет записан. Для n ≤ 92 это не происходит, потому что значения не превышают F(92). Но если нужно работать с большими n по модулю, следует брать остаток после каждого умножения:

c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;

Формула Бине: почему она не подходит для точных вычислений​

Существует замкнутая формула:

F(n) = (φⁿ − ψⁿ) / √5,  где φ = (1+√5)/2, ψ = (1−√5)/2

Поскольку |ψ| < 1, второй член быстро стремится к нулю, и F(n) ≈ φⁿ / √5 с округлением до ближайшего целого. Однако при реализации через double точность теряется уже для n > 70 из-за ограниченной мантиссы (53 бита). Для практических вычислений формула Бине не используется — итеративный или матричный метод дают точный результат без проблем с округлением.

Сравнение подходов​

Метод	Время	Память	Точность	Когда использовать
Итеративный	O(n)	O(1)	точная	Универсальный выбор для n ≤ 92
Наивная рекурсия	O(φⁿ)	O(n) стек	точная	Только как учебный пример
Мемоизация	O(n)	O(n)	точная	Когда нужна рекурсивная структура
Матричное возведение	O(log n)	O(1)	точная	Большие n, работа по модулю
Формула Бине	O(1)	O(1)	приближённая	Не рекомендуется для точных вычислений

Типичные ошибки начинающих​

Отрицательный аргумент. Последовательность определена для n ≥ 0. Если функция принимает int, стоит проверять n < 0 и возвращать код ошибки или завершать программу.

Переполнение без проверки. int переполняется на F(47), и результат становится отрицательным или бессмысленным. Если нужен диапазон — используйте long long и помните про границу n = 92.

Наивная рекурсия для n > 35. Программа «зависает» не из-за бага, а из-за экспоненциального роста вызовов. Если нужно быстро — переключайтесь на итеративный вариант или мемоизацию.

Неинициализированный массив мемоизации. Если memo не заполнен маркером (например, −1), функция будет возвращать мусор. Всегда инициализируйте массив перед первым вызовом.

Проверка результата​

Простой способ убедиться, что реализация корректна — сравнить первые 20 значений с эталонной последовательностью:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181

Если хотя бы одно значение расходится — ищите ошибку в базовом случае или в порядке обновления переменных.

Источники​

• Fibonacci Numbers - Algorithms for Competitive Programming
  
• Main Page - Algorithms for Competitive Programming