f(n)=f(n-1)+f(n-2),
for n=2,3,4,...n and
f(0)=0 and f(1)=1
一个斐波那契数列数列是前面两个斐波那契数的加和。所以我们一般写的代码可能就是这样的：
function fibonacci(n) {
return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}
这个算法以教学为目的,但非常低效的,不仅因为递归,而且两次调用fibonacci函数,在函数里面右侧调用的fibonacci(n-2) 在表达式左侧调用fibonacci(n-1)时就已完全计算过一遍。对于这个特定卡塔(类似打怪升级里面的级数)，我们想实现缓存的解决方案。这是特别酷的,因为它将让我们继续使用递归算法,同时仍然保持足够迅速的得到一个答案。
memoize的版本的诀窍是,保持一个缓存数据结构(最有可能的关联数组),将斐波纳契数列的值缓存。当获取一个斐波那契数列值时,首先在缓存中查找，如果有则直接返回值,如果没有,再计算并把它放进缓存。
使用memoize的数据结构重构函数的递归Fibonacci以避免递归调用的缺陷。
分析
斐波那契数列里面不断的递归调用自身，列入输入的是 70，那么需要计算69和68的值。
在计算69的过程中又计算了 68、67、、、、、1。 计算 68的过程又计算了 67、66、、、、、、、1的值，如此重复计算的值太多了，花费的时间也就比较多。
缓存思想恰好可以减少不必要的重复计算。当第一遍计算69的值时就递归计算了 68、67、66、、、1的值，之后的每次都先查看是否有缓存，有就直接返回缓存值，避免了重复计算。
代码
let cache = [];
let fibonacci = function(n) {
if(n < 2)
return n;
if(cache[n]){
return cache[n];
}
return cache[n] = fibonacci(n-1) + fibonacci(n-2);
}
或者
var fibonacci = function() {
var memo = [0, 1];
var fib = function(n) {
var result = memo[n];
if (typeof result != "number") {
result = fib(n - 1) + fib(n - 2);
memo[n] = result;
}
return result;
}
return fib;
}();
Underscore.js库有提供实现该功能的memoize()函数。使用方法如下：
var fibonacci = _.memoize(function(n) {
return n < 2 ? n: fibonacci(n - 1) + fibonacci(n - 2);
});
对于耗时计算计算较长的计算，强烈推荐使用哦~
发表评论：