无法用斐波那契解决记忆化设计模式

Question

我不明白记忆化设计模式的最后几步。这是我的经典斐波那契计算代码：

//Memoization
      const fiboCache = () => {
        const cache = [0,1];
        const fibo = (x) => {
          let result = cache[x];
          if(typeof result !== 'number') {
            console.log('new calculation for: ' + x);
            result = fibo(x-1) + fibo(x-2);
            cache[x] = result;
          }
          return result;
        };
        return fibo;
      };
      const getFibo = fiboCache();
      console.log(getFibo(4));

对我来说问题是最后一步，我尝试将其分解为如下所示的每次迭代：

4. result=undef; console.log; result=3; cache=[0,1,empty,empty,3]
3. result=undef; console.log; result=2; cache=[0,1,empty,2,3]
2. result=undef; console.log; result=1; cache=[0,1,1,2,3]
1. result=1; return 1;

我了解数组如何作为我下一次计算的缓存，但是一旦我进行最后一次迭代 (1)，我的 result 对象就会变成 1，这会破坏我的递归，我我直接去 return result.

这不是说我只是 returning 1 最后吗？我不应该 return 这里是数组的最后一项吗？

Answer 1

并不是那么简单：您必须在每个 return 时上下递归级别。它会像这样

fibo(4), cache = [0,1] - 不在缓存中；从 fibo(3) 和 fibo(2) 计算
- fibo(3), cache = [0,1] - 不在缓存中；从 fibo(2) 和 fibo(1) 计算它
  - fibo(2), cache = [0,1] - 不在缓存中；从 fibo(1) 和 fibo(0) 计算它
    - fibo(1)，缓存 = [0,1] - return 1 来自缓存
    - fibo(0)，缓存 = [0,1] - return 0 来自缓存
  - 返回 fibo(2)：结果 = fibo(1) + fibo(0) = 1 + 0 = 1；写缓存[2] = 1, return 1
  - fibo(1)，缓存 = [0,1,1] - return 1 来自缓存
- 返回 fibo(3)：结果 = fibo(2) + fibo(1) = 1 + 1 = 2；写缓存[3] = 2, return 2
- fibo(2)，缓存 = [0,1,1,2] - return 1 来自缓存
返回 fibo(4)，缓存 = [0,1,1,2]：结果 = fibo(3) + fibo(2) = 2 + 1 = 3；写缓存[4] =3, return 3

即

每次递归 return 返回到更高级别的值，并且您从顶层获得结果 = 3 而不是您第一次点击 return (1) 时d想
缓存在每个递归级别完成后更新；你永远不会像原来那样以 [0,1,empty,empty,3] 结束。

使用调试器单步执行此操作并观察缓存内容和调用堆栈可能也很有启发性。

无法用斐波那契解决记忆化设计模式

Can't resolve memoization design pattern with fibonacci

javascript

recursion

fibonacci