メモ化再帰で逆から計算する.

\(F(X, Y)\) を, \((X, Y)\) が作れるかどうかを返す関数とする. このとき,

  • \(X = 0 \lor Y = 0\) ならば \(F(X, Y) = true\) である. \(+1\) の操作を繰り返せばいいからである.
  • \(X\) が2で割り切れるならば, \(F(X/2, Y-1)\) を計算してこれが \(true\) ならば \(F(X, Y)\) は \(true\) である.
  • \(Y\) が2で割り切れるならば, \(F(X-1, Y/2)\) を計算してこれが \(true\) ならば \(F(X, Y)\) は \(true\) である.
  • 上で \(true\) にならなければ \(F(X, Y) = false\) である.

となる.