繰り返しと末尾再帰 (1/2)

fact の例を再び

先程、 fact を次のように定義しました。

(define (fact n)
    (if (> n 1)
	(* n (fact (- n 1)))
	1))

先程も解説したように、このプログラムでは、 (fact 5) を計算しようとし、 (fact 4) が必要となり、、、、 (fact 1) = 1 がもとまり、それを (fact 2) の計算に返し、 (fact 2) = 2 * (fact 1) を実行し、、、、、 (fact 5) = 5 * (fact 4) と計算が進んでいきます。このように再帰を実行するために、深い呼び出し関係を生成しています。

繰り返し文

ところで、 C において階乗を計算する場合、普通どうしたでしょう。多くの人は繰り返し文を使ったのではないでしょうか？

int fact(n) {
    int result = 1;
    int i;
    for (i = 1; i <= n; i++) {
        result = i * result;
    }
    return result;
}

これは、繰り返し文を用いて result という値に、 1, ..., n を掛け合わせていくことによって値を得るものです。

99.9.29/ Tomio KAMADA: kamada@cs.kobe-u.ac.jp