真正末尾再帰

提供: MonoBook
2016年3月2日 (水) 05:13時点におけるimported>Administratorによる版
ナビゲーションに移動 検索に移動

真正末尾再帰とは、末尾再帰を利用することで確実に末尾再帰最適化が行われることが保証されるプログラミング言語のことである。単に「真正」「真正的」などと呼ばれることもある。

概要

末尾再帰を利用することで確実に末尾再帰最適化が行われるため、末尾再帰をいくら使用してもコールスタックなどのリソースを食いつぶすなどの挙動がなく、結果として再帰の呼び出し回数に制限がない状態をいう。

また、このような末尾再帰最適化が必ず行われることが保証されている処理系プログラミング言語)を指す。

正格評価関数型プログラミング言語を名乗る言語であれば、ほぼ真正末尾再帰であると思ってよい。ただし正格評価の代表格であるLISPだけは何故か真正末尾再帰ではない。その派生品であるSchemeなどでは真正になっている。

関連項目

参考文献