Rubyでの末尾呼び出しの最適化について

再帰処理の最適化についてなんもわからんという問題に向き合う

はじまり

普通に再帰処理書いてるとスタックが溢れてエラーになる。どうすりゃいいの？調べたら末尾呼び出しの最適化というワードが出てきた。

末尾呼び出しとは

処理の最後の呼び出し。
関数の最後にやってる処理のこと。

末尾再帰とは

末尾再帰（まつびさいき）とは、再帰的な関数やプロシージャにおいて、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。

呼び出し元に戻らなくてもいいような再帰呼出しのこと。

末尾呼び出しの最適化とは

末尾呼出しのコードを、戻り先を保存しないジャンプに変換することによって、スタックの累積を無くし、効率の向上などを図る手法である。

再帰はスタックが積まれていくといずれスタックオーバーフローするのでそうならないよう最適化すること

書いてみる

ある課題がRubyだったのでそれでやる

tco.rb

# 末尾呼び出しでない
# add(n - 1)を計算して結果を返す必要がある
def add(n)
  return 0 if n.zero?
  n + add(n - 1)
end

# 末尾呼び出しに修正
def tco_add_1(n, acc = 0)
  return acc if n.zero?
  tco_add_1(n - 1, acc + n)
end

# 末尾呼び出しの最適化有り
RubyVM::InstructionSequence.compile_option = {
  :tailcall_optimization => true,
  :trace_instruction => false
}
RubyVM::InstructionSequence.new(<<-EOS).eval

# 末尾最適化有り
def tco_add_2(n, acc = 0)
  return acc if n.zero?
  tco_add_2(n - 1, acc + n)
end

EOS

確認してみる

irb(main):001:0> require './tco.rb'
=> true

irb(main):002:0> add(100_000)
Traceback (most recent call last):
...
...
SystemStackError (stack level too deep)

irb(main):003:0> tco_add_1(100_000)
Traceback (most recent call last):
...
...
SystemStackError (stack level too deep)

irb(main):004:0> tco_add_2(100_000)
=> 5000050000

まとめ

末尾再帰のイメージがなんとなくできるようになった
Haskell だとどうなってんだろうか

これだけできたとしても、その課題が解けたかと言われるとそうでもないと思うので悔しいが精進するしかない。

fugafuga.write

日々のログ