时间戳

首页 > 解决方案 > 记忆递归斐波那契函数

javascript - 记忆递归斐波那契函数

问题描述

我创建了一个withMemo函数，它返回所提供函数的记忆版本。

const memoizedFn = withMemo(fn)

我怎样才能记住这个与递归一起工作的斐波那契函数？

const fibo = (n) => {

  if (n <= 1) return 1
  
  return fibo(n - 2) + fibo(n - 1)
}

确实withMemo(fibo)并没有提高性能，因为内部的递归调用fibo仍然指向未记忆的版本......

所以我必须改变 fibo 的声明以使 momoization 工作：

    const momoizableFibo = memoizer => {
      const fibo = (n) => {
    
        if (n <= 1) return 1
      
        return memoizer(fibo)(n - 2) + memoizer(fibo)(n - 1)
      }
      
      return memoizer(fibo)
    }
// momoizableFibo(withMemo)(50) // takes a ms

有没有办法记忆fibo（或任何其他递归函数）而不像我那样改变它的声明？

标签： javascriptalgorithmrecursionmemoization

解决方案

您可以使用let fibo而不是const fibo. 然后用fibo记忆的版本替换变量。通过更新fibo嵌套调用现在将引用 memoizedfibo函数而不是原始函数。

let fibo = (n) => {
  console.log(n); // <- show original fibo calls
  if (n <= 1) return 1;
  return fibo(n - 2) + fibo(n - 1);
}
// update fibo variable so the nested fibo call calls the memoized version
fibo = withMemo(fibo);

console.log("fibo(3)", "//=>", fibo(3));
console.log("fibo(5)", "//=>", fibo(5));
console.log("fibo(2)", "//=>", fibo(2));


// simplified memoize function, only works for serializable parameters
function withMemo(fn) {
  const cache = new Map();
  return function (...args) {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key);
    const result = fn(...args);
    cache.set(key, result);
    return result;
  }
}

推荐阅读