末尾再帰 - odz buffer

shinh さんの末尾再帰の理解が適当だというのが個人的には衝撃。しかし gcc の最適化はすごいなー。
ちなみに、末尾再帰は何かって言うと再帰呼び出しした関数の戻り値をそのまま返すような再帰関数のことなわけだけど。

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

は再帰呼び出しの後、乗算を行う必要があるから、末尾再帰じゃないと。
で、こういうのは典型的で、

int fact(int n)
{
    return fact_sub(n, 1);
}

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

と書き直せば末尾再帰になる。いや、乗算の順序が変わっているので厳密には等価ではないんだけど。
で、Scheme だとどれくらい違うんだろね、と思って sum で速度測定。(fact で時間を測定できるような値を入れると多倍長演算のほうに時間をとられるので)

(use srfi-1)

(define (sum1 ls)
  (if (null? ls)
      0
      (+ (car ls) (sum1 (cdr ls)))))

(define (sum2 ls)
  (letrec ((sum-tr
            (lambda (xs a)
              (if (null? xs)
                  a
                  (sum-tr (cdr xs) (+ a (car xs)))))))
    (sum-tr ls 0)))

(define (sum3 ls)
  (fold + 0 ls))

(define (sum4 ls)
  (let ((a 0))
    (for-each (lambda (n) (set! a (+ a n))) ls)
    a))

(define (main args)
  (let ((ls (iota 100000 1)))
    (time (sum1 ls))
    (time (sum2 ls))
    (time (sum3 ls))
    (time (sum4 ls))))

で、Gauche での結果

;(time (sum1 ls))
; real   0.406
; user   0.080
; sys    0.220
;(time (sum2 ls))
; real   0.046
; user   0.000
; sys    0.050
;(time (sum3 ls))
; real   0.107
; user   0.010
; sys    0.100
;(time (sum4 ls))
; real   0.058
; user   0.000
; sys    0.060

およそ10倍の差。結構差が出るものだな。