末尾再帰の最適化
tail call optimization
末尾再帰の最適化
末尾再帰における末尾呼び出しの除去をする
故に、再帰的に呼ばれてもCall Stackは積まれない
故に、メモリ使用量が減る、Stack Over Flowを抑える
再帰なので、ただの末尾呼び出しの除去にとどまらず、loopに変換することが出来る
ただの末尾呼び出しの除去と異なり、Loopに変換することが出来る
この節を読むと、なぜloopにできるのかがなんとなくイメージできる
例
Babelで末尾再帰の最適化を行いWhile loopに変換している例 ref
実際のコンパイラの最適化など
https://engineering.mercari.com/blog/entry/2019-12-16-081047/
Swift、つまりLLVMでの最適化の話
Swift知らなくても読めるはず
https://qiita.com/takl/items/6d3319e835a27fc5e4b9
ただ単にgotoに変換できない場合の末尾再帰の最適化の例
いくつかのコーナーケースが紹介されていて良い
関連
Syntactic Tail Calls
JSのproposalの一つ
https://speakerdeck.com/kota_yata/mo-wei-hu-bichu-sizui-shi-hua-tojavascript?slide=18
経緯など
参考
末尾再帰による最適化 - Qiita
コールスタックの具体例もあってわかりやすい
https://rn4ru.com/blog/posts/tail-recursion/
説明に継続みがある