いや、早くなるのは分かってたけどめちゃくちゃ早かった*1のでw− P.S. チーター本の7章「動的計画法、メモ化」のサンプルのrubyでのベンチ結果です。 dfs $ ruby -v ruby 2.1.5p273 (2014-11-13) [arm-linux-gnueabihf] $ time ruby hello_dfs.rb 119759850 real 13m50.176s user 13m50.080s sys 0m0.050s hello_dfs.rb $h = 13 $w = 17 def dfs(nowh, noww) return 0 if nowh > $h || noww > $w return 1 if nowh == $h && noww == $w dfs(nowh+1, noww) + dfs(nowh, noww+1) end puts dfs(0, 0)