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 ってホントにおもしろいですね。