末尾再帰
一般に再帰呼び出しが可能な言語では、サブルーチン呼び出しのたびにスタックに呼び出し先から戻るための情報を保存する。そのため再帰が深くなりすぎるとスタックオーバーフローでプログラムが異常終了する。
そのような場合、次のようにループに変換して回避する。
関数型言語では、自身の戻り値に別の関数の戻り値を使うという末尾呼び出しによるプログラミングは自然なスタイルである。特にSchemeは、後述の最適化を施すべきパターンを形式的に定め、最適化を行うよう仕様で定めている。
また、関数型言語の処理系には、プログラム全体を継続渡しスタイルに変換し、全ての呼び出しを末尾呼び出しに変換する手法もある。
置き換えモデルを基準に考えれば、ある手続きが返す値はその中で最後に呼び出した手続きの結果に等しく、それ以外の部分は過程の分岐または副作用をもつ場合のみ意味を持つ。従って上記関数的な観点では手続きの末尾だけを考慮すればよく、ここで再帰が行われる場合を末尾再帰という。
Common Lisp での末尾再帰の例:
F#での末尾再帰の例:
末尾行では定義と同型の式が現れている。