為什么高階函式只呼叫一次

我很難理解為什么這個例子中的 memoize 似乎只被呼叫一次。查看代碼，我希望“備忘錄列印一次”在每一層遞回中列印。但是，它只列印一次。

const memoize = fn => {
  console.log("memo prints once")
  const cache = {};
  
  return (...args) => {
      console.log("memo prints witch each iteration")
    const argsString = JSON.stringify(args);
    if (!cache[argsString]) {
      cache[argsString] = fn(...args);
    }
    return cache[argsString];
  }
};

const factorial = memoize(n => {
    if (n === 0) return 1;
    else return (factorial(n - 1) * n);
});



console.log(factorial(3))

相反，“每次迭代都會列印備忘錄”會在每一層遞回中列印。

uj5u.com熱心網友回復：

階乘實際上是 memo 回傳的函式，因此每次“迭代”時，都會呼叫回傳的函式，而不會呼叫 memo。

您可以在宣告后通過執行 console.log(factorial) 進行驗證。執行備忘錄，然后列印回傳的函式。

所以那條備忘錄是遞回執行的。

uj5u.com熱心網友回復：

要點是你的日志記錄在錯誤的地方來展示記憶是如何作業的。這個版本應該有助于解釋：

const memoize = fn => {
  console.log("memo prints once")
  const cache = {};
  
  return (...args) => {
    // console.log("memo prints witch each iteration")
    const argsString = JSON.stringify(args);
    if (!cache[argsString]) {
      cache[argsString] = fn(...args);
    }
    return cache[argsString];
  }
};

const factorial = memoize(n => {
    console.log(`factorial prints once for the input ${n}`)
    if (n === 0) return 1;
    else return (factorial(n - 1) * n);
});


console .log (factorial (3))
console .log (factorial (5))
console .log (factorial (7))

.as-console-wrapper {max-height: 100% !important; top: 0}

運行一次的代碼是創建快取和使用該快取的新函式。每個輸入值運行一次是傳遞給的匿名階乘函式內的代碼memo。在每次呼叫時運行的是檢查快取以決定是否呼叫該階乘函式的代碼。

如果取消注釋注釋行，您將看到它運行3, 2, 1, and 0, 然后運行5??, 4, 3, 2, 1, and 0，即使最后一個視圖值被快取，但它會采用不會重新計算的分支這些點，我們通過記錄該匿名函式的輸出看到。

uj5u.com熱心網友回復：

使用引數遞回

另一種技術是給你的函式一個額外的引數并使用該引數遞回。這允許更好的控制，因為遞回機制可以完全抽象 -

const memorec = f => {
  let memo = new Map
  return function recur(x) {
    if (memo.has(x)) return memo.get(x)
    console.log(`${f.name}(${x})...`)
    const v = f(recur)(x)
    memo.set(x, v)
    return v
  }
}

const fact = recur => n =>
  n == 0
    ? 1
    : n * recur(n - 1)

const fib = recur => n =>
  n < 2
    ? n
    : recur(n - 1)   recur(n - 2)

const factmemo = memorec(fact)
const fibmemo = memorec(fib)

console.log(factmemo(3)) // 6
console.log(factmemo(6)) // 720
console.log(fibmemo(10)) // 55

.as-console-wrapper { min-height: 100%; top: 0; }

先說評價——

fact(3)...
fact(2)...
fact(1)...
fact(0)...
6
fact(6)...
fact(5)...
fact(4)... // ? fact(3) already computed so fact(4) doesn't repeat work
720
fib(10)... // fib(10) computes fib(9) and fib(8)
fib(9)...  // ? fib(9) skips memoized fib(8) but computes fib(7)
fib(8)...  // ? fib(8) skips memoized fib(7) but computes fib(6)
fib(7)...  // ...
fib(6)...
fib(5)...
fib(4)...
fib(3)...
fib(2)...
fib(1)...
fib(0)...
55

你不小心發現了 Y 組合子

memorec如上所述，實際上只是對Y-combinator的擴展和優化。如果我們去掉所有memo-specific 代碼，我們可以看到 Y 的 vanilla 實作，rec如下所示。遞回是一種功能性遺產，因此與我們祖先發現的一些巧妙技術相關聯可能會令人興奮 -

const rec = f => {
  // ? const memo = ...
  return function recur(x) {
    // ? if(memo.has(x)) ...
    return f(recur)(x)
  }
}

const fact = recur => n =>
  n == 0
    ? 1
    : n * recur(n - 1)

const fib = recur => n =>
  n < 2
    ? n
    : recur(n - 1)   recur(n - 2)

const factrec = rec(fact)
const fibrec = rec(fib)

console.log(factrec(3))
console.log(factrec(6))
console.log(fibrec(10))

.as-console-wrapper { min-height: 100%; top: 0; }

factrec并且fibrec沒有通過記憶優化，但它們仍然得出正確的結果 -

6
720
55

標籤：javascript 递归 函数式编程 高阶函数

上一篇：如何在使用遞回時最好地存盤資料，并在方法被呼叫時重置資料

下一篇：JS、遞回、函式堆疊示例，難懂