再帰処理 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
成功していますね。
今日の一言
基本情報以外でも再帰処理は一般的に使われるので、しっかり押さえておこう。