| 目次 | 索引 |
|---|---|
再帰とは、自分自身を呼び出すことです。 もちろん、ただ呼び出したのでは、無限ループに陥ってしまいます。 if文などを使い、ある条件のもとで自分を呼び出すのです。 再帰は、問題の種類によっては分かりやすい解決方法になります。
再帰的プログラム （ recursive program ）
再帰呼出し （ recursive call ）
再帰的手続き （ recursive procedure ）
再帰的関数 （ recursive function ）
はじめに、 n の階乗を計算します。 ここで、 n の 階乗 （ factorial ）とは、1から n までの積のことです。 これを、再帰を使って
fact(n) = n * fact(n - 1), fact(0) = 1
と定義します。
/* 1*/ class Factorial { /* 2*/ public static void main (String[] args) { /* 3*/ System.out.println("fact(3) is " + fact(3)); /* 4*/ System.out.println("fact(4) is " + fact(4)); /* 5*/ System.out.println("fact(5) is " + fact(5)); /* 6*/ } /* 7*/ static int fact (int n) { /* 8*/ if (n == 0) { /* 9*/ return 1; /* 10*/ } else { /* 11*/ return n * fact(n - 1); /* 12*/ } /* 13*/ } /* 14*/ }
b04a001@AsiaA1:~/comp3b% java Factorial fact(3) is 6 fact(4) is 24 fact(5) is 120 b04a001@AsiaA1:~/comp3b%
再帰的プログラムの例として、フィボナッチ数を取り上げます。 フィボナッチ数 （ Fibonacci number ）とは、
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...
のように、1, 1 から始め、直前の2つの数を足して次の数にするという数列です。 この規則は、
fib(n) = fib(n - 1) + fib(n - 2), fib(0) = fib(1) = 1
のように再帰を使って定義できます。 この定義をそのままプログラムにしますと、フィボナッチ数の計算ができるのです。
/* 1*/ class Fibonacci { /* 2*/ public static void main (String[] args) { /* 3*/ System.out.println("fib(3) is " + fib(3)); /* 4*/ System.out.println("fib(4) is " + fib(4)); /* 5*/ System.out.println("fib(5) is " + fib(5)); /* 6*/ } /* 7*/ static int fib (int n) { /* 8*/ if (n <= 1) { /* 9*/ return 1; /* 10*/ } else { /* 11*/ return fib(n - 1) + fib(n - 2); /* 12*/ } /* 13*/ } /* 14*/ }
b04a001@AsiaA1:~/comp3b% java Fibonacci fib(3) is 3 fib(4) is 5 fib(5) is 8 b04a001@AsiaA1:~/comp3b%
次の例として、ハノイの塔問題を取り上げます。 ハノイの塔問題 （ tower of Hanoi problem ）とは、大きさのすべて異なる n 枚の円盤が台Aに積み上がっているとき、台Bを利用して、すべての円盤を台Cに移動するという問題です。 ただし、円盤は一度に一枚しか移動できず、小さい円盤の上に大きい円盤はのせられません。
例えば、円盤が3枚ですと、初期状態は
+---+
| |
+-+---+-+
| |
+-+-------+-+
| |
---+-----------+--- ------------------- -------------------
A B C
であり、最終状態は
+---+
| |
+-+---+-+
| |
+-+-------+-+
| |
------------------- ------------------- ---+-----------+---
A B C
です。
この問題は、次のように再帰を使って解決できます。
ただし、 n が正でないときは何もしません。
n が3の場合は次のようになります。
+---+
| |
+-+---+-+
| |
+-+-------+-+
| |
---+-----------+--- ------------------- -------------------
A B C
+---+
| |
+-----------+ +-+---+-+
| | | |
---+-----------+--- -----+-------+----- -------------------
A B C
+---+
| |
+-+---+-+ +-----------+
| | | |
------------------- -----+-------+----- ---+-----------+---
A B C
+---+
| |
+-+---+-+
| |
+-+-------+-+
| |
------------------- ------------------- ---+-----------+---
A B C
再帰メソッドの名前は hanoi とします。 引数は、台の文字を表す x , y , z と枚数を表す n です。
/* 1*/ class HanoiTower { /* 2*/ public static void main (String[] args) { /* 3*/ hanoi('A', 'B', 'C', 4); /* 4*/ } /* 5*/ static void hanoi (char x, char y, char z, int n) { /* 6*/ if (n > 0) { /* 7*/ hanoi(x, z, y, n - 1); /* 8*/ System.out.println(x + " to " + z); /* 9*/ hanoi(y, x, z, n - 1); /* 10*/ } /* 11*/ } /* 12*/ }
b04a001@AsiaA1:~/comp3b% java HanoiTower A to B A to C B to C A to B C to A C to B A to B A to C B to C B to A C to A B to C A to B A to C B to C b04a001@AsiaA1:~/comp3b%
4桁のグレイ符号を表示するプログラムを作成してください。
ここで、 n 桁の グレイ符号 （ Gray code ）とは、0と1からなる n 桁の符号を縦に2の n 乗個並べたものです。 この2の n 乗個の符号はすべて異なり、直接上下する符号は1桁のみ異なります。
グレイ符号を構成するには、次にどの桁を反転するかのみ決定するとできます。 ここで、桁を反転するとは、0を1にすることと、1を0にすることです。 例えば、3桁のグレイ符号は、次のように^で示した桁を反転させるとできます。
0 0 0
^
1 0 0
^
1 1 0
^
0 1 0
^
0 1 1
^
1 1 1
^
1 0 1
^
0 0 1
ここでは、グレイ符号を配列 a に格納し、{0, 0, 0, 0} から始めることにします。 n 桁の場合の反転系列を、次のように再帰を使って決定します。
ただし、 n が正でないときは何もしません。
再帰メソッドの名前は gray とします。 引数は、配列型の a と桁数を表す n です。
なお、最初の符号0000は、再帰呼出しの前に出力しておいてください。
b04a001@AsiaA1:~/comp3b% java GrayCode 0000 1000 1100 0100 0110 1110 1010 0010 0011 1011 1111 0111 0101 1101 1001 0001 b04a001@AsiaA1:~/comp3b%
今日の演習4の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（10月15日）を明記してください。