末尾再帰の違和感

末尾再帰がいまいちわからない

自分も末尾再帰には違和感を感じていました。今のところ、「末尾再帰」は、「末尾再帰の最適化」とセットで、「再帰」で「ループ」表現する為の手段だとして納得しています。
それ以外で「末尾再帰」という概念が必要な場面は思いついていません。

階上計算 on xyzzy-lisp
普通の再帰
(defun fact (x)
  (if (zerop x)
	  1
	(* x (fact (1- x)))))

末尾再帰
(defun fact-tail (x &optional (a 1))
  (if (zerop x)
	  a
	(fact-tail (1- x) (* x a))))

末尾再帰は呼び出しした関数の返し値に対して計算を行わないので、バックトラックする必要がありません。その為、スタックを消費せずに計算を行えます(処理系が対応していれば。schemeは対応している)。

でも、それはわざわざ再帰的に書いて末尾最適化まで行って行う必要が処理でしょうか。ここに違和感を感じました。なぜなら、再帰はまだ見ぬ値に対して計算するのがミソだと考えていたからです。
普通の再帰は「未来の値」に対する計算を記述することでアルゴリズムを素直に記述することが出来ます。対して、末尾再帰は「過去の値」*1を次の関数に渡して計算するだけです。それならば普通にループで書けば良いのに、と思っていました。
上記コードを見ても判るように、普通の再帰が直感的であるのに対して、末尾再帰はぱっと見どういう処理が書かれているか判りません。

わざわざ「末尾再帰」というナゾの概念を持ち出す理由が判らなかったのですが、下記のサイトを読んで、ちょっと納得できました。
http://www.shiro.dreamhost.com/scheme/docs/schemersway-j.html

上記の「ループで書けば良いのに」と言うのは全くの間違いでした。「ループは言語に必要か？」と言う観点が必要だったようです。
そしてschemeが出した結論が、「末尾再帰と末尾再帰の最適化でスタックを消費しない再帰が書ける」だったようです。

以上が、現時点での「末尾再帰」の理解となります。

*1:「累積器」と呼んだりするらしい