末尾再帰

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

手続き型言語と末尾再帰

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

プログラムの手動変換

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

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

{ 変換前 }
function F (a1:T1, a2:T2, ..., an:Tn) : T0
begin
   P ;
   return func (b1, b2, ..., bn) ;
end ;

{ 変換後 }
function F (a1:T1, a2:T2, ..., an:Tn) : T0
begin
   loop
     P ;
     a1 := b1 ;
     a2 := b2 ;
         :
     an := bn ;
   end loop ;
end ;

{
Ti は型、P は手続き、bi は値または a1～an に対する副作用を伴わない式である。
それ以外の識別子は変数を表すPの中に最低1個のreturn文がないと
スタックオーバーフローあるいは無限ループになる。
}

関数型言語と末尾再帰

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

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

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

Common Lisp での末尾再帰の例：

(defun fact (n)
  (labels ((ifact (n r)
             (if (= n 0)
                 r
                 (ifact (- n 1) (* n r)))))
    (ifact n 1)))

F#での末尾再帰の例：

// 非末尾再帰
let rec fact n =
  if n = 0 then 1 else fact (n - 1) * n

// 末尾再帰
let fact n =
  let rec ifact n r =
    if n = 0 then r else ifact (n - 1) (n * r)
  ifact n 1

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

末尾呼出し最適化

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

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

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

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