マンガで分かる Java入門講座

第8章 メソッド
8-12. 再帰

再帰的に呼び出されるメソッドについて、その仕組みと挙動を紹介します。

● 再帰

　「再帰（再帰呼び出し、再帰処理）」とは、あるメソッドから、そのメソッド自信を呼び出す処理です。

　再帰では、適切な終了条件を用意しておかなければ、無限ループのような状態になってしまいます。

　以下、再帰の例を示します。

ソースコード）再帰
package sample;

public class Sample {
    public static void main(String[] args) {
        up(0);
    }

    public static int up(int i) {
        if (i < 3) {
            System.out.println(i);
            up(i + 1);
        }
        return i;
    }
}

出力）再帰
0
1
2

　再帰は、繰り返し処理という意味でループ処理と似ています。しかし。メソッドでは、そのメソッドごとにローカル変数が作成され、独立しています。そのため、処理毎に独立した値を保持することができ、ループ処理とは違った便利さがあります。

　上記の例では、この特性は活かされていません。通常のループ処理で書いた方が適切な処理だと言えます。

　以下、再帰の特性を活かした、少し複雑なプログラムを示します。

ソースコード）再帰2 文字の組み合わせを生成
package sample;

public class Sample {
    public static void main(String[] args) {
        System.out.println(strCmb("abc"));
    }

    // 文字の組み合わせを生成
    public static String strCmb(String src) {
        String res = "";  // 戻り値用文字列
        int len = src.length();  // 文字列長

        for (int i = 0; i < len; i ++) {
            char c = src.charAt(i);  // 対象文字
            String[] bArr = {""};    // 再帰結果の組み合わせ
            if (len >= 2) {
                // 2文字以上の場合は
                // 対象文字列以外を結合して再帰
                String bck = strCmb(
                    src.substring(0, i) +  // 前の文字列
                    src.substring(i + 1)   // 後の文字列
                );
                /*
                 * 「"abc"」の「'b'」が対象文字の場合
                 * 「"a"」が前の文字列
                 * 「"c"」が後の文字列
                 *
                 * 「"abc"」の「'a'」が対象文字の場合
                 * 「""」が前の文字列
                 * 「"bc"」が後の文字列
                 */
                bArr = bck.split("\n");  // 改行で分割
            }

            //対象文字列と、再帰結果の組み合わせを結合
            for (int j = 0; j < bArr.length; j ++) {
                res += c + bArr[j] + "\n";
            }
        }
        return res;
    }
}

出力）再帰2 文字の組み合わせを生成
abc
acb
bac
bca
cab
cba
この講座のマンガ部分は「箱人形マンガ(Box Comic) 」で作成しています。
作成：2013/06/02　 更新：2015/08/09　 [Permalink]