JS：再帰関数をキャッシュで装飾できますか？

Question

確定的な関数の計算結果をキャッシングするデコレータを作成します（単純に1つの引数の関数を仮定します）。一般的な場合には

は、この方法を行うことができている：origFuncが再帰的であるとき

function makeCacheable(origFunc){ 
    let registry = {}; 

    return function (a){ 
    if (a in registry){ 
     return registry[a]; 
    } 

    let res = origFunc(a); 

    registry[a] = res; 

    return res; 
    } 
} 

問題が表示されます：唯一のトップレベルの呼び出しはラッピングキャッシュを経るが、再帰呼び出しスタックの残りの部分はしていませんキャッシュを満たしている。これがなぜ起こるのか説明する必要はありません。 は、同じ方法でキャッシュ可能な再帰関数を作る自然な方法ですか？？

function fibonacciF(n) { 
    if (n <= 2) return 1; 

    let a = 1, b = 1; 

    for (let i = 2; i < n; ++i){ 
    [a, b] = [b, a+b]; 
    } 

    return b; 
} 

function fibonacciR(n) { 
    return n <= 2 ? 1 : (fibonacciR(n-1) + fibonacciR(n-2)); 
} 

let fiboF = makeCacheable(fibonacciF); // OK 
let fiboR = makeCacheable(fibonacciR); // actually is not what expected 

Answer 1

デコレートされたバージョンを格納するために同じ（関数）変数を使用する場合は、動作させることができます。元に戻すために許可するには、関数オブジェクトにプロパティoriginalを追加することができます。

function makeCacheable(origFunc){ 
 
    let registry = {}; 
 
    let f = function (a){ 
 
    if (a in registry){ 
 
     console.log(`retrieving value from registry[${a}]`); 
 
     return registry[a]; 
 
    } 
 
    let res = origFunc(a); 
 
    registry[a] = res; 
 
    return res; 
 
    } 
 
    // Add property for exposing the original function: 
 
    f.original = origFunc; 
 
    return f; 
 
} 
 

 
function fibonacciR(n) { 
 
    console.log(`Called fibonnacci(${n})`); 
 
    return n <= 2 ? 1 : (fibonacciR(n-1) + fibonacciR(n-2)); 
 
} 
 

 
// Demo illustrating the registry is being used: 
 
console.log('Call fibonnacciR(5) with cache turned on:'); 
 
var fibonacciR = makeCacheable(fibonacciR); 
 
var f5 = fibonacciR(5); 
 
console.log(`Result: fibonnaciR(5) = ${f5}`); 
 

 
// Demo illustrating the function can be restored: 
 
console.log('Call fibonnacciR(5) with cache removed:'); 
 
fibonacciR = fibonacciR.original; 
 
f5 = fibonacciR(5); 
 
console.log(`Result: fibonnaciR(5) = ${f5}`);

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

Answer 2

この関数は、fibonacciRという名前の関数を呼び出します。あなたはこの呼び出しがキャッシュを通過したい場合は、あなたがfibonacciRを上書きする必要があります。

fibonacciR = makeCacheable(fibonacciR); 

は同じように再帰関数をキャッシュできるようにする自然な方法はありますか？

一般的に、関数の実装を検査することはできず、再帰的に実装されているのか、ループなどで実装されているのかは違いありません。純関数プログラミングを使用すると、関数全体をキャッシュバージョン（fiboR）のビルディングブロックとしてのみ使用できますが、実装が協調的でない限り、その動作を変更したり、関数の一部のみを使用することはできません（例えば、recursion operatorそれはユーザーが提供することができます）。

上記の解決策では、関数内で使用される変数を上書きすることによってこれらのルールを破りますが、JavaScriptでも常にそうであるとは限りません。