Python、再帰とダイナミック・プログラミング

IT速報で以下の記事があった。Pythonでの解き方を少し考えてみた。

blog.livedoor.jp

数列Hが以下のように定義されているとき、H(2015)を求める。

H(0) = 0

H(n) = n - H(H(H(n - 1))) (n > 0)

再帰で書くならかなり簡単である。

def H(n, memo={0:0}):
    if n not in memo:
        memo[n] = n - H(H(H(n-1)))
    return memo[n]

すこし気の利いたところとしては、mutable default argumentで簡単にメモ化を実現しているところ。*1

ただしこのままだとn=2015ではPythonの再帰リミットにぶちあたる。

解決法としては、memoizationしているのをいいことに、何回かにわけて小さな値から計算していくこと

H(500)
H(1000)
H(1500)
print H(2015)

あまり美しくない。あるいは再帰リミットの上限を上げること

import sys
sys.setrecursionlimit(3000)

しかしそもそもPythonのようにスタック作成が重い言語では再帰自体あまり推奨されない。TCOとかやっているschemeで書くならまだしも。あとその場合でもTCOできる書き方に直す場合、ちょっとややこしくなる。

そもそも式をよく見ると、

n >= H(n) >= 0　　(n >= 0)

の不等式が成り立つことが見て取れる。そして、H(n)を計算するためにはx = 1..n-1のすべてのH(x)を計算する必要があることもわかる。

とすれば、むしろiterationを使ったダイナミック・プログラミングのほうがよさそうである。

H = {0:0}
for n in xrange(1, 2016):
    H[n] = n - H[H[H[n-1]]]
print H[2015]

これで無駄なスタックを延々と作ることもなく、メモリ利用はHというディクショナリーに格納する値のみとなる。*2

*1:ぱっと見、メモ化しなかった場合時間コストが指数的爆発を起こすはず。

*2:ちなみに、はい、すみません、Python 2.xです。