末尾再帰たん萌え - TopCoderとJ言語と時々F#

たとえばF#で階乗をつぎみたいに実装したとするよね↓

let fact n res =
    if n = 0 then res else fact (n-1) (n*res)

末尾再帰たんモエス

なんだけど、末尾再帰って最適化されちゃうんだよね？特にSchemeとかだと。

たとえばさっきの階乗をC風に書けば

int fact(int n, int res) {
    if(n == 0) return res;
    else return fact(n-1, n*res);
}

こんな感じだけど、もしこれがコンパイラとかによって最適化されちゃうとさ、

int fact(int n, int res) {
    while(true) {
        if(n == 0) return res;
        else {
            n = n-1;
            res = n*res;
        }
    }
}

みたいになるの？末尾再帰たんは居なくなっちゃうの？

「末尾再帰たんは、どこへいっちゃったの？」

――『きっと、どこか遠いところへいってしまったんだよ。』

「とおいところって、どこ？」

――『今はまだ分からないだろう。』

「もう会えないの？」

――『大人になって、いつかパフォーマンスを気にするときが来るだろう。そうすれば、きっと末尾再帰がどこへいってしまったのか分かるさ。』

「ぜったい？」

――『ああ。大人になってメモリの事情なんかを知るときっとね。』

まあ、具体的に末尾再帰がどう最適化されてるんだろうなっていうお話。