末尾再帰とは？

末尾再帰（Tail Recursion）とは、関数内で行われる再帰呼び出しが関数の最後の処理（末尾）になっている再帰の特殊な形式です。末尾再帰最適化（TCO: Tail Call Optimization）に対応したコンパイラや処理系は、末尾再帰をループに変換することで、スタックフレームを積み重ねずに再帰を実行できます。

通常の再帰では、関数が呼び出されるたびにスタックフレームが積まれるため、再帰の深さが大きいとスタックオーバーフローが発生します。一方、末尾再帰では現在のフレームを使い回すことができるため、定数量のスタック空間で動作します。

末尾再帰への変換には、一般的にアキュムレータパターンが用いられます。途中結果を引数（アキュムレータ）として持ち回ることで、戻り値に演算を残さない形に書き換えます。例えばファクトリアル計算では、末尾再帰版は fact(n, acc=1) のように現在の積をaccに蓄積しながら呼び出します。

末尾再帰最適化の対応状況は言語によって異なります。

• Haskell・Erlang・Scheme などの関数型言語は標準でTCOをサポート
• Scala・F#・Clojure もTCOまたは専用構文（recur等）を持つ
• JavaScript（ES2015以降）は仕様上TCOを定義しているが、主要ブラウザの実装は限定的
• Python・Java は標準ではTCOを行わない

関数型プログラミングではループの代わりに再帰を多用するため、末尾再帰最適化はパフォーマンスと安全性の両面で重要な技法です。