Одна из первых тем, которой учат в учебниках по программированию — это рекурсия. Это довольно сложная для понимания тема, ну то есть для некоторых (для меня например). И почти в 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
Как видим новая функция с легкостью вычислила пятисотый член последовательности, что было бы практически нереально для рекурсии.
Источник: css-live.ru