0371.blog

再帰処理 recursive processing

code

こんにちは、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

成功していますね。

今日の一言

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