プログラム言語 II TOP

関数(4)
再帰呼出し

例題6.4



1. 再帰関数(recursive function)
関数を定義する際,自分自身を使って定義する場合があります。このような定義の方法を再帰的定義(recursive definition)と呼びます。

これはプログラムとしては,関数の定義中に,その関数自身を呼び出すことになります(再帰呼出し recursive call)。このような関数を再帰関数と呼びます。


2. 例題6.4
階乗を再帰的に求める関数の例です。

負でない整数 n の階乗 n! は

  n! = n × (n-1) × (n-2) × … × 2 × 1 (ただし,0! = 1)

と定義されています。ここで,

   (n-1) × (n-2) × … × 2 × 1

が, (n-1)!であることに注意すると,

  n! = n × (n-1)!

と定義することもできます(階乗の再帰的定義)。

教科書では"10未満の正整数 n"とかなり範囲を限定しています。これは n の値がちょっと大きくなると,階乗の値がすぐに桁あふれするからです。

行番号16・17 で,n の値が 0 か 1 のときに再帰呼出しを行わずに,返却値 1として戻っています。このように再帰呼出しが無限に続かないように注意しなければなりません。

教科書p.107にあるように,これは繰返しにより容易に記述することができます。また,その方が効率が良いプログラムとなります。


3. 再帰関数の例(ハノイの塔)
これも有名な例題です(プログラムは講義中に資料として配布します)。


4. 演習
a) 整数 n (n>2)を読み込み,3番目から n 番目までのフィボナッチ(Fibonacci)数を求める再帰呼出しを用いたプログラムを作りなさい。

b) a を再帰呼出しを使わずに,繰返しで求めるプログラムに変更しなさい。


プログラム言語 II TOP