末尾再帰のソースを表示

'''末尾再帰'''（まつびさいき）とは、[[再帰]]的な[[関数]]や[[プロシージャ]]において、自身の再帰呼び出しが、その計算における最後のステップになっているような再帰のパターンのことである。再帰にかかわらず一般に、そのような最後の呼び出しを末尾呼び出し （[[:en:Tail call]]）という。呼び出しではなく、戻り先を保存しないジャンプに[[コンパイラ最適化|最適化]]できるという特徴がある（[[#末尾呼出し最適化]]）。

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

===プログラムの手動変換===
一般に手続き型言語では、[[サブルーチン]]呼び出しのたびにスタックに呼び出し先から戻るための情報を保存する。そのため再帰が深くなりすぎると[[スタックオーバーフロー]]でプログラムが異常終了する。

そのような場合、次のようにループに変換して回避する。

<source lang="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文がないとスタックオーバーフローあるいは無限ループになる
*/
</source>

==関数型言語と末尾再帰==
関数型言語では、自身の戻り値に別の関数の戻り値を使うという末尾呼び出しによるプログラミングは自然なスタイルである。特に[[Scheme]]は、後述の最適化を施すべきパターンを形式的に定め、最適化を行うよう仕様で定めている（properly tail-recursive）。

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

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

[[LISP]]での末尾再帰の例：
<source lang="lisp">
(defun factorial (n &optional (acc 1))
  (if (<= n 1)
      acc
    (factorial (- n 1) (* acc n))))
</source>
末尾行では定義と同型の式が現れている。

==末尾呼出し最適化==
'''末尾呼出し最適化'''（'''まつびよびだしさいてきか'''、tail call optimization）とは、末尾呼出しのコードを、戻り先を保存しないジャンプに変換することによって、スタックの累積を無くし、効率の向上などを図る手法である。末尾呼出しの除去（tail call elimination）などとも言う。

関数呼出しでは、呼出し毎にスタックに呼出し元に戻るための情報を保存する。これをジャンプに最適化できれば、みかけの再帰がいくら深くなってもスタックが溢れたりすることがなくなる。この最適化が言語処理系によって行われるのであれば、プログラマが再帰的な手続きをループに変換することなく記述しても、再帰のためのスタック溢れを気にかける必要が無くなる。

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

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

[[Category:プログラミング|まつひさいき]]