递归函数计算Fibonacci数列之记忆优化

  • 2017-09-15
  • 143
  • 1

标题有点绕口,但是看完两个案例你就知道了。
Fibonacci数列简称斐波那契数列,每个fibonacci数字是之前两个fibonacci的数字之和。

普通的递归算法–求解

// 递归
var fibonacci = function (n) {
	return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
};
for (var i = 0; i <= 10; i++) {
	document.writeln('//' + i + ':' + fibonacci(i) + '
'); } // 0: 0 // 1: 1 // 2: 1 // 3: 2 // 4: 3 // 5: 5 // 6: 8 // 7: 13 // 8: 21 // 9: 34 // 10: 55

观察这个结果fibonacci函数被调用了453次,我们调用了11次,他自身调用了442次计算。可能你觉得递归计算不都这样嘛,的确我开始也是这么认为的。下面看用了“记忆“的算法。


记忆–加持求解

// 记忆加持
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;
        console.log(memo)
    }
    return result;
  };
  return fib;
}();
fibonacci(10);
// 输出
// [0, 1, 1]
// [0, 1, 1, 2]
// [0, 1, 1, 2, 3]
// [0, 1, 1, 2, 3, 5]
// [0, 1, 1, 2, 3, 5, 8]
// [0, 1, 1, 2, 3, 5, 8, 13]
// [0, 1, 1, 2, 3, 5, 8, 13, 21]
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

当我们调用fiboacci(10)会放回一样的结果,但是它只调用了29次,我们调用了11次,它自身调用了18次,相比较前面的递归算法,有了大大的有话,我们用一个memo数组存储我们的结果,并将它影藏在闭包中。

评论

- 友情链接 - Theme by Qzhai