вернуться к уроку

Числа Фибоначчи

важность: 5

Вычисление рекурсией (медленное)

Решение по формуле, используя рекурсию:

function fib(n) {
  return n <= 1 ? n : fib(n - 1) + fib(n - 2);
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
// fib(77); // не запускаем, подвесит браузер

При больших значениях n оно будет работать очень медленно. Например, fib(77) уже будет вычисляться очень долго.

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

...
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
...

Здесь видно, что значение fib(3) нужно одновременно и для fib(5) и для fib(4). В коде оно будет вычислено два раза, совершенно независимо.

Можно это оптимизировать, запоминая уже вычисленные значения, получится гораздо быстрее. Альтернативный вариант – вообще отказаться от рекурсии, а вместо этого в цикле начать с первых значений 1, 2, затем из них получить fib(3), далее fib(4), затем fib(5) и так далее, до нужного значения.

Это решение будет наиболее эффективным. Попробуйте его написать.

Алгоритм вычисления в цикле

Будем идти по формуле слева-направо:

var a = 1, b = 1; // начальные значения
var c = a + b; // 2

/* переменные на начальном шаге:
a  b  c
1, 1, 2
*/

Теперь следующий шаг, присвоим a и b текущие 2 числа и получим новое следующее в c:

a = b, b = c;
c = a + b;

/* стало так (ещё число):
   a  b  c
1, 1, 2, 3
*/

Следующий шаг даст нам ещё одно число последовательности:

a = b, b = c;
c = a + b;

/* стало так (ещё число):
      a  b  c
1, 1, 2, 3, 5
*/

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

P.S. Этот подход к вычислению называется динамическое программирование снизу-вверх.

Код для вычисления в цикле

function fib(n) {
  var a = 1,
    b = 1;
  for (var i = 3; i <= n; i++) {
    var c = a + b;
    a = b;
    b = c;
  }
  return b;
}

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77) ); // 5527939700884757

Цикл здесь начинается с i=3, так как первое и второе числа Фибоначчи заранее записаны в переменные a=1, b=1.

Последовательность чисел Фибоначчи имеет формулу Fn = Fn-1 + Fn-2. То есть, следующее число получается как сумма двух предыдущих.

Первые два числа равны 1, затем 2(1+1), затем 3(1+2), 5(2+3) и так далее: 1, 1, 2, 3, 5, 8, 13, 21....

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

Напишите функцию fib(n), которая возвращает n-е число Фибоначчи. Пример работы:

function fib(n) { /* ваш код */ }

alert( fib(3) ); // 2
alert( fib(7) ); // 13
alert( fib(77)); // 5527939700884757

Все запуски функций из примера выше должны срабатывать быстро.