Rubyの末尾再帰最適化を理解する

RubyではSchemeなどとは異なって、末尾再帰の最適化を勝手にしてはくれません。

再帰は再帰なんかじゃない！末尾再帰こそが真の再帰なんだ！

でもid:athosさんが、Rubyで末尾再帰最適化を実現するコードを書いてくれました。

http://d.hatena.ne.jp/athos/20110119/p1

自分の実力だと一見しただけでは何をしているか理解できなかったので、少し自分用にコードを整理してその処理を追ってみます。

class Module
   def tco(meth)
     called = false
     tmp = nil
 
     orig_meth = "orig_#{meth}"
     alias_method orig_meth, meth
     private orig_meth
 
     define_method(meth) do |*args|
       unless called
         called = true
         args = tmp until result = send(orig_meth, *args)
         result
       else
         tmp = args
         false
       end
     end
   end
 end
 class Sum
   def sum1(n, acc=0)
     return acc if n == 0
     sum1(n-1, acc+n)
   end
 
   def sum2(n, acc=0)
     return acc if n == 0
     sum2(n-1, acc+n)
   end
   tco :sum2
 end
 
 s = Sum.new
 s.sum2(100000) # => 5000050000
 s.sum1(100000) # => 
 # ~> -:25: stack level too deep (SystemStackError)

tcoクラスメソッドに対象のメソッドを渡せばその最適化がなされます。tcoメソッドでは具体的には以下の処理をしています。

1. 元メソッド(sum2)の別名(orig_sum2)を定義する(alias_method)。
2. 元メソッド名を持った新メソッドを定義する(define_method)。
3. 新メソッドにおいて別名定義した元メソッドを反復的に呼び出す。

これによってsum2が呼ばれると以下の処理がなされます。

1. 新メソッドが呼ばれ、その中で元メソッドが呼ばれる(unless節)。
2. 元メソッドの呼び出しは、その引数nが0(resultが有意な値)になるまでここで反復的に繰り返される。
3. 元メソッドの再度の呼び出しにより、今度は新メソッドのelse節が実行される(called=true)。
4. ここでその引数argsが次の元メソッドの反復呼び出しに渡されるよう保持する。
5. 元メソッドの呼び出しにおいて引数nが0になると、accが返りresultに渡される。
6. これによってuntilループを抜けて、このメソッドの返り値としてresultが得られることとなる。

なるほど！

100円〜で好評発売中！
M'ELBORNE BOOKS

• ruby 117
• recursion 3