末尾呼び出し最適化 とは？

略してTCOとも呼ばれるよ。まず「末尾呼び出し」から説明すると、関数の一番最後の処理が「別の関数を呼ぶだけ」のパターンのことだよ。この場合、呼び出し元の情報をメモリに残しておく必要がないから、スタックフレームを使い回せるんだ。

関数を呼ぶたびに、戻り先やローカル変数の情報がメモリに積み上がるんだ。これがスタックフレーム。お皿を重ねるイメージだね。再帰で1万回関数を呼ぶと1万枚のお皿が積まれて、限界を超えるとスタックオーバーフローでクラッシュしてしまうんだよ。

そうだよ！末尾呼び出しの場合、呼び出し元にもう戻る必要がないから、お皿を新しく積む代わりに今のお皿を上書きできるんだ。だから再帰を100万回やっても、メモリ的にはお皿1枚分で済む。ループと同じ効率で再帰が書けるんだよ。

言語やランタイムによるんだ。Scheme（Lispの方言）は言語仕様でTCOを保証していて、Haskellも遅延評価と組み合わせてサポートしているよ。Scalaは @tailrec アノテーションで末尾再帰を強制チェックできる。JavaScriptはES2015仕様に入ったけど、実際に実装しているのは2026年時点でもSafariだけなんだ。

ポイントは「再帰呼び出しの結果に何もしない」こと。たとえば factorial(n) で return n * factorial(n-1) と書くと、再帰の結果に掛け算が必要だから末尾呼び出しにならない。代わりにアキュムレータ引数を使って return factorial(n-1, acc*n) と書けば、最後の処理が関数呼び出しだけになって末尾再帰になるよ。この書き換えパターンを覚えておくと、関数型プログラミングで再帰を安全に使いこなせるようになるね。