Trampoline で再帰処理の最適化 - Qiita

Scala ではコンパイラや JavaVM では最適化されない末尾相互再帰を Trampoline (トランポリン) を使って解決します。また末尾再帰になっていない再帰処理をコールスタックを消費しないで実行するためにも Trampoline を使用します。 C/C++/Java 暦が長いんで末尾最適化されずコールスタック量も想定できない処理は自前でループに書き換えていましたけど、後述する問題を Trampoline で解決できないかなと知識まとめがてらの投稿です。 前提知識: Scala の末尾相互再帰 関数やメソッドの再帰呼び出しはその再帰が処理の一番最後であれば理論的にループ命令に展開できます。これは再帰ごとにその呼び出しのコールスタックをクリアしても問題ないためで、ループの方がコールスタックを消費しないので再帰がどれだけ深くなっても一定量のスタック空間で済む (Stack Overf