再帰関数 (1)

あるメソッドが自分自身を 1回だけ呼ぶ関数を、僕は分岐しない再帰関数と呼んでいます。理解することがなかなか大変である再帰関数の中で、最もシンプルな形ということでもあります。

多分、一般論を説明するよりも、具体的な例を見たほうが早いと思います。さっそくサンプルプログラムを作っていきます。

階乗を求めるプログラムは G102.javaで作成済みです。このプログラムとまったく同じ動作をするプログラムを、再帰関数を利用して実現してみることにします。

仕様を以下に定めます。

• 1の階乗から 10の階乗までを表示する。なお階乗については以下の通り。
  • 階乗とは該当する数から 1までを乗算したもの。「5の階乗」とは 5×4×3×2×1、つまり 120 のこと。
• 階乗の計算部分を staticなメソッドに分離し、再帰関数を用いて実現する。
• 計算結果の値が大きくなるため、階乗の値を格納する変数には long型を使用することにする。今回は 10の階乗までなので int型で問題ないのだけど、今後のことを考えて念のため。

なお、階乗を求める再帰関数を漸化式のように表現すると、以下のようになります。

• a_n = n × a_n-1 (nの階乗は、それよりひとつ小さいものの階乗に nを掛けたものである)
• a₁ = 1 (1の階乗は 1)

1つめの意味は、例えば、「5の階乗は、5 × (4の階乗の値)である」ということです。

さっそく、この仕様を満たすプログラムを製作します。

G401/G401.java

/**
 * 1～10の階乗を表示します(再帰関数を使用)。
 */
public class G401 {
	/**
	 * メインメソッド。
	 * @param args 引数
	 */
	public static void main(String[] args) {
		for(int i = 1; i <= 10; i ++) {
			long value = G401.factorial(i);
			System.out.println(i + "の階乗は " + value);
		}
	}
	
	/**
	 * 指定した数の階乗を求めます。なお、0以下の値を指定した場合は Errorになります、注意。
	 * @param number 数
	 * @return 階乗の値
	 */
	private static long factorial(int number) {
		if(number == 1) {
			return 1L;
		} else {
			return number * G401.factorial(number - 1);
		}
	}
}

実行結果は以下の通り。

1の階乗は 1
2の階乗は 2
3の階乗は 6
4の階乗は 24
5の階乗は 120
6の階乗は 720
7の階乗は 5040
8の階乗は 40320
9の階乗は 362880
10の階乗は 3628800

メソッド factorialに漸化式の要素が組み込まれていることが理解できるでしょうか。factorialメソッドの実行中に、畳み掛けるように自分自身のメソッドを呼び出している(例えば 5の階乗の計算では、五重に呼び出される)ことが分かるでしょうか。

また、G102.javaと比較すると、factorialメソッドの中の for文が無くなったことが分かるでしょうか。再帰関数では、自分自身を呼び出すことで、結果的に for文や while文などの繰り返し構造が減少することが多いです。

平方根の近似値を、再帰関数を利用して実現してみます。

このプログラムは以下のように動作します。

• 1周目
  1. 初期値として 2、そして検索回数として 3を与えるとします。
  2. 左端 0と右端 2の平均値をとって 中央値は 1。
  3. 1の2乗は 1なので、2よりも小さい。つまり、2の平方根は 1より右側。
• 2周目
  1. 左端を 1、右端は 2。
  2. 左端 1と右端 2の平均値をとって 中央値は 1.5。
  3. 1.5 の2乗は 2.25なので、2よりも大きい。つまり、2の平方根は 1.5より左側。
• 3周目
  1. 左端を 1、右端は 1.5。
  2. 左端 1と右端 1.5の平均値をとって 中央値は 1.25。
  3. 1.25 の2乗は 1.5625なので、2よりも小さい。つまり、2の平方根は 1.25より右側。
  4. 最後。1.25と 1.5の平均値として近似値 1.375と判断します。

さっそく、この仕様を満たすプログラムを製作します。

G402/G402.java

/**
 * 平方根の近似値を表示します(再帰関数を用いて)。
 */
public class G402 {
	/**
	 * メインメソッド。
	 * @param args 引数
	 */
	public static void main(String[] args) {
		double number = MySystem.in.getDouble("正の数字を入力してください");
		int count = MySystem.in.getInt("探索回数を入力してください");
		
		if(number < 0.0) {
			System.out.println("負の数が入力されました。");
		} else {
			double sqrt = G402.sqrt(number, 0, number, count);
			System.out.println(number + "の平方根の近似値は " + sqrt + "です。");
		}
	}
	
	/**
	 * 再帰的に平方根を求めます。
	 * @param number 元の数
	 * @param a 下の値
	 * @param b　上の値
	 * @param count カウンタ
	 */
	private static double sqrt(double number, double a, double b, int count) {
		double c = (a + b) / 2.0;
		double c2 = c * c;
		if(count == 0) {
			// System.out.println("探索終了");
			return c;
		} else if(c2 == number) {
			return c;
		} else if(c2 > number) {
			// System.out.println(number + "の平方根は " + a + "と " + c + "の間です。");
			return G402.sqrt(number, a, c, count - 1);
		} else {
			// System.out.println(number + "の平方根は " + c + "と " + b + "の間です。");
			return G402.sqrt(number, c, b, count - 1);
		}
	}
}

実行結果の例は以下の通り。

正の数字を入力してください? 2
探索回数を入力してください? 3
2.0の平方根の近似値は 1.375です。

正の数字を入力してください? 49
探索回数を入力してください? 8
49.0の平方根の近似値は 6.986328125です。

コメントアウトしてある部分を出力するようにすると、動きがよく分かるかもしれません。