Rubyで末尾再帰最適化

背景

普段のrailsコーディングでは末尾再帰最適化なんて
まあ間違いなく使う機会がない。
けど訳あって末尾再帰最適化しなきゃ
stack level too deep (SystemStackError)
になるプログラム動かしたかった.

結論

このページが完璧にまとまってた.

obelisk.hatenablog.com

ので今日は書くのサボれる<-

末尾再帰とは

関数Aの呼び出しの最後が関数Aの呼び出しであること.

def func_a(n, a=0)
  # process
  return func_a(n - 1, n + a)
end

末尾再帰最適化とは

プログラミング言語が末尾再帰のプログラムを
スタックオーバーフローしないように
解釈してくれるようになってる事。

つまり末尾再帰でコードを書いても、
その言語が最適化してくれてないと意味にないよって話

普通の再帰は

def loop_normal(n)
  1 + loop_normal(n-1)
end

loop_normal(4)

これはn=4の呼び出しは内部でn=3の呼び出しを行い,
n=3の呼び出しは、、、続く
となるのでn=4の呼び出しは
n=3, n=2, n=1の呼び出しの結果をずっと保持しなきゃならん
ということ.
これでnがでかくなると保持しきれず死ぬ