#102 记忆化斐波那契函数（Memoization）

[kitewhere]

斐波那契数列指的是类似于以下的数列：

1, 1, 2, 3, 5, 8, 13, ....

也就是，第 n 个数由数列的前两个相加而来：f(n) = f(n - 1) + f(n -2)

请你完成 fibonacci 函数，接受 n 作为参数，可以获取数列中第 n 个数，例如：

fibonacci(1) // => 1
fibonacci(2) // => 1
fibonacci(3) // => 2
...

测试程序会从按顺序依次获取斐波那契数列中的数，请注意程序不要超时，也不要添加额外的全局变量。

本题来源：《JavaScript 语言精髓》

[kitewhere]

const fibonacci = ((memory = {}) => n => {
	if(n < 2) return n
	if(memory[n-2] === undefined){
		memory[n-2] = fibonacci(n-2)
	}
	if(memory[n-1] === undefined){
		memory[n-1] = fibonacci(n-1)
	}
	return memory[n] = memory[n-1] + memory[n-2]
})()

[kitewhere]

递归 循环 尾递归都不是关键 关键是记忆 用缓存减少重复的计算
所有需要在要有一个 memory 记录计算结果 缓存命中直接返回 否则计算
既然不能有外部变量就只有闭包了

为什么 memory 用对象比数组效率高
因为数组是有长度 memory[n]=1 需要初始化n-1个 undefined 和一个1

为什么需要计算 memory[n-2] memory[n-1] memory[n] 只计算 memory[n] 不就够了吗
因为前者一次可以缓存3个计算 效率更高

进一步把记忆函数提取出来

"use strict";
let memoize = function(func) {
  let cache = {};
  return function(key) {
    if (!cache[key])
      cache[key] = func.apply(this, arguments);
    return cache[key];
  }
}

let fibonacci = memoize(function(n) {
  return n < 2 ? n : fibonacci(n - 2) + fibonacci(n - 1);
});

参考
https://segmentfault.com/a/1190000007115162
https://github.com/hanzichi/underscore-analysis/issues/23