Как разработчик, вы, вероятно, сталкивались с задачей написания функции для вычисления значений в последовательности Фибоначчи. Эта классическая проблема часто возникает на собеседованиях по программированию, обычно требуя рекурсивной реализации. Однако иногда интервьюеры могут потребовать конкретных подходов. В этой статье мы рассмотрим наиболее распространенные реализации последовательности Фибоначчи в JavaScript.

Что такое последовательность Фибоначчи?

Для начала давайте освежим память. Последовательность Фибоначчи представляет собой ряд чисел, каждое из которых представляет собой сумму двух предыдущих. Он начинается с 0 и 1:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Общие подходы к реализации

1. Рекурсивный подход

Самый традиционный запрос — рекурсивная реализация:

function fibonacciRecursive(n) {
  if (n 



Несмотря на простоту, этот подход неэффективен для больших значений n. На MacBook Pro i9 с 16 ГБ ОЗУ вычисление 40-го числа Фибоначчи заняло около 1,5 секунды:


console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms




При попытке вычислить 50-е число вкладка Chrome перестала отвечать на запросы.

2. Рекурсивный подход с кэшированием (мемоизацией)

Следующий вариант этого вопроса — повысить производительность за счет добавления механизма кэширования в нашу рекурсивную реализацию:


function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n 



Этот подход вводит кешированный объект с начальными значениями 0 и 1. Для любого заданного числа мы сначала проверяем, вычислили ли мы уже его значение Фибоначчи. Если это так, мы возвращаем кэшированный результат вместо его пересчета. В противном случае мы вычисляем это значение и сохраняем его в кэше.

Увеличение производительности существенно (конечно, за счет использования дополнительной памяти). Вычисление 40-го числа Фибоначчи заняло ~0,02 мс:


console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms




3. Итеративный подход с циклом for

Другой распространенный вариант — реализация последовательности Фибоначчи с использованием цикла for:


function fibonacciWithIteration(n) {
    if (n 



Этот подход намного быстрее, чем базовый рекурсивный метод (без кэширования):


console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms




Итеративный подход позволяет эффективно обрабатывать очень большие входные значения:


console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e 292
VM325:23 With iteration: 0.5830078125 ms





  
  
  Бонус: возврат последовательности Фибоначчи в виде массива


Интервьюеры также могут попросить вас вернуть всю последовательность Фибоначчи до n-го числа в виде массива. Давайте реализуем это, используя как рекурсивный, так и итеративный подходы.

Рекурсивный подход


function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1]   arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]




Эта функция работает следующим образом:

Для 0 и 1 мы возвращаем жестко запрограммированные массивы.
Для других случаев:

• Мы получаем последовательность предыдущего номера и сохраняем ее в arr.
• Мы вычисляем currentValue путем суммирования двух последних значений arr.
• Мы объединяем arr и currentValue в новый массив и возвращаем его.

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

function fibonacciSequenceWithIteration(n) {
  if (n 



Эта функция работает следующим образом:

Если входное значение равно 0, мы возвращаем массив только с элементом 0.
Для других случаев:

• Мы инициализируем переменные prev и next для хранения предыдущего и следующего значений.
• Создаем arr с начальными значениями [0, 1].
• Мы повторяем от 2 до n, помещая сумму prev и next в arr на каждой итерации.
• Мы обновляем предыдущее и следующее значения и переходим к следующей итерации.

Заключение

Хотя в этой статье рассматриваются несколько распространенных реализаций последовательности Фибоначчи, это не исчерпывающий список. Если вы встречали другие варианты интервью или своей работы, поделитесь ими в комментариях!

Будьте в курсе последних новостей о JavaScript и разработке программного обеспечения! Присоединяйтесь к моему каналу в Telegram, чтобы получить больше информации и обсуждений: TechSavvy: Frontend & Backend.