Fibonacci: примеры (JAVASCRIPT)

Базовые примеры использования

Рекурсивная реализация

function fibonacciRecursive(n) {
  if (n <= 1) return n;
  return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
}

fibonacciRecursive(7) // 13

Итеративный подход

function fibonacciIterative(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    let c = a + b;
    a = b;
    b = c;
  }
  return n === 0 ? a : b;
}

fibonacciIterative(10) // 55

Альтернативные подходы в JavaScript

Мемоизация

Использование кэширования результатов для ускорения рекурсивных вычислений. Подходит для многократных вызовов.

Генераторы

Создание бесконечной последовательности через функцию-генератор. Позволяет получать значения по требованию.

Математическая формула Бине

Применение замкнутой формулы для прямого вычисления. Быстро работает для больших чисел, но возможны ошибки округления.

Реализации в других языках

Python

def fibonacci(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

fibonacci(8) # 21

PHP

function fibonacci($n) {
    $fib = [0, 1];
    for ($i = 2; $i <= $n; $i++) {
        $fib[$i] = $fib[$i-1] + $fib[$i-2];
    }
    return $fib[$n];
}

echo fibonacci(6); // 8

C

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

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

Отсутствие базового случая в рекурсии

function fibonacciError(n) {
  return fibonacciError(n-1) + fibonacciError(n-2);
}

fibonacciError(5) // RangeError

Неучёт отрицательных значений

function fibonacciNoCheck(n) {
  if (n <= 1) return n;
  return fibonacciNoCheck(n-1) + fibonacciNoCheck(n-2);
}

fibonacciNoCheck(-3) // Бесконечная рекурсия

Переполнение стека при больших n

fibonacciRecursive(50);

Время выполнения слишком велико

Эволюция реализации

Современные версии JavaScript не включают встроенную функцию Фибоначчи. Развитие языка повлияло на доступные подходы:

Оптимизация хвостовой рекурсии

Некоторые движки поддерживают оптимизацию хвостовых вызовов, что улучшает рекурсивные реализации.

BigInt для больших чисел

Появление типа BigInt позволяет вычислять очень большие числа Фибоначчи без потери точности.

Расширенные примеры

Генератор бесконечной последовательности

function* fibonacciGenerator() {
  let [a, b] = [0, 1];
  while (true) {
    yield a;
    [a, b] = [b, a + b];
  }
}

const fibGen = fibonacciGenerator();
const firstTen = Array.from({length: 10}, () => fibGen.next().value);

firstTen // [0,1,1,2,3,5,8,13,21,34]

Мемоизация с использованием Map

const fibonacciMemo = (() => {
  const cache = new Map([[0, 0], [1, 1]]);
  
  function fib(n) {
    if (cache.has(n)) return cache.get(n);
    
    const result = fib(n-1) + fib(n-2);
    cache.set(n, result);
    return result;
  }
  
  return fib;
})();

fibonacciMemo(70) // 190392490709135

Вычисление с использованием формулы Бине

function fibonacciBinet(n) {
  const sqrt5 = Math.sqrt(5);
  const phi = (1 + sqrt5) / 2;
  return Math.round(Math.pow(phi, n) / sqrt5);
}

fibonacciBinet(15) // 610

Функция возвращающая объект с метаданными

function fibonacciExtended(n, start = [0, 1]) {
  const sequence = [...start];
  for (let i = 2; i <= n; i++) {
    sequence[i] = sequence[i-1] + sequence[i-2];
  }
  return {
    value: sequence[n],
    sequence: sequence.slice(0, n+1),
    ratio: n > 1 ? sequence[n] / sequence[n-1] : null
  };
}

fibonacciExtended(8)
// {value: 21, sequence: [0,1,1,2,3,5,8,13,21], ratio: 1.615}