畑（＠素人プログラマ）です。

計算機学の専門家の方でしたら、取り立てて論じるほどのことでもないかもしれ
ません。テーマは「再帰とループの違い」についてです。

例えば、必ずと言って例に取り上げられる「階乗の計算」ですが、再帰呼出・
while ループのどちらでも同じことを実現できると思います。

ただ、この場合の両者の違いとして、while ループは外側に関数（ループ内の
ルーチン）の呼出が並べられて展開されるが、再帰呼出は内側に入れ子状に関数
の呼出が展開される、というようなイメージでいいのでしょうか？

while ループだと、
n! = n
n! *= n - 1
n! *= n - 2
n! *= n - 3
（……）
n! *= 2
n! *= 1
という風に階乗の計算と代入が逐次的に行われていくイメージがありますが、
再帰呼出だと、
n! = n * (n - 1)!
n! = n * (n - 1) * (n - 2)!
（……）
n! = n * (n - 1) * (n - 2)! * （……） * 2 * 1
という風に式の展開が終わるまで続いていって、式の展開が終わりきってから、
やっと計算と代入が行われるというイメージがあります。

処理系（ちなみに自分が親しんでいる言語は Perl です）によって違いがあるの
かもしれませんが、同じことをやるのなら、while ループの方が効率は良さそう
な気がします（それに再帰の場合はコンパイラ側のスタック（？）の管理が大変
そうに思える）が、実際のところどうなのでしょう？

# こういうのが関数型と手続型の違いってやつなんだろうか？

-- 
Masanori HATA