末尾再帰
末尾呼出し最適化(まつびよびだしさいてきか、英: tail call optimization)とは、末尾呼出しのコードを、戻り先を保存しないジャンプに変換することによって、スタックの累積を無くし、効率の向上などを図る手法である。末尾呼出しの除去などとも言う。
関数呼出しでは、呼出し毎にスタックに呼出し元に戻るための情報を保存する。これをジャンプに最適化できれば、みかけの再帰がいくら深くなってもスタックが溢れたりすることがなくなる。この最適化が言語処理系によって行われるのであれば、プログラマが再帰的な手続きをループに変換することなく記述しても、再帰のためのスタック溢れを気にかける必要が無くなる。
理論的には、継続渡しによる飛び越し命令(いわゆる「GOTO文」)と同等のジャンプ処理では、手続きの呼出し元の情報を保存する必要がないことに帰着する。この場合 return は飛び越し命令の特殊なケースで、ジャンプ先が呼出し元に等しいケースである。末尾最適化があれば、手続きの再帰を行なう時でも、結果はループと等価な処理手順となり、どれほど深い再帰を行なってもスタックオーバーフローを起こさない。このような振る舞いは「正しい終端再帰」と呼ばれる。Scheme は実装仕様として正しい終端再帰を要求する言語である。
Schemeに限らず、一部Cコンパイラなどでも条件がそろえば、再帰呼び出しが最適化される事がある。