Во-первых, ваш алгоритм не совсем корректен.
function Fibo(n) {
if (n<2)
return n;
else
return FIBO(n-1)+FIBO(n-2);
};
Во-вторых, в принципе, такой алгоритм является крайне медленным. Вот пример его стэка вызовов для пятого числа.
Если не вдаваться в подробности, то уже 50-е число такой алгоритм будет считать несколько минут.
Посему могу предложить использовать memoize подход (как в underscore)
var FIBO2=_.memoize(function(n) {{
if (n<2)
return n;
else
return FIBO2(n-1)+FIBO2(n-2);
});
либо воспользоваться итеративным алгоритмом
function FIBO3(n) {
if (n<2) return n;
var x=0,
y=1,
z;
for (var i=1; i<n; i++) {
z=x+y;
x=y;
y=z;
}
return z;
};
Итеративный алгоритм опережает остальные по скорости на несколько порядков при разовых вычислениях, однако memoize подход позволяет сэкономить на вычислениях при частом использовании функции (+за одно выполнение закэшируются результаты для всех n, стоящих перед требуемым).
