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

末尾再帰をスタックオーバーフローせずに実行する(Ruby)

アルゴリズム Ruby

あるプログラムを書いていて、再帰がいわゆる「スタックオーバーフロー」するのに悩まされました。結局そのプログラムはカスだったのですが、スタックオーバーフローをおもしろい方法で回避することを知ったので、メモしておきます。

まず、1 から n までを単純に足すプログラムを、再帰で書きます。

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

puts add(100)    #=>5050

こんな感じですね。これは再帰の呼び出しがメソッドの最後にあるので、「末尾再帰」といいます。これは引数を大きくすると、スタックオーバーフローを引き起こします。

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


これを回避するのに、再帰呼出しの部分を関数を返すようにします。そして、その関数を繰り返し呼び出すメソッドを追加します。

def trcall(value)
  while value.instance_of?(Proc)
    value = value.call
  end
  value
end

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

puts trcall(add(100_0000))    #=>500000500000

確かに、スタックオーバーフローは起きていません。これは、Ruby の Proc が手続きオブジェクト(クロージャここなどを参照)であり、評価が「遅延」されるからです(「遅延評価」といいます)。Ruby の動的な型付けが巧妙に使われています。


これはおもしろい回避法ではないでしょうか。以上の元ネタは下の記事です。
www.geocities.jp
この記事には他にも様々なことが書かれているので、勉強になりました。



次のような方法もあります。

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 add(n, a = 0)
    return a if n.zero?
    add(n - 1, n + a) 
  end
  tco :add
end

puts Sum.new.add(100_0000)    #=>500000500000

トップレベルのメソッドには適用できませんが、元のメソッドを変更なしで使える、スマートな方法です。元ネタは
athos.hatenablog.com
です。ここで多少アレンジされたコードを使いました。これはよく考えられた複雑な方法で、ここでも一種の「遅延評価」が実装されています。


追記
なんと Ruby は末尾呼び出し最適化をサポートしていました。下記事をどうぞ。
obelisk.hatenablog.com