Реализация на языках программирования

1. Наивная рекурсия (Python)

Сложность: O(2^n) — медленно для больших n

Классический учебный пример, повторяющий математическую формулу, но пересчитывающий одни и те же значения многократно.

def fib_recursive(n: int) -> int:
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

print(fib_recursive(10))  # Вывод: 55

2. Итеративный метод (JavaScript)

Сложность: O(n) по времени, O(1) по памяти

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

function fibIterative(n) {
    if (n <= 1) return BigInt(n);
    let prev = 0n, curr = 1n;
    for (let i = 2; i <= n; i++) {
        [prev, curr] = [curr, prev + curr];
    }
    return curr;
}

console.log(fibIterative(50).toString()); // 12586269025

3. Формула Бине (C++)

Сложность: O(1) — мгновенный расчёт

Позволяет найти n-е число без циклов через Золотое сечение, но ограничена точностью чисел с плавающей точкой (обычно до n ≈ 70).

#include <iostream>
#include <cmath>

long long fibBinet(int n) {
    double phi = (1.0 + std::sqrt(5.0)) / 2.0;
    return std::round(std::pow(phi, n) / std::sqrt(5.0));
}

int main() {
    std::cout << fibBinet(12) << std::endl; // Вывод: 144
    return 0;
}