自己末尾再帰

Prog D Scheme

再帰 http://www.stdio.h.kyoto-u.ac.jp/~hioki/gairon-enshuu/SchemeNotes/recursive.html を勉強中。
「計算されない項目」が増えると効率が悪いらしい。ローカル関数が使える D と Scheme で早速書いてみた。
D:

/**
 * 計算積み上げ再帰
 */
long totalSum( long nVal )
{
	if( nVal == 0 ) return nVal;
	return nVal + totalSum( nVal - 1 );
}

/**
 * 自己末尾再帰
 */
long totalSum2( long nVal )
{
	long totalSum2_inner( long nVal, long nRes )
	{
		if( nVal == 0 ) return nRes;
		return totalSum2_inner( nVal - 1, nVal + nRes );
	}
	return totalSum2_inner( nVal, 0L );
}


/* */
int main( char[][] args )
{
	// D言語では自分自身が 0 番目に入る
	if( args.length != 2 ) {
		dout.writeLine( "usage: ./l02_d [number]." );
		return 1;
	}

	// long is 64bit + signed
	long sum = totalSum2( toLong( args[1] ) );

	// D の文字列 char[] は ?0 終端しないらしい
	// D の long は C でいうところの long long ( = __int64 )
	dout.printf( "Sigma[%.*s] is %lld.?n", args[1], sum );
	return 0;
}

Scheme:

;; 計算積み上げ再帰
(define (totalSum val)
  (if (= val 0)
	0
	(+ val (totalSum (- val 1)))))

;; 自己末尾再帰
(define (totalSum2 val)
  (define (totalSum2-inner val res)
	(if (= val 0)
	  res
	  (totalSum2-inner (- val 1) (+ val res))))
  (totalSum2-inner val 0))


;; Guile では (car (command-line) ) は自分自身
;; (cdr (command-line) ) に引数が入る
(define *argv* (cdr (command-line)))

;; 引数の取得
(define num (string->number (car *argv*)))

;; 結果表示
(display '"Sigma[")
(display num)
(display '"] is ")
(display (totalSum2 num))
(display #?newline)   ;; 文字データ


結果。60000 を引数にした、time (tcsh) の 3回平均。

D 積み上げ再帰: 0.022u 0.031s 0:00.09 55.5%     0+0k 0+0io 0pf+0w
D 自己末尾再帰: 0.021u 0.036s 0:00.10 55.3%     0+0k 0+0io 0pf+0w
guile 積み上げ再帰: Stack overflow
guile 自己末尾再帰: 0.205u 0.016s 0:00.31 69.0%     0+0k 0+0io 0pf+0w

コンソールへの出力などや実行方法も入っているので、言語の優劣は比較不可。
D はどちらも変わらない。この程度の計算じゃ負荷にならないのだろう。
guile のほうはそもそも積み上げ式だと計算できない。引数が 600 でもスタックが溢れてしまったので、このやり方だとよっぽど効率が悪いのだろう。
今まで馬鹿の一つ覚えみたいに積み上げ再帰をしてたけれど、これからは頭を使ってプログラミングをする必要がありそうだ。