Lispは遅くて実用にならないと揶揄されるで、それに論駁するために竹内郁雄先生が2時間ほどで考えだしたという「たらい回し関数」を、手元で実行してみた。計算量はtarai(2n,n,0)の場合にO(n^n)ということらしい。これだけ短いコードで、これほどの計算量の爆発感がある関数は、ほかにないのじゃないかという。 def tarai(x, y, z) if y < x then tarai( tarai(x-1, y, z), tarai(y-1, z, x), tarai(z-1, x, y) ) else y # not z! end end loop do print "x, y, z? :" print tarai(*(gets.chomp!.split(" ").map(&:to_i))), "\n" end 12,6,0あたりでも2秒ほどかかる。14,7,0とすると、もう返事が戻