関数型言語と末尾再帰
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/13 14:08 UTC 版)
関数型言語では、自身の戻り値に別の関数の戻り値を使うという末尾呼び出しによるプログラミングは自然なスタイルである。特にSchemeは、後述の最適化を施すべきパターンを形式的に定め、最適化を行うよう仕様で定めている。 また、関数型言語の処理系には、プログラム全体を継続渡しスタイルに変換し、全ての呼び出しを末尾呼び出しに変換する手法もある。 置き換えモデルを基準に考えれば、ある手続きが返す値はその中で最後に呼び出した手続きの結果に等しく、それ以外の部分は過程の分岐または副作用をもつ場合のみ意味を持つ。従って上記関数的な観点では手続きの末尾だけを考慮すればよく、ここで再帰が行われる場合を末尾再帰という。 Common Lisp での末尾再帰の例: (defun factorial (n &optional (acc 1)) (if (<= n 1) acc (factorial (- n 1) (* acc n)))) 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 末尾行では定義と同型の式が現れている。
※この「関数型言語と末尾再帰」の解説は、「末尾再帰」の解説の一部です。
「関数型言語と末尾再帰」を含む「末尾再帰」の記事については、「末尾再帰」の概要を参照ください。
- 関数型言語と末尾再帰のページへのリンク