ruby再帰最適化-テール再帰、スタックの追加

再帰は使いやすいが、スタックオーバーフロー(SystemStackError:stack level too deep)を招きやすい.簡単な解決策は2つあり,1つはrubyのstack sizeを大きくし,1つはテールで再帰する.
Stack level too deep

def factorial(n)
  raise InvalidArgument, "negative input given" if n < 0
  if n == 0
    1
  else
    factorial(n - 1) * n
  end
end

入力が小さい場合、コードは正常に動作します.

 irb> factorial(1_000).to_s.size
 => 2568

入力を大きくするとエラーが発生します

 irb> factorial(100_000).to_s.size
 SystemStackError: stack level too deep

ソリューション-スタックサイズを増やす
ruby vmのスタックサイズを増やすことができます.RUBYを設定する限りTHREAD_VM_STACK_SIZEという環境変数でいいです.export RUBY_THREAD_VM_STACK_SIZE=50000000
また、RubyVM::DEFAULT_PARAMSというコマンドで元の値を表示することもできます.
しかし、このような方法でも問題を完全に解決することはできません.もっと良い方法は、尾再帰を使用することです.
テール再帰
rubyのデフォルトでは、テール再帰はサポートされていません.まず、構成をオンにします.

RubyVM::InstructionSequence.compile_option = {
  tailcall_optimization: true,
  trace_instruction: false
}

末尾再帰の実現は以下の通りである.

def factorial_by_tail_call(n, accumulator = 1)
  raise InvalidArgument, "negative input given" if n < 0

  return accumulator if n == 0
  return factorial_by_tail_call(n - 1, accumulator * n)
end

尾再帰はどうして溢れなかったの?
簡単にfactorialではfactorial(n - 1) * nにnが必要なので、現在の実行(procedure call)にはメモリが必要です.しかし、factorial_by_tail_callは異なり、factorial_by_tail_call(n - 1, accumulator * n)は他の変数に依存せず、直接実行することができ、メモリに存在する必要はないので、最適化することができます.
言語対末尾再帰のサポート状況
まず,テール再帰最適化には解釈器のサポートが必要である.
rubyも後からサポートされていますが、手動で開く必要があります.
JAvaはサポートされていません.clojureはサポートされていませんが、recurで同じ効果を達成しました.
最後に、前世紀のlispは尾再帰をサポートしています!