メモ化
factorial をメモ化したバージョンを以下に示す。
このメモ化バージョンでは、「テーブル」は広域の永続性のある変数であり、n をキーとする連想配列のようなものである。このルックアップテーブルが領域(すなわちコンピュータのメモリ)を使うことによって、factorial を同じ引数で繰り返し呼び出したときに要する時間が削減される。
例えば、factorial を最初に引数 5 で呼び出すと、その後 5 以下の引数で呼び出したとき、それらの値は既にメモ化されている。なぜなら、factorial は引数 5、4、3、2、1、0 で再帰的に呼び出され、それぞれの呼び出しについて結果が記憶されるからである。また、引数 5 で呼び出された後に引数 7 で呼び出されると、再帰呼び出しは 2 回で済み(7 と 6)、5! の値は既に記憶されているのでそれが使われる。このように、メモ化された関数は呼び出される度により効率化されていき、結果として全体の高速化が図られる。
次の擬似コードは n の階乗を計算する関数である。
n ≥ 0 であるような全ての整数 n について、関数 factorial の結果は不変である。つまり、x = factorial(3) としたとき、x の値は常に 6 である。上記のメモ化する前のコードでは、結果を得るのに n + 1 回の再帰呼び出しが必要であり、それが計算における時間コストに相当する。プラットフォームのアーキテクチャにも依存するが、時間コストは以下のコストの総和である。
関数のスタックフレームを設定するのにかかるコスト
n と 0 を比較するのにかかるコスト
n から 1 を引くのにかかるコスト
再帰呼び出しのためのスタックフレームを設定するのにかかるコスト
再帰呼び出しの結果と n の乗算を行うコスト
結果を呼び出し側に返すのにかかるコスト
メモ化していない実装では、これらのコストのうち 2 番から 6番が n に比例した回数かかることになる。