読者です 読者をやめる 読者になる 読者になる

Rubyは末尾呼び出し最適化をサポートしている

Ruby アルゴリズム

Ruby でこれはスタックオーバーフローします。

def add(n, a = 0)
  return a if n.zero?
  add(n - 1, n + a) 
end

puts add(10000)
#=>a.rb:2:in `add': stack level too deep (SystemStackError)


例えばこう対策します。
obelisk.hatenablog.com
上のとおり以前に Ruby で末尾再帰のスタックオーバーフローを避ける方法を書いたのですが、『アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで』を読んでいたら、Ruby は末尾呼び出し最適化(Tail Call Optimization)をサポートしているとの驚くべき記事があった(p.45 )。このブログ記事にも書かれている。こんな感じでやればいいようだ。

tco = <<-EOS
  def add(n, a = 0)
    return a if n.zero?
    add(n - 1, n + a) 
  end
EOS

R = RubyVM::InstructionSequence
R.compile_option = {tailcall_optimization: true, trace_instruction: false}
R.new(tco).eval

puts add(10000)    #=>50005000

確かにスタックオーバーフローしない。いや、驚いた。Ruby ってホントにおもしろいですね。

※参考
class RubyVM::InstructionSequence (Ruby 2.2.0)