第 2 章 Java 言語の基本的な文法 I 5
2.18 メソッド I
2.18.5 再帰プログラム
数学で、漸化式(recurrence relation)というのを学んだかと思います。「各項がそれ以前の項の式として定まる」と いう数列・数学的帰納法に関連する理論ですが、プログラムの世界でもこれと同等な考え方でプログラムを作ることが 可能です。以下のプログラムを解読してみて下さい。
ソースコード2.78 FibonacciRecursive.java (再帰プログラムによるフィボナッチ数) package section0218;
public class FibonacciRecursive {
public static void main(String[] args) { int n = 10;
System.out.println( "Fibonacci 数列の " + n + "番目の値は、" + fibo( n ) );
}
static int fibo( int n ) {
if( n == 1 || n == 2 ) return 1;
else return fibo( n-1 ) + fibo( n-2 );
} }
これは、フィボナッチ数（以前のプログラムでも作りましたね）を計算しています。フィボナッチ数列の n番目の値 Fn は、漸化式Fn=Fn−1+Fn−2, F1=F2= 1 を満たすので、それをそのままプログラムにしたわけです。
引数に nを与えられたメソッドfiboは、nが1もしくは2 の場合は1 を値として返します(return 1;)。一方、
n >2 の場合、fiboは自分のコピーに引数n−1とn−2 を渡してそれらの値を計算してもらい、その和を自分の戻
り値として返しています。こうすることで、mainメソッドは、フィボナッチ数列の10番目の値55を出力できるわけ です。難しいですか？
では、もう一つ例を。次のプログラムは何を計算しているでしょう？
ソースコード2.79 FactorialRecursive.java (再帰プログラムによる階乗) package section0218;
public class FactorialRecursive {
public static void main(String[] args) { int n = 10;
System.out.println( n + "! の値は、" + fact( n ) );
}
static int fact( int n ) { if( n == 1 ) return 1;
else return n * fact( n-1 );
} }
10 の階乗10! = 3628800 を計算していますね。n! =n×(n−1)!, 1! = 1をプログラム化したわけです。このよう
に、メソッドが引数の値を変えながら自分のコピーを呼び出して処理が続くプログラムを再帰プログラム(recursive
program)と言います。
では、さらにもう一例。ハノイの塔(Tower of Hanoi)という話を聴いたことがありますか？フランスの数学者リュ カが創作した「世界の中心にある寺院に3 本のダイヤの棒が立てられていて、そのうちの1本に大きさの異なる64枚 の純金の円盤が大きい円盤から順に刺さっている。それを僧侶たちが 1枚1 枚、小さい円盤の上に大きな円盤が乗ら ないようにしながら、他の棒に移動させている。全ての円盤の移動が終わるとこの世界も終わる。」という話です。
問題2.18.4. 1秒に1枚の移動を行ったとして、64枚全ての円盤が移動し終わるのにどの位の時間がかかるでしょう。
では、円盤の枚数を与えてハノイの塔をシミュレートするプログラムを作ってみましょう。
ソースコード2.80 HanoiTower.java (ハノイの塔) package section0218;
public class HanoiTower {
public static void main(String[] args) { int n = 3; // 円盤の数は３枚
hanoi( n, 'A', 'B', 'C' );
}
static void hanoi( int n, char a, char b, char c ) { if( n == 0 ) return;
hanoi( n-1, a, c, b );
System.out.println( n + "枚目の円盤を " + a + " から " + b + " に移動します" );
hanoi( n-1, c, b, a );
} }
メソッドhanoi は、引数が4つで戻り値なしのメソッドです。第1引数は円盤の枚数を整数値で、第2 から4 引数
は棒の名前を文字で与えています。そして、メソッドが呼び出されると、hanoi メソッドはn枚の円盤を第2引数の 棒(a)から第3引数の棒(b )へ全ての移動させる！という処理を始めます。第4引数(c)はその時の移動対象から 外れている棒の名前を記憶しておくために使われます。
A B C
図2.22 ハノイの塔(1)
A B C
図2.23 ハノイの塔(2)
さて、n 枚の円盤を棒Ａから棒Ｂへ移動させる際に、必ず経由しなければならない状態があります。それは、上に 乗っている n−1枚の円盤が全て棒Ｃに退いていて、最も下の最も大きな円盤を棒Ａから棒Ｂへ移動する、図ど 2.23の 状態です。
その状態を作るためには、1 枚円盤の少ないハノイの塔の問題、但し棒Ａから棒Ｃへの移動、を行えば良い。つ まり、メソッド hanoi を呼び出して、hanoi( n-1, 'A', 'C', 'B' )を行ってもらうわけです。その後で、最も 大きな円盤を棒Ａから棒Ｂに移動し、再度、1 枚円盤の少ないハノイの塔の問題、但し棒Ｃから棒Ｂへの移動、を hanoi( n-1, 'C', 'B', 'A' )で行えば、n枚の円盤の移動は完了となります。
こうして、n枚の円盤の移動が、n−1 枚の円盤の移動で「再帰的に」表され、それがさらにn−2枚の円盤の移動 で表され、· · · とメソッドhanoiが呼び出されていくわけです。もちろん、nの値がどんどん小さくなるとして、どこ かで止めないと無限に再帰が続いてしまいます。それを実現するためには、移動する円盤の数が0枚になったとき、つ
まりhanoi( 0, a, b, c )が呼び出されたとき、何もせずに呼び出し元へ戻って行けば良い。プログラムの9 行目
の命令がそれに対応します。
メソッドhanoiは戻り値の無い voidメソッドですから、戻り値を返すreturn命令は書けませんが、単に自分を
呼び出したメソッドへ帰る、戻り値を持たない単独の return 命令を置くことができます。先に、void メソッドは return 命令がないと学びましたが、実は、メソッドの最後に1 つreturn 命令が存在していて、メソッドの最後の return命令は省略可能というルールがあったのです。つまり、メソッド hanoiには9行目にreturn命令がありま すが、実はもう1つ12行目の後にreturn命令が隠れている、というわけです。
return命令は、戻り値のある・なしに関わらず、メソッド内のどこに置いても構いません。また個数にも制限がな
く、複数個のreturn命令を持つメソッドも可能です。ただし、return命令を置いたために、その直後の命令にどこ からも到達できなくなってはいけません。次のメソッドでは、ifブロックの中かっこを書き忘れたために5行目に到 達不可能なプログラムになっています。
static void method( int a ) {
if( a < 0 ) // 次の 2 行を囲むブロックを書き忘れた
System.out.println( "この命令を行った後、強制的に return" );
return;
System.out.println( "そのため、この命令は到達不可能" );
}
問題 2.18.5. 上のハノイの塔のプログラムで、n= 3と設定したとき、最大で幾つのhanoi メソッドがメモリー内に 同時に存在するか述べよ。
メソッドＡがメソッドＢを呼び出したとき、メソッドＢが終了しない限り、メソッドＡもメモリ内で待機状態になっ ています。つまり、この待機状態のメソッドが増えすぎてメモリーオーバーでプログラムが停止してしまう可能性を再 帰プログラムは持っています。
問題 2.18.6. 次のようなハノイの塔の発展形をプログラム化しなさい。
1. ３本の棒の間の移動をA→B→C→Aのみしか許さないで棒 Aから棒B へn枚の円盤を移動させるハノ イの塔のプログラムHanoiTower2.javaを作りなさい。
2. 上と同じルールのもとで、棒Aから棒Cへn枚の円盤を移動させるハノイの塔のプログラムHanoiTower3.java を作りなさい。
3. 円盤の移動ルールは基本と同じで、棒の数を４本A, B, C, Dとし、棒Aから棒 B へn枚の円盤を移動させる ハノイの塔のプログラムHanoiProblem4.javaを作りなさい。