関数 （ function ） とは、呼び出されるとまとまった計算をして、呼んだ側に計算結果を返すプログラム単位です。 手続き （ procedure ） とは、呼び出されるとまとまった処理をして、呼んだ側に戻るプログラム単位です。 Java言語では、関数も手続きも メソッド （ method ） で実現します。
メソッドには、インスタンス・メソッドとクラス・メソッドがあります。 今日は、（同じクラスの）クラス・メソッドのみを扱います。
メソッドは、定義してから呼び出します。 メソッド定義の形式は、関数の場合は
static クラス名 メソッド名 (クラス名 変数名, ...) {
文の並び
}
となり、手続きの場合は
static void メソッド名 (クラス名 変数名, ...) {
文の並び
}
となります。 メソッド呼出しの形式は、関数の場合は式として
メソッド名(式, ...)
となり、手続きの場合は文として
メソッド名(式, ...);
となります。
メソッドの括弧の中は、 引数 （ argument ） と呼ばれます。 メソッドと呼ぶ側は、引数を使ってデータをやり取りします。
メソッド呼出しの括弧の中は、 実引数 （ actual argument ） と呼ばれ、メソッド定義の括弧の中は、 仮引数 （ formal argument ） と呼ばれます。 Java言語では、メソッドが呼び出されますと、仮引数の変数が用意され、そこに実引数の式の値が格納されます。 このように呼び出すことを、 値呼出し （ call by value ） と言います。
メソッドを呼び出したとき、引数が基本データ型ならば、仮引数に基本型の値がコピーされるだけですので、呼ぶ側のデータに影響はありません。 一方、引数が参照データ型ならば、仮引数に参照が格納されますので、呼ぶ側のデータに影響を与えられます。 この違いを、次の例で理解してください。
/* 1*/ class CallByValueTest { /* 2*/ public static void main (String[] args) { /* 3*/ int[] a = new int[1]; /* 4*/ a[0] = 100; /* 5*/ System.out.println("a[0] = " + a[0]); /* 6*/ clearVariable(a[0]); /* 7*/ System.out.println("a[0] = " + a[0]); /* 8*/ clearArray(a); /* 9*/ System.out.println("a[0] = " + a[0]); /* 10*/ } /* 11*/ static void clearVariable (int n) { /* 12*/ n = 0; /* 13*/ } /* 14*/ static void clearArray (int[] s) { /* 15*/ s[0] = 0; /* 16*/ } /* 17*/ }
b04a001@AsiaA1:~/comp3b% java CallByValueTest a[0] = 100 a[0] = 100 a[0] = 0 b04a001@AsiaA1:~/comp3b%
メソッドの中では、さらに他のメソッドを呼び出すこともできます。 さらに呼び出されたメソッドが終了しますと、呼んだメソッドに制御が戻ります。 この動作を確認するのが、次のプログラムです。
/* 1*/ class DoubleCall { /* 2*/ public static void main (String[] args) { /* 3*/ method1(); /* 4*/ } /* 5*/ static void method1 () { /* 6*/ System.out.println("The method call method1() begins."); /* 7*/ method2(); /* 8*/ System.out.println("The method call method1() ends."); /* 9*/ } /* 10*/ static void method2 () { /* 11*/ System.out.println("The method call method2() begins."); /* 12*/ System.out.println("The method call method2() ends."); /* 13*/ } /* 14*/ }
b04a001@AsiaA1:~/comp3b% java DoubleCall The method call method1() begins. The method call method2() begins. The method call method2() ends. The method call method1() ends. b04a001@AsiaA1:~/comp3b%
再帰とは、自分自身を呼び出すことです。 もちろん、ただ呼び出したのでは、無限ループに陥ってしまいます。 if文などを使い、ある条件のもとで自分を呼び出すのです。 再帰は、問題の種類によっては、分かりやすい問題解決の方法になります。
再帰を用いたプログラムを 再帰的プログラム （ recursive program ） と呼びます。 再帰的プログラムで、自分自身を呼び出すことを 再帰呼出し （ recursive call ） といいます。 再帰呼出しが行われる手続きと関数は、それぞれ 再帰的手続き （ recursive procedure ）、 再帰的関数 （ recursive function ） と呼ばれます。
次のプログラムでは、メソッド method3 の中で、自分自身を呼び出しています。 このプログラムを実行しますと、まず method3 (2) が呼び出され、その途中で method3 (1) が呼び出され、さらにその途中で method3 (0) が呼び出されます。 メソッドの実行が終了しますと、順次、呼んだ側に制御が戻ります。
/* 1*/ class RecursionTest { /* 2*/ public static void main (String[] args) { /* 3*/ method3(2); /* 4*/ } /* 5*/ static void method3 (int n) { /* 6*/ System.out.println("The method call method3(" + n + ") begins."); /* 7*/ if (n > 0) { /* 8*/ method3(n - 1); /* 9*/ } /* 10*/ System.out.println("The method call method3(" + n + ") ends."); /* 11*/ } /* 12*/ }
b04a001@AsiaA1:~/comp3b% java RecursionTest The method call method3(2) begins. The method call method3(1) begins. The method call method3(0) begins. The method call method3(0) ends. The method call method3(1) ends. The method call method3(2) ends. b04a001@AsiaA1:~/comp3b%
再帰の例として、はじめに、 n の階乗を計算します。 ここで、 n の 階乗 （ factorial ） とは、1から n までの積のことです。
これを、再帰的に
と定義します。 すると、例えば fact (3) は、
fact(3) = 3 * fact(2)
= 3 * 2 * fact(1)
= 3 * 2 * 1 * fact(0)
= 3 * 2 * 1 * 1
と計算できます。
/* 1*/ class Factorial { /* 2*/ public static void main (String[] args) { /* 3*/ System.out.println("fact(3) = " + fact(3)); /* 4*/ System.out.println("fact(4) = " + fact(4)); /* 5*/ System.out.println("fact(5) = " + 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) = 6 fact(4) = 24 fact(5) = 120 b04a001@AsiaA1:~/comp3b%
次の例として、フィボナッチ数を取り上げます。 フィボナッチ数 （ Fibonacci number ） とは、
のように、1, 1 から始め、直前の2つの数を足して次の数にするという数列です。 この規則は、
のように再帰を使って定義できます。 この定義をそのままプログラムにしますと、フィボナッチ数の計算ができるのです。
/* 1*/ class Fibonacci { /* 2*/ public static void main (String[] args) { /* 3*/ System.out.println("fib(3) = " + fib(3)); /* 4*/ System.out.println("fib(4) = " + fib(4)); /* 5*/ System.out.println("fib(5) = " + fib(5)); /* 6*/ } /* 7*/ static int fib (int n) { /* 8*/ if (n == 0 || 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) = 3 fib(4) = 5 fib(5) = 8 b04a001@AsiaA1:~/comp3b%
最後の例として、ハノイの塔問題を取り上げます。 ハノイの塔問題 （ tower of Hanoi problem ） とは、大きさのすべて異なる n 枚の円盤が台Aに積み上がっているとき、台Bを利用して、すべての円盤を台Cに移動するという問題です。 ただし、円盤は一度に一枚しか移動できず、小さい円盤の上に大きい円盤はのせられません。
例えば、円盤が3枚ですと、初期状態は
であり、最終状態は
です。
この問題は、次のように再帰を使って解決できます。
ただし、 n が正でないときは何もしません。
n が3の場合は次のようになります。
まず、上の2枚を、台Aから台Cを利用して台Bへ移動します。
次に、残った1枚を、台Aから台Cへ移動します。
最後に、2枚を、台Bから台Aを利用して台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%
パスカルの3角形を計算するプログラムを作成してください。 ここで、 パスカルの3角形 （ Pascal's triangle ） とは、3角形の辺には1を書き、内部には左肩と右肩の和を書いて得られる図形のことです。
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
: :
0番目から数え始め、上から n 番目、左から r 番目の数を、 combi ( n , r ) と書くことにします。 すると、パスカルの3角形は次のように定義できます。
この定義にしたがってメソッドを定義し、このメソッドを呼び出して、 combi (5, 0), combi (5, 1), combi (5, 2) を計算してください。
b04a001@AsiaA1:~/comp3b% java PascalTriangle combi(5, 0) = 1 combi(5, 1) = 5 combi(5, 2) = 10 b04a001@AsiaA1:~/comp3b%
余力のある人は、パスカルの3角形を8行分計算してください。 出力が左揃えになっても構いません。
b04a001@AsiaA1:~/comp3b% java PascalTriangle2 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 b04a001@AsiaA1:~/comp3b%
今日の演習3の答案（Javaプログラム）をメールで提出してください。 差出人は学内のメール・アドレス（b04a001@cis.twcu.ac.jpなど）とし、宛先はkonishi@cis.twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（10月12日）を明記してください。