"CSS Live". Сверстай свой мир

Одна из первых тем, которой учат в учебниках по программированию — это рекурсия. Это довольно сложная для понимания тема, ну то есть для некоторых (для меня например). И почти в 90% учебников рекурсию рассматривают на примере чисел Фибоначчи.

Числа Фибоначчи — это последовательность чисел, в которой каждое следующее число является суммой двух предыдущих чисел. Начинается последовательность с нуля и единицы (ноль иногда опускают). Выглядит это так:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34… и так до бесконечности

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

Вот так, примерно, будет выглядеть рекурсия для нахождения n-ного числа:

function fibonacci(n) {
  var num;

  if (n >= 2) {
    num = fibonacci(n - 1) + fibonacci(n - 2);
  } else {
    num = n
  }

  return num;
}

alert(fibonacci(6)); // >>> 8

Всё хорошо, функция отлично находит шестое число в последовательности. Но это только пока… Я не знаю насколько мощный у вас комп, но попробуйте найти пятидесятое число:

alert(fibonacci(50));

Уверяю вас, комп ощутимо задумается, если не повиснет в принципе. То есть эта функция – отличный пример рекурсии, и, вместе с тем, отличный пример того, что рекурсия не самый лучший способ решить задачу. Рекурсия очень прожорлива к ресурсам компа, поэтому нужно, по возможности, её избегать.

Итак как же нам найти любое число в последовательности Фибоначчи? Лезем в википедию и узнаём, что нам на помощь приходит формула Бине:

Нас интересует часть до первого знака равенства, реализуем её:

function fibonacci2(n) {
  var sq5 = Math.sqrt(5); // сохраняем значение корня из 5, чтобы сэкономить ресурсы
  var a = (1 + sq5) / 2;
  var b = (1 - sq5) / 2;
  return (Math.pow(a, n) - Math.pow(b, n)) / sq5;
}

alert(fibonacci2(500)); // >>> 1.3942322456169767e+104

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

Ссылка на пример

Ссылка на источник