末尾再帰をスタックオーバーフローせずに実行する(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