Rubyの末尾呼び出し最適化を試す

どうも寝落ちしました。rsnniです。
Classi Advent Calendar 2017 17日目です。

Rubyも末尾呼び出し最適化をサポートしていると聞いたので試してみました。

末尾呼び出し最適化?

例えば、再帰で階乗計算する際に以下のように書いたとします。

def fact(x)
  return 1 if x == 0
  fact(x - 1) * x
end

この場合、再帰呼び出しをしたfactの結果にxをかけているため、
factの計算後に呼び出し元に戻さなければなりません。
これによって深い再帰になるとスタックが溢れる事になります。

そこで、以下のように再帰呼び出しを計算の最後に持ってこれるように書き直します。

def fact_tail_call(x, m = 1)
  return m if x == 0
  fact_tail_call(x - 1, x * m)
end

このように書き直した時に、トップレベル以降の呼び出し元に戻す必要がなくなる事から、
処理系がスタックを積む事なく最適化してくれます。

試してみる

デフォルトではサポートしておらず、コンパイルオプションを指定する必要がるようです...

RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}

RubyVM::InstructionSequence.new(<<-EOS).eval

def fact(x)
  return 1 if x == 0
  fact(x - 1) * x
end

def fact_tail_call(x, m = 1)
  return m if x == 0
  fact_tail_call(x - 1, x * m)
end

EOS

末尾呼び出しでない再帰ではスタックオーバーフローが発生しますが、

irb(main):019:0> fact(10000)
SystemStackError: stack level too deep

末尾再帰では最適化され計算できる事が確認できます。

irb(main):020:0> fact_tail_call(10000)
=> 2846259680917...