メモ化とは何か？

メモ化は、純粋関数の出力をその引数をキーとして格納し、同じ入力が再び現れたときにキャッシュされた結果を返す最適化です。高価な計算は、呼び出しのたびではなく、異なる入力ごとに一度だけ実行されます。これは、関数が決定論的で副作用が無いことに依存します。

なぜ重要か

メモ化は、繰り返される高価な計算を安価な参照へと変え、重なり合う再帰的な作業では劇的な効果があります。コストは、キャッシュのためのメモリと、入力が安定して出力に対応するという前提です。