末尾再帰

末尾再帰（まつびさいき）とは、プログラミング手法のひとつで、再帰のある関数またはプロシージャのおこなうべき最後のステップが、関数またはプロシージャの再帰的な呼び出しになるようにすることである。再帰にかかわらず一般には、末尾呼び出し （en:Tail call）という。呼び出しをジャンプに最適化できるという特徴がある（#末尾最適化）。

LISPなどの関数型言語に典型的に出現する。

手続き型言語と末尾再帰

C言語のような副作用と構造化を基本とする手続き型言語では、言語処理系による自動的な末尾呼び出しへの変換やその最適化（末尾最適化）は難しい。自己再帰を注意して書けば、最適化によりループにできるコンパイラもある、という程度である。

プログラムの手動変換

一般に手続き型言語では、呼び出しを繰り返す度に実行中断された手続きの状態を保存しなければならない。そのため再帰が深くなりすぎるとコールスタックなどの資源が不足してプログラムが停止してしまう（スタックオーバーフロー）。

このような場合、次のような変換を施し、再帰呼び出しを、手続き型のループに変換すると回避できる。

/* 変換前 */
T_0 func (T_1 a_1, T_2 a_2, ..., T_n a_n ) {
   P
   return func(na_1, na_2, ..., na_n);  
}
 
/* 変換後 */
T_0 func (T_1 a_1, T_2 a_2, ..., T_n a_n ) {
   for (;;) {
     P
     a_1 = na_1;
     a_2 = na_2;
      :
     a_n = na_n;
   }
}
/* T_i は型、P は手続き、na_i は式を表す。それ以外の識別子は変数を表す 
Pの中に最低1個のreturn文がないとスタックオーバーフローあるいは無限ループになる
*/

関数型言語と末尾再帰

一方、関数型言語では、基本的に副作用を持たないので、自身の戻り値に、別の関数の戻り値を使うという、末尾呼び出しによるプログラミングが自然に可能である。特にSchemeは、仕様で処理系に末尾最適化をおこなったのと等しい結果になることを要求している。

また、関数型言語の処理系には、プログラム全体を継続渡しスタイルに変換し、全ての呼び出しを末尾呼び出しに変換する手法もある。

置き換えモデルを基準に考えれば、ある手続きが返す値はその中で最後に呼び出した手続きの結果に等しく、それ以外の部分は過程の分岐または副作用をもつ場合のみ意味を持つ。従って上記関数的な観点では手続きの末尾だけを考慮すればよく、ここで再帰が行われる場合を末尾再帰という。

LISPでの末尾再帰の例：

(defun factorial (n &optional (acc 1))
  (if (<= n 1)
      acc
    (factorial (- n 1) (* acc n))))

末尾行では定義と同型の式が現れている。

末尾最適化

末尾最適化（まつびさいてきか）とは、末尾再帰のコードを反復に変換することによって処理効率を向上し、必要なスタック領域を軽減する手法である。

言語が手続き呼び出しを行うとき、通常は呼び出しを重ねる毎にコールスタックなどの資源を消費していく。一方、末尾最適化を許容する言語では、終端文脈での手続き呼び出しに限って、ジャンプで実行することでリソースを節約する。これは主として再帰的アルゴリズムをロスなく自然に実装する際に有効となる。

原理的には、継続渡しによるgotoと同等のジャンプ処理では、手続きの呼び出し元の情報を保存する必要がないことに帰着する。この場合returnはgotoの特殊なケースで、ジャンプ先が呼び出し元に等しいケースである。末尾最適化があれば、手続きの再帰を行なう時でも、結果はループと等価な処理手順となり、どれほど深い再帰を行なってもスタックオーバーフローを起こさない。このような振る舞いは「正しい終端再帰」と呼ばれる。Schemeは実装仕様として正しい終端再帰を要求する言語である。

Schemeに限らず、一部Cコンパイラなどでも条件がそろえば、再帰呼び出しが最適化される事がある。