末尾再帰
tail recursive
末尾呼び出しの特殊パターン
末尾呼び出しでかつ、その呼び出しが再帰になっているもの
具体例
末尾呼び出しの具体例から持ってくると ref 末尾呼び出し#609d32161982700000c07cbe
example.cfunction foo(data) {
a(data);
return foo(data);
}この
foo は末尾呼び出しで、かつ再帰呼び出しをしているHaskellでの例 ref
hssum :: Num a => [a] -> a
sum xs = sum' xs 0
where
sum' [] r = r
sum' (y:ys) r = sum' ys (y+r) r は状態として機能している sum' の定義が末尾再帰になっている = のすぐ右に sum' (自分自身)が来ているのがポイント = sum' ... になっている末尾再帰じゃない例
hssum [] = 0
sum (x:xs) = (+) x (sum xs)Scheme言語読めるようになったらまた読みたい
ただの再帰関数を、末尾再帰に変換すること、はなんと呼ぶのか
継続で言う、CPS変換的な
末尾再帰にするのが嬉しい場合
よくわかっていない #??
この記事を雑に読む感じ以下の場合で話が全く異なる
その言語が遅延評価をするかどうか
その言語が末尾再帰の最適化をするかどうか
その関数がリストを生成するのか、数値を生成するのか
monad