stack level too deepの倒し方

SystemStackError - stack level too deep

rubyを書いてるとよく遭遇するこのエラーを倒すgemを作りました。

stack level too deepとは

バグで無限再帰を作ってしまった時や、再帰関数の再帰が深すぎる時に起きるエラーです。

def factorial(n)
  # return 1 if n.zero?　を忘れて無限再帰になってしまった時
  n * factorial(n-1)
end
factorial 10 #=> SystemStackError: stack level too deep

def hoge
  # 数万回の再帰は深すぎてできない
  hoge if rand < 0.99999
end
hoge #=> SystemStackError: stack level too deep

こうなったが最後、通常は再帰をやめてループに展開するしかありません。
(環境変数RUBY_THREAD_VM_STACK_SIZEで必要な分指定する方法もあります)

# before
def hoge
  do_something
  hoge if rand < 0.99999
end

# after
def hoge
  loop do
    do_something
    break unless rand < 0.99999
  end
end

# before
def fibonacci i, memo = {}
  return i if i <= 1
  memo[i] ||= fibonacci(i-1, memo) + fibonacci(i-2, memo)
end

# after
def fibonacci i
  a, b = 0, 1
  i.times do
    a, b = b, a+b
  end
  a
end

beforeとafterが違いすぎる...

No Stack Level Too Deep

そこ作ったのが no_sltd https://github.com/tompng/no_sltd

$ gem install no_sltd

# before
def hoge
  do_something
  hoge if rand < 0.99999
end

# after
require 'no_sltd'
no_sltd def hoge
  do_something
  hoge if rand < 0.99999
end

def の前に no_sltd をつけるだけでstack level too deepが出なくなります。

どうやってる?

stackはThreadやFiberごとに確保されてるようです。
なので、stack levelが一定以上深くなる毎に、普通に再帰呼び出しする代わりに Fiber.new { func }.resume で新しいstackを使うようにしています。
(stackが残りがどれだけ使えるか測る手段があればメモリ効率よくなりそう)

遅くないの?

遅いです。メモリもばか食いします。

どういう時に使えばいいの?

遅くてもいいから再帰が動いて欲しい時、使い捨てのプログラムがstack level too deepになって困った時などにどうぞ