再帰処理 recursive processing

2020-09-04

こんにちは、0371です。

今回は、再帰処理の方法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。

再帰処理 とは？

ある関数が、自分自身を呼び出すような処理のことを再帰処理と言います。

再帰処理を行うプログラム

言語はJavaです。

Main.java

// n*fact(n-1)の部分の表示方法がわからなかったので、prl()で結果だけ表示しています。
// すみません。orz

public class Main {

	public static void main(String[] args) {
		int count = 1;
		int num = 5;
		int ans = fact(num, count);
		System.out.println();
		System.out.println("===");
		System.out.println("ans: "+ans);
	}

	private static int fact(int num, int count) {
		int ans = 0;
		System.out.println("------");
		System.out.println((count++)+"回目の再帰処理です。");
		if(num == 0) {
			System.out.println("num: "+num);
			System.out.println("ans: "+1);
			prl();
			return 1;
		} else {
			System.out.println("num: "+num);
			System.out.println("ans: "+ans);
			return num*fact(num-1, count);
		}

	}

	private static void prl() {
		System.out.println();
		System.out.println("再帰終了。");
		System.out.println("ここから最新の再帰から順番に処理をする。");
		System.out.println();
		System.out.println("1*fact(1) = 1");
		System.out.println("1*fact(2) = 2");
		System.out.println("1*fact(3) = 6");
		System.out.println("6*fact(4) = 24");
		System.out.println("24*fact(5) = 120");
	}

}

確認なしverはこちら

public class Main {

	public static void main(String[] args) {
		int count = 1;
		int num = 5;
		int ans = fact(num, count);
		System.out.println("ans: "+ans);
	}

	private static int fact(int num, int count) {
		if(num == 0) {
			return 1;
		} else {
			return num*fact(num-1, count);
		}
	}
}

fact()メソッドの中では、再帰処理を行っています。 retutnで自分自身(fact())を呼び出すことで、続けてfact()メソッドの処理を行います。

確認ありverで、実行した結果は以下の通りです。

------
1回目の再帰処理です。
num: 5
ans: 0
------
2回目の再帰処理です。
num: 4
ans: 0
------
3回目の再帰処理です。
num: 3
ans: 0
------
4回目の再帰処理です。
num: 2
ans: 0
------
5回目の再帰処理です。
num: 1
ans: 0
------
6回目の再帰処理です。
num: 0
ans: 1

再帰終了。
ここから最新の再帰から順番に処理をする。

1*fact(1) = 1
1*fact(2) = 2
1*fact(3) = 6
6*fact(4) = 24
24*fact(5) = 120

===
ans: 120

成功していますね。

今日の一言

基本情報以外でも再帰処理は一般的に使われるので、しっかり押さえておこう。