関数の再帰的定義 (1/2)

再帰的定義とは？

関数の再帰的定義 (recursive definition) とは、関数の定義において今まさに定義しようとしている関数自体をもちいることです。

階乗の計算の場合をみてみましょう。自然数 n に対して、その階乗を返す関数 fact(n) を定義します。

fact (n) = 1 * 2 * .... * n

でも、プログラム中に .... なんて書くわけにもいきません。
これを再帰的に定義しようとすると、

fact (1) = 1
fact (n) = fact(n-1) * n       ; for n > 1

として定義することができます。

これを Scheme の program として記述すると以下のようになります。

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

関数の意味を、素直に表現しているだけです。

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