如何不修改递归斐波那契函数声明实现memoize缓存优化

直接调用withMemo(fibo)无效的核心原因是：原斐波那契函数内部的递归调用指向的是fibo变量绑定的原始函数，withMemo只会生成一个新的缓存函数，不会影响原函数内部的调用指向，下面是两种不需要修改原函数内部逻辑的实现方案：

方案1：替换函数变量绑定 #

这是成本最低的方案，只需要修改原函数的声明关键字（如果是const声明改为let即可），不需要改动任何内部代码：

// 原函数内部逻辑完全不变，仅把const改为let
let fibo = (n) => {
  if (n <= 1) return 1
  return fibo(n - 2) + fibo(n - 1)
}
// 将fibo变量的指向替换为缓存后的版本
fibo = withMemo(fibo)

// 此时调用fibo(50)会直接命中缓存，性能大幅提升
console.log(fibo(50))

如果不想修改顶层fibo的const声明，可以在局部作用域内做绑定替换，完全不影响顶层定义：

// 顶层原fibo声明完全不动
const fibo = (n) => {
  if (n <= 1) return 1
  return fibo(n - 2) + fibo(n - 1)
}

// 局部生成缓存版本
const memoizedFibo = (() => {
  let localFibo = withMemo((n) => {
    if (n <= 1) return 1
    return localFibo(n - 2) + localFibo(n - 1)
  })
  return localFibo
})()

方案2：通用递归缓存工具（基于Y组合子思想） #

如果需要批量处理任意递归函数的缓存，可以实现一个通用工具，只需要传入原函数和缓存器，不需要修改原函数的任何计算逻辑：

const memoizeRecursive = (fn, memoizer) => {
  // 递归注入缓存逻辑
  const rec = memoizer((...args) => fn(rec, ...args))
  return rec
}

// 使用时仅需要给原递归函数新增第一个参数接收递归器，计算逻辑完全不变
const fibo = (rec, n) => {
  if (n <= 1) return 1
  return rec(n - 2) + rec(n - 1)
}

// 生成缓存版本
const memoizedFibo = memoizeRecursive(fibo, withMemo)
console.log(memoizedFibo(50))

这个方案的优势是完全解耦了递归逻辑和缓存逻辑，同一个递归函数可以搭配任意缓存策略使用，不需要调整内部实现。

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