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

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

普通的递归算法–求解

// 递归
var fibonacci = function (n) {
    return n ');
}

// 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数组存储我们的结果,并将它影藏在闭包中。

点赞
  1. ytu说道:

    可以

发表评论

电子邮件地址不会被公开。 必填项已用*标注