1)低级版本
var fibonacci = function(n) {
if (n == 0 || n == 1) {
return n;
} else {
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
基本上算到fibonacci(50), 就不行了, 老半天。
2) 进阶版一
var fibonacci = function(n) {
var cache = {};
return function(n) {
if (!cache[n])
cache[n] = n < ? n : fibonacci(n - ) + fibonacci(n - );
return cache[n];
}
}();
利用闭包,缓存已计算好的值, fibonacci(200)不超过4ms
3) 进阶版二
var fibonacci = function(n) {
if (n == 0 || n == 1) {
return n;
} else {
var cache = arguments[1] || {};
if (!cache[n]) {
cache[n] = fibonacci(n - 1, cache) + fibonacci(n - 2, cache);
}
return cache[n];
}
}
传递缓存的数据, fibonacci(200) 不超过4ms
4) 终极版
var fibonacci = (function() {
var cache = {};
return function(n) {
if (n == 0 || n == 1)
return n;
if (cache[n - 2] === undefined)
cache[n - 2] = fibonacci(n - 2);
if (cache[n - 1] === undefined)
cache[n - 1] = fibonacci(n - 1);
return cache[n - 1] + cache[n - 2];
}
})();
递归缓存的数据,fibonacci(200) 不超过4ms