递归+记忆化实现斐波那契函数返回函数定义而非数值问题求解

问题根因 #

你的代码出现该问题的核心原因有两个：

• 递归调用时错误指向了外层fib函数：fib函数本身的返回值是inner函数对象，你定义的外层fib没有接收参数，无论传入什么值都会直接返回inner函数。递归时写的fib(n-1) + fib(n-2)实际是生成了两个新的inner函数对象做相加，函数相加时会自动转为字符串拼接，最终就得到了函数定义拼接的结果。
• 记忆化逻辑的递归调用没有复用当前闭包下的inner函数，也导致memo对象完全没有被复用。

修复方案 #

只需要把递归调用的目标从fib改为内层的inner即可，修改后的完整代码如下：

function fib() {
  // 创建记忆化对象
  let memo = {};
  // 内层递归函数
  function inner(n) {
    // 边界情况1：n=0返回0
    if (n === 0) return 0;
    // 边界情况2：n=1返回1
    if (n === 1) return 1;
    // 边界情况3：命中缓存直接返回
    if (memo[n]) return memo[n];
    // 递归计算：注意这里调用的是inner而非fib
    memo[n] = inner(n - 1) + inner(n - 2);
    return memo[n];
  }
  return inner;
}

// 测试代码
let innerFib = fib()
console.log(innerFib(1)); // -> 1
console.log(innerFib(2)); // -> 1
console.log(innerFib(7)); // -> 13

额外优化提示 #

如果你不想每次使用都先调用fib()生成内层函数，可以用立即执行函数表达式（IIFE）直接封装闭包，使用起来更便捷：

const fib = (function() {
  let memo = {};
  return function inner(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    if (memo[n]) return memo[n];
    memo[n] = inner(n - 1) + inner(n - 2);
    return memo[n];
  }
})();

// 直接调用即可
console.log(fib(1)); // -> 1
console.log(fib(2)); // -> 1
console.log(fib(7)); // -> 13

内容的提问来源于stack exchange，提问作者DaShaman