末尾再帰
tail recursive
末尾呼び出しでかつ、その呼び出しが再帰になっているもの 具体例
code:example.c
function foo(data) {
a(data);
return foo(data);
}
このfooは末尾呼び出しで、かつ再帰呼び出しをしている
code:hs
sum xs = sum' xs 0
where
sum' [] r = r
sum' (y:ys) r = sum' ys (y+r)
rは状態として機能しているmrsekut.icon
sum'の定義が末尾再帰になっている
=のすぐ右にsum'(自分自身)が来ているのがポイント
= sum' ...になっている
末尾再帰じゃない例
code:hs
sum [] = 0
sum (x:xs) = (+) x (sum xs)
ただの再帰関数を、末尾再帰に変換すること、はなんと呼ぶのか
継続で言う、CPS変換的な
末尾再帰にするのが嬉しい場合
この記事を雑に読む感じ以下の場合で話が全く異なる
その言語が遅延評価をするかどうか
その関数がリストを生成するのか、数値を生成するのか
『基礎からわかるElm』.icon pp.82-83にもちょっと書いてる
monad